ECOO '19 R2 P3 - Ribbon

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 13.0s
Memory limit: 512M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

After wrapping a present for her friend’s birthday, Elaine discovered that she has a long length of ribbon left over. The ribbon is currently unwound, so she decided that she will fold the ribbon M times before putting it away in a small box. To make sure the ribbon will fit, she would like to know what the length and thickness of the ribbon will be once she performs her sequence of folds.

The ribbon initially has a length of N units and a thickness of 1 unit. When folding a ribbon at a point P from the left, the part of the ribbon left of P is folded onto the part of the ribbon right of P. Formally, for all K > 0, the thickness of the ribbon at the point P - K is added to the thickness at the point P + K - 1 and the thickness at the point P - K becomes zero. Folding the ribbon from the right is the same up to symmetry.

The thickness of the ribbon is defined as the maximum thickness of any given point. The length of the ribbon is defined as the number of points with non-zero thickness. Given the sequence of M folds, can you help Elaine determine the dimensions of the final ribbon?

Input Specification

The input will contain 10 datasets. Each dataset begins with two integers N, M (1 \le N \le 10\,000\,000, 1 \le M \le 1\,000\,000), the initial length of the ribbon and the number of folds. The points of the ribbon are numbered from 1 to N.

The next M lines each contain an integer P (1 \le P \le N) followed by either L or R, representing a fold at point P from either the left or right. The point P is guaranteed to be at a point with non-zero thickness.

For the first 3 cases, each fold will be of type L. For the first 6 cases, N \le 1\,000.

Output Specification

For each dataset, output two space-separated integers: the length and thickness of the ribbon.

Sample Input (Two Datasets Shown)

6 1
3 L
10 2
10 L
10 R

Sample Output

4 2
8 3

Explanation of Sample Datasets

In the first dataset, the thickness of the ribbon at each point is 2, 2, 1, 1.
In the second dataset, the thickness of the ribbon at each point is 1, 1, 1, 1, 1, 1, 1, 3.

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments

There are no comments at the moment.