DMOPC '16 Contest 3 P2 - Starstruck Squeeze

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 128M

Authors:

Phoenix1369, jackyliao123

Problem type

jackyliao123 is part of the robotics team in his school. During one of the meetings after school, a sketchy person was wandering around and came into the robotics room. This person sees a storage bin full of the VEX Starstruck jacks and immediately becomes obsessed with them. Phoenix1369 sees this and tells him that he can disassemble one of the jacks by squeezing them. The person does so, and the jack breaks into pieces.

Due to the sketchy nature of this person and his obsession with the jacks, he begins to take $K$ ~K~ jacks from the storage bin one by one, and squeezing them. This frenzied period continues for $N$ ~N~ seconds.

Every second, the person does one of two possible actions:

T: Takes one jack out from the storage bin, and places it on the table.
B q: Breaks each jack or piece that's currently on the table into q pieces, and puts them on the floor. When the table is empty, transfer all the pieces on the floor back onto the table.

jackyliao123 needs to gather all these pieces so that he can fix them by gluing them together at home. After a few minutes, he realizes that the number of pieces is growing rapidly. In order to ~~prevent integer overflow~~ allow jackyliao123 to finish the work that was assigned by his English teacher, he decides that he will consider a jack "dust" if the jack is broken into strictly greater than $D$ ~D~ pieces, and he will not be gluing them back together.

jackyliao123 needs to figure out how many pieces each jack has been broken into, to assist him in gluing together the jacks that the person broke.

Since jackyliao123 is quite busy building the robot, can you help him figure this out?

Input Specification

The first line will contain the integers $N$ ~N~, $K$ ~K~ and $D$ ~D~, representing the number of modifications done by the sketchy person, the number of jacks in the storage bin, and the dust threshold respectively.

The next $N$ ~N~ lines represent the operations. Each line will contain either just a character T, or a character followed by an integer B q, where $q$ ~q~ is the integer.

Constraints

For all subtasks:

$1 \le K \le N$ ~1 \le K \le N~

$1 \le D \le 10^6$ ~1 \le D \le 10^6~

$1 \le q \le 1000$ ~1 \le q \le 1000~, for each $q$ ~q~

Subtask 1 [50%]

$1 \le N \le 100$ ~1 \le N \le 100~

Subtask 2 [50%]

$1 \le N \le 10^5$ ~1 \le N \le 10^5~

Output Specification

Output the number of pieces each jack has been broken into, in the order they were taken out of the storage bin.

If a jack has been considered as dust, output dust.

Sample Input

7 4 5
T
T
B 2
B 3
T
B 4
T

Sample Output

dust
dust
4
1

Explanation

The person did $7$ ~7~ operations on the $4$ ~4~ jacks that were in the storage bin, and jackyliao123 will consider any jacks that got broken up into more than $5$ ~5~ pieces as "dust".

The person takes out a jack from the bin and puts it on the table.
He takes out another jack. (Same operation as above)
He breaks each of the 2 jacks into 2 pieces, resulting in $2$ ~2~ broken pieces for the first jack and $2$ ~2~ broken pieces for the second jack.
He then breaks each piece into 3 new pieces, resulting in $6$ ~6~ broken pieces for the first jack and $6$ ~6~ broken pieces for the second jack.
He takes out another jack.
He then breaks each piece into 4 new pieces, resulting in $24$ ~24~ broken pieces for the first jack, $24$ ~24~ broken pieces for the second jack, and 4 broken pieces for the third jack.
He takes out another jack.

In the end, he took out 4 jacks, the first 2 were broken into $24$ ~24~ pieces each and therefore considered as "dust" by jackyliao123. The third jack was broken into $4$ ~4~ pieces, and the fourth jack was not broken, therefore it remains as $1$ ~1~ piece.

Comments

2

marshmelllo commented on April 11, 2017, 9:44 p.m.

Why am I MLEing?

1

P234rex commented on April 12, 2017, 9:56 p.m. ← edited →

I'm not sure but I think it's due to your product function. My guess is that as $N$ ~N~ gets really large, you're essentially performing something along the lines of a manual factorial or exponent function and storing all the steps.

0

Walt28 commented on Dec. 16, 2016, 4:23 a.m.

If the table becomes empty while breaking the pieces, do I move the pieces from the floor to the table?

3

Paradox commented on Dec. 16, 2016, 5:40 a.m.

Don't worry about the floor thing. Just assume that the pieces stay on the table at all times. Don't move anything to the floor.

1

println_hi_ commented on Dec. 14, 2016, 8:15 a.m.

Currently only 1 python submission has passed with question in time(from the mighty D). Would it be possible to get a time extension for python

1

r3mark commented on Dec. 14, 2016, 6:42 p.m.

It wasn't an issue with the language. Your solution's time complexity is too slow for the constraints.

0

println_hi_ commented on Dec. 15, 2016, 6:47 a.m.

I know realise that, thank you