Training Site
Sideways banner

Crochet Rounds

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 100 megabytes
Time limit: 1.0 seconds

You are crocheting a very specifically shaped hacky-sack in a spiral round, and have in front of you instructions which stitches to use. The process of crocheting the hacky-sack is as follows: You start with a circle of 6 stitches. We will consider these stitches row 0 of the hacky-sack. Starting with your trusty 7mm crochet hook in one of these stitches, you repeatedly either create a certain number of new stitches using the current stitch, or create a single stitch from several stitches in front of your hook. Each stitch you create belongs to the row above the stitch(es) you created it from. If you create a stitch from several stitches (during a 'decrease') the row of the created stitch is one above the stitch with the greatest row number.

Now begins the problem. You are given a sequence of instructions, where an instruction is either an 'increase' instruction of the form Ix, indicating you should create x stitches using the current stitch and move on to the next stitch, or a 'decrease' instruction of the form Dx, indicating you should create one stitch from the next x stitches, moving to the next stitch after all these stitches. The created stitches effectively replace the used stitches in the circle. However, these instructions are not labelled by row, which is somewhat annoying.

Write a program that, given a sequence of instructions, computes the number of stitches left in the round after following said instructions, and the row number of the last created stitch.

You are guaranteed the sequence of instructions will be valid, that is, the number of unused stitches will always remain above zero, and a decrease instruction will never use more than the number of unused stitches.


On the first line is a single integer n (1 \leq n \leq 10 000), the number of instructions. The following n lines each contain a single instruction, Ix or Dx, where x is a positive integer (1 \leq x \leq 20).


Output two lines. On the first line output the number of unused stitches remaining. On the second line output the row number of the last created stitch.


  • Subtask 1 (+30%): There are only 'increase' instructions.
  • Subtask 2 (+30%): 'Decrease' instructions will never use stitches from different rows.
  • Subtask 3 (+40%): No further constraints.

Sample Cases Explanation

Sample Case 1

The unused stitches labeled by row number would evolve as follows (with the current stitch at each step preceded with an 'h', and the newly created stitches in parentheses):

h000000 -> 1h00000 -> 111h0000 -> 1111h0 -> h111111 -> 222h11111 -> 2222h111.

(Note the stitches loop from the end back to the start)

Thus there are 7 unused stitches remaining at the end, with the last created stitch being in row 2.

Sample Case 2

h000000 -> 1h00000 -> 11h00 -> 2h1.

Thus there are 2 unused stitches remaining at the end, with the last created stitch being in row 2.

  • Sample Input 1


    Sample Output 1

  • Sample Input 2


    Sample Output 2