RTE '16 J3 - Mule Wars

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem types

While many claim that Richmond Hill High School is one of the most peaceful schools they've ever seen, their words aren't necessarily true. Enter mule wars, a devastating battle that has been going on for the past decade, right below the school. The mules run around trying to find jelly beans, shooting each other with deadly STRANGOs, all while trying their best not to get covfefed, the ultimate humiliation.

All of this started when the mule king, Mr. Lookinhere, learned about an escaped prisoner, which he dubbed the 'runaway jelly bean'. The king, being quite skilled in mathematics, decided that in order to maximize their chances of finding the runaway jelly bean, they needed to maximize the number of jelly beans they found. So, he fabricated a contest for his mule peasants to collect and store as many jelly beans as possible. His plan was to then search through all of the captured jelly beans every week. At the end of each week, he collects all of the jelly beans and destroys them.

You, being the supreme admiral general of programming for King Lookinhere, have been tasked to help him determine an optimal group of people to search for the following T weeks, before he gives up. In each of the T weeks, the king will provide you N, the number of mules competing, which he numbers from 1 to N and C, the number of actions that will happen, which includes the mules acquiring jelly beans, and the queries to determine the optimal group to search. Your program must respond to the following commands:

  • A n x: Mule x found n jelly beans.
  • Q x: Return the number of jelly beans mule x has.
  • G x: Return the number of jelly beans the first x mules have.
  • L x: Return the number of jelly beans the last x mules have.
  • Covfefe x: Mule x loses all of its jelly beans, and will be unable to collect any jelly beans given to it for the rest of the week.

Input Specification

The first line of input will contain T (1 \le T \le 1\,000), the number of weeks.

For each of the T weeks, the first line will contain two space separated integers, N (1 \le N \le 1000), and C (1 \le C \le 10\,000).

The next C lines will contain any of the commands specified above, followed by their targets.

For test cases worth 40 of 100 points, the input will only contain commands A and Q commands.

Output Specification

Given command Q, G, or L, you must output a single integer representing the number of jelly beans the specified group has in total, among all of its respective members, at the point in time the command is issued at.

Sample Input 1

1 2
A 100 1
Q 1

Sample Output 1


Explanation for Sample 1

There's one mule competing in the one week of competition. The first command dictates that mule 1 (the only mule in this competition) found 100 jelly beans. The second command asks for the number of jelly beans mule 1 has.

Sample Input 2

5 12
A 100 1
A 200 1
Q 1
Covfefe 1
A 500 1
A 375 2
Q 1
Q 2
G 2
A 500 3
G 3
L 3

Sample Output 2


Explanation for Sample 2

There is only one week of competition. There are 5 mules competing.

  1. Mule 1 finds 100 \rightarrow [100, 0, 0, 0, 0]
  2. Mule 1 finds 200 \rightarrow [300, 0, 0, 0, 0]
  3. Return value of mule 1 \rightarrow 300
  4. Mule 1 finds covfefed \rightarrow [x, 0, 0, 0, 0]
  5. Mule 1 finds 500, but it's covfefed, so there's no impact \rightarrow [x, 0, 0, 0, 0]
  6. Mule 2 finds 375 \rightarrow [x, 375, 0, 0, 0]
  7. Return value of mule 1 \rightarrow covfefed = 0
  8. Return value of mule 2 \rightarrow 375
  9. Return sum of first two mules \rightarrow 0 + 375 = 375
  10. Mule 3 finds 500 \rightarrow [x, 375, 500, 0, 0]
  11. Return sum of first three mules \rightarrow 0 + 375 + 500 = 875
  12. Return sum of last three mules \rightarrow 0 + 0 + 500 = 500


  • 0
    herro  commented on Feb. 6, 2021, 12:02 p.m.

    how big can n be?

  • 2
    Jerry_Gu  commented on Feb. 13, 2018, 3:34 p.m. edited

    If T>1, then would the commands be looped? So for sample input 2, if T=2 then what would be the output?

    • 0
      injust  commented on Feb. 13, 2018, 5:33 p.m. edit 2

      Each week can be processed as a separate case. The commands do not loop.

      For sample input 2, if T = 2, there would have to be additional lines of input.

  • 1
    Phoenix1369  commented on June 16, 2017, 7:12 p.m.

    The point value of this problem has been halved.

    Partial scoring has been enabled and all submissions have been re-scored. Apologies for any inconvenience caused.