LCC '22 Contest 5 S5 - Jimmy's Ribbon

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem types

The University of Waterloo's admission decisions are approaching soon! In a desperate attempt to impress the admissions committee, Jimmy decides to send them a gift, which he would like to wrap up using a ribbon. He has a ribbon of length N.

Jimmy puts the ribbon on a number line such that the left end is at 1, and the right end is at N. Each point has a thickness of 1. There are two ways in which he can fold the ribbon:

  1. L x: Jimmy holds his finger down at point x (as a pivot) and folds whatever is to the left of x onto the right side.
  2. R x: Jimmy holds his finger down at point x (as a pivot) and folds whatever is to the right of x onto the left side.

Note that Jimmy can sometimes fold beyond the left and right edges of the ribbon (see Sample Case 2), but the ribbon will never be folded to a negative coordinate.

After the M folding operations that Jimmy performs, determine the final length of the ribbon and the maximum thickness at any point on the ribbon.

Input Specification

First line: N (initial length of the ribbon) and M (the number of folds). Next M lines: Each line describes a fold of type L or R as described above.

Output Specification

Output two space separated integers: the final length of the ribbon and the maximum thickness.

Constraints

For all test cases, 1 \le N \le 10^9, 1 \le M \le 10^6. In addition, x will always be a position on the ribbon at the time of folding.

Important Note: for every subtask,

  1. Outputting the correct final length earns you 30% of the subtask's points.
  2. Outputting the correct maximum thickness earns you 70% of the subtask's points.
Subtask 1 [30%]

1 \le N \le 1000, and there will only be folds of type L.

Subtask 2 [20%]

1 \le N \le 1000

Subtask 3 [40%]

1 \le N \le 10^7

Subtask 4 [10%]

No additional constraints.

Sample Input 1:

6 1
L 3

Output for Sample Input 1:

4 2
Explanation for Sample Case 1:

Here is the thickness at every x-coordinate at every folding stage (the pivot at each fold is bolded):

Folding stage 1 2 3 4 5 6
Initial (before folding) 1 1 1 1 1 1
After L 3 fold 2 2 1 1

Therefore, the final length of the ribbon is 4, and the maximum thickness is 2.

Sample Input 2:

7 2
L 6
R 9
R 6

Output for Sample Input 2:

3 4
Explanation for Sample Case 2:

Here is the thickness at every x-coordinate at every folding stage (the pivot at each fold is bolded):

Folding stage 1 2 3 4 5 6 7 8 9 10
Initial (before folding) 1 1 1 1 1 1 1
After L 6 fold 2 2 1 1 1
After R 9 fold 2 2 1 2
After R 6 fold 2 1 4

Therefore, the final length of the ribbon is 3, and the maximum thickness is 4.


Comments

There are no comments at the moment.