Woburn Challenge 2016-17 Round 2 - Senior Division
Problem 3: Turbolift Testing
Lieutenant commander Scetty has been assigned quite the tedious task - testing a turbolift. Hardly a job worthy of the Enterprise's chief engineer! This particular turbolift has just 2 buttons – one to take the turbolift up 1 floor, and another to take it down 1 floor.
One "button press" is an action consisting of, well, pressing one of the buttons. It can be represented as a single character, either "
U" if the up button is pressed, or "
D" if the down button is pressed.
One "button sequence" is an ordered sequence of one or more button presses. The turbolift has the ability to perform N (1 ≤ N ≤ 200,000) different types of button sequences, numbered from 1 to N, with the i-th one represented by the string Bi. The j-th character in this string represents the j-th button press in the sequence. The strings B1..N are not necessarily distinct, and the sum of their lengths is at most 200,000.
The turbolift will start on floor 0 of the Enterprise. Due to recent technological advances, the ship has infinitely many floors above floor 0 (numbered upwards from 1), and infinitely many basement floors below it (numbered downwards from −1). As part of the testing process, it will then be programmed to execute M (1 ≤ M ≤ 200,000) button sequences, one after another. The i-th button sequence in this sequence of sequences will be button sequence is Si (1 ≤ Si ≤ N). Note that some button sequences could be executed multiple times during the testing, while others could not be executed at all.
Throughout the process, Scetty will make notes about how low and high the turbolift ends up getting. In particular, he has Q (1 ≤ Q ≤ 200,000) questions to answer. The i-th one asks: "After the first Pi button presses, what are the minimum and maximum floor numbers that the turbolift will have reached up to that point?". Pi is a positive integer no greater than the total number of button presses which will be executed throughout the sequence of M button sequences. Note that both Pi and the answers may not fit within a 32-bit integer.
In test cases worth 12/27 of the points, N ≤ 3000, M ≤ 3000, and no single button sequence consists of more than 3000 button presses.
The first line of input consists of three space-separated integers N, M, and Q.
N lines follow, the i-th of which consists of a single string Bi (for i = 1..N).
M lines follow, the i-th of which consists of a single integer Si (for i = 1..M).
Q lines follow, the i-th of which consists of a single integer Pi (for i = 1..Q).
Output Q lines, the i-th of which should consist of two space-separated integers – the lowest and highest floors that the turbolift will reach after no more than Pi button presses (for i = 1..Q).
2 3 3 DDUU U 2 1 2 1 6 4
0 1 -1 2 -1 1
The turbolift will receive 6 button presses in total, with the following results:
Button | Floor -------------- U | 1 D | 0 D | -1 U | 0 U | 1 U | 2
Point Value: 15 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: Dec 11, 2016
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3