D - Good Code
It's time for the members of The Team to do what they do best - coding! Faster than you can say "Dijkstra", they've already produced an elegant piece of work. The program has N (1 ≤ N ≤ 106) lines of code (conveniently numbered 1..N), and just one integer variable, c, which starts with a value of 0. The program starts executing at line 1, and every line i contains one of the following:
c++;" — The value of c is incremented by 1. Then, if i = N, the program terminates - otherwise, the program moves to line i + 1.
x:" — This line contains the label x, where x is an integer such that 1 ≤ x ≤ 106. No value of x will appear as a label more than once in the program. If i = N, the program terminates - otherwise, the program moves to line i + 1.
goto x;" — The program jumps to the single line that contains the label x, where x is an integer such that 1 ≤ x ≤ 106. It is guaranteed that, for every such line, the corresponding label will exist in the program.
Now, even though this program is glorious, its creators are wondering if it's quite correct. In particular, they know that c should ideally reach a value of M (1 ≤ M ≤ 1012), but they're not sure when. If the program terminates with c ≤ M, then certainly there's an issue, and the program should get a WA (Wrong Answer). If the program will never terminate, and c will never reach a value of M, then that's also no good, and can be considered a TLE (Time Limit Exceeded). In all other cases, however, The Team would like to know exactly on which line c will first attain a value of M. Naturally, having written the program, they instantly realized this already. But can you?
First line: 2 integers, N and M
Next N lines: The i-th line of the program (as described above), for i = 1..N
Either 1 integer, the number of the line on which c will first reach a value of M, or the string "
WA" if the program terminates with c < M, or the string "
TLE" if the program runs forever with c < M.
12 4 c++; goto 6; 18: c++; c++; goto 2; goto 6; 6: goto 18; 2: c++; c++;
Explanation of Sample
The program will run through the following lines, and corresponding values of c:
Line 1 ("
c++;"), c = 1
Line 2 ("
goto 6;"), c = 1
Line 8 ("
6:"), c = 1
Line 9 ("
goto 18;"), c = 1
Line 3 ("
18:"), c = 1
Line 4 ("
c++;"), c = 2
Line 5 ("
c++;"), c = 3
Line 6 ("
goto 2;"), c = 3
Line 10 ("
2:"), c = 3
Line 11 ("
c++;"), c = 4
As can be seen, c first achieves a value of M = 4 on line 11.
Point Value: 15
Time Limit: 4.00s
Memory Limit: 64M
Added: Jun 01, 2012
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3