JOI-chan was selected to represent Japan in the upcoming IOI. In order to improve his information processing skills, manager K of the Japanese Informatics Olympic Committee has presented him with a task as follows:
Manager K will write down a string S that he will not reveal to JOI-chan. S consists only of the characters '<', '>', '[' and ']'. Manager K will still tell JOI-chan the length of the string.
JOI-chan's task is to determine if the string S is good. Whether or not a string is good is defined by the following rules:
- It is an empty string. In other words, it is a string of length zero.
- If x is a good string, then <x> is also a good string.
- If x is a good string, then [x] is also a good string.
- If x and y are good strings, then xy is also a good string.
For example, "<>[]" and "[<>]<>" are good strings, but "><" and "[<]>" are not.
JOI-chan will can make a phone call to Manager K once a day at noon. JOI-chan can give Manager K an integer I, to which Manager K will respond by telling JOI-chan the Ith character of S.
However, JOI-chan is not allowed to make any notes about this problem or otherwise note any information about it down. The only exception to this is the length of the string, which JOI-chan will always have access to. Apart from that, JOI-chan is only allowed to rely on his own memory. Every day, JOI-chan sleeps at 10 pm and wakes up at 6 am, during which he can only remember 22 bits of information. In other words, before he sleeps, JOI-chan can memorize any integer from 0 to 222 - 1 and recall it in the morning.
Relying only on his memory and his smarts, JOI-chan must determine if Manager K's string is good through the daily phone calls within 15 000 days.
Implementation
You are to write one program to implement JOI-chan's strategy for determing if Manager K's string is good. The program should include Memory_lib.h as a header. Within the program, you must implement the following function.
Your program is allowed to call this function.
-
char Get(int I)
- Within every call to
Memory you are allowed to call this function at most once. If this function is called more than once within one call of Memory, your program will receive a "Wrong Answer (2)" verdict.
- Parameter I must be within the bounds 1 ≤ I ≤ N. If this function is called with a parameter I that does not satisfy those bounds, then your program will receive a "Wrong Answer (3)" verdict.
- This function will return the Ith character of S.
Grading Process
The program is graded against a selection of test cases each of which consist of multiple test strings S with the same length N. For each test string, the grading process terminates immediately whenever a "Wrong Answer" verdict is determined.
Given the length of the strings N, the grader will investigate the behavior of your program for all possible inputs. In other words, for each M satisfying 0 ≤ M ≤ 222 - 1, the following process will be used:
- For each character c in '<', '>', '[' and ']',
Memory will be called with parameters N and M. If Get is called during the execution of Memory, c will be returned. The grader will store the return value of Memory(N, M) as m(M, c).
- In the four calls to
Memory performed above, any calls to Get must be exactly the same. In other words, if a call to Get is made during any of the calls to Memory for this particular M, then all of the three other calls to Memory should call Get with the same parameter I. If no call was made to Get during one of the calls to Memory for this particular M, then all of the three other calls to Memory should also not produce any calls to Get. If this condition is not satisfied, your program will receive a "Wrong Answer (4)" verdict.
- If a call to
Get was made, the grader will store the parameter to Get as i(M). If no call was made, i(M) = 1.
For each of the strings S in the test case, the grader will simulate the process described in the problem as follows:
M is initially 0.
-
Repeat forever:
- Set c to the i(M)th character of S.
- Set M to m(M, c).
- If M is -1 or -2, break.
- If this is the 15 000th iteration, your program will receive a "Wrong Answer (5)" verdict.
-
If any of the conditions below are satisfied, your program will receive a "Wrong Answer (6)" verdict.
- S is a good string but M = -2.
- S is not a good string but M = -1.
Your program will receive a "Correct" verdict.
Important Note
The runtime of your program will be the runtime of the grading process as described above. Namely, note that Memory will be called 222 × 4 times.
The simple grader provided runs your program according to a simulation of the problem above, whereas the strict grader provided runs your program according to the grading process described above. Due to the difference in grading method, the simple grader is not able to determine a "Wrong Answer (4)" verdict.
Constraints
All test cases satisfy the following constraints.
- 1 ≤ N ≤ 100.
- S consists of only characters '<', '>', '[' and ']'.
Subtasks
Subtask 1 (10 points):
Subtask 2 (10 points):
Subtask 3 (5 points):
Subtask 4 (5 points):
Subtask 5 (10 points):
- S contains only characters '<' and '>'.
Subtask 6 (60 points):
No further constraints.
Sample Input
4 1
<>[]
Explanation
According to the behavior of the simple grader, here is an example of the sequence of calls made.
Call to Memory | Return value | Call to Get | Return value |
|---|
Memory(4, 0) | | | |
| | Get(1) | |
| | | < |
| 2015 | | |
Memory(4, 2015) | | | |
| | Get(3) | |
| | | [ |
| 3 | | |
Memory(4, 3) | | | |
| | Get(2) | |
| | | > |
| 23 | | |
Memory(4, 23) | | | |
| | Get(4) | |
| | | ] |
| 4194303 | | |
Memory(4, 4194303) | | | |
| | Get(3) | |
| | | [ |
| -1 | | |