PEG Judge - NOI '13 - Little Q's Training

National Olympiad in Informatics, China, 2013

Day 1, Problem 3 - Little Q's Training

Little Q recently discovered a new video game. The objective of the game is to train from a lowly noob to a powerful master.

Facing an intricate virtual world, little Q must make careful decisions about the events that lie ahead. For example, whether he should accept a stranger's challenge to battle, whether he should accept or reject an offer to trade his precious blade for another's martial arts manual, etc. Furthermore, Little Q's every decision might impact how his future develops: for example, voluntarily facing a master may lead to heavy losses, but not accepting the fight may lead to never being able to see the master again.

Little Q has played through this game many times, yet still he has not been able to play through to his desired ending. So, he has painstakingly tracked down the game's storyboard. Surprisingly, the storyboard for this game does not at all resemble the average video game storyboard. Instead, it very much resembles source code. The storyboard is outlined as follows:

Value: Can be one of two types – a constant or a variable.
Constant: An integer.
Variable: An integer, initially 0, that can change throughout the game. Each variable is identified by its unique positive integer index.
Event: The entire storyline consists of some number of events. All events are numbered sequentially starting from 1. Can be one of three types – a normal event, an optional jump, or a conditional jump.
Position: An integer representing the number of the next event that will happen. If an event with this number doesn't exist, then the game has found an ending and will stop. Initially, the position will be 1.
Normal event: A variable will increase or decrease by a value. Afterwards, the position will be incremented by 1.
Optional jump: Two integers. Reaching here, the player must pick one of the two integers. Afterwards, the position will be set equal to the selected integer.
Conditional jump: Two values and two integers. Reaching here, if the first value is smaller than the second value, then the position will be set equal to the first integer. Otherwise, the position will be set equal to the second integer.

Little Q believes that the objective of the game is to make the variable called "EXP" (index 1) as large as possible.

Input Format

There will be 10 files train1.in ~ train10.in that will be given to your program (through standard input). They can be downloaded here for you to study: train.zip.

For each test case:

The first line of input contains an integer from 1 to 10, representing the test case number. Test case traini.in will have i on its first line.
The second line of input will contain two positive integers n and m, representing the number of events and the number of variables.
The following n lines each describes an event. These events are numbered sequentially from 1 to n.
The format of each event is outlined as follows:

Type	Format	Example
Constant	`c <Integer>`	`c -2`
Variable	`v <Positive Integer>`	`v 5`
Normal Event	`<Variable> + <Value>` `<Variable> - <Value>`	`v 1 + c -1` `v 2 - v 2`
Optional jump	`s <Integer 1> <Integer 2>`	`s 10 20`
Conditional jump	`i <Value 1> <Value 2> <Integer 1> <Integer 2>`	`i c 99 v 2 0 1`

Output Format

For each test case, output some number of lines. On each line output a single character, either "1" or "2", representing the decisions made for optional jumps as the game progresses. The number of lines outputted must strictly match the number of optional jumps encountered throughout the gameplay.

Sample Input

0
11 2
v 2 + c 19
i v 2 c 3 7 3
s 4 7
v 1 + c 13
v 2 - c 3
i c 0 c 1 2 0
i v 2 c 5 12 8
s 9 12
v 1 + c 23
v 2 - c 5
i c 0 c 1 7 0

Sample Output

Explanation

If the storyboard was numbered as follows,

1 2 3 4 5 6 7 8 9 10 11	v 2 + c 19 i v 2 c 3 7 3 s 4 7 v 1 + c 13 v 2 - c 3 i c 0 c 1 2 0 i v 2 c 5 12 8 s 9 12 v 1 + c 23 v 2 - c 5 i c 0 c 1 7 0

then according to the sample output, the positions would undertake the following values: 1→2→3→4→5→6→2→3→4→5→6→2→3→4→5→6→2→3→7→8→9→10→11→7→8→9→10→11→7→12

When the position becomes 12, the game ends. The final value of variable 1 is 85.
Event 1 consists of variable 2 increasing by 19. We can think of it as receiving 19 units of initial gold.
Event 6 is an unconditional jump to event 2. It is not hard to see that this is a cycle. From event 2 and event 3, we can observe that if variable 2 is less than 3 (gold is not enough to make purchase) or if a choice is made to exit, then the cycle will be broken. Within the cycle, events 4 and 5 will cost 3 gold units to obtain 13 EXP.
Events 7 and 11 form a similar loop only with different parameters. It costs 5 units of gold to obtain 23 EXP.
Noticeably, the sample is an unbounded knapsack problem. The sample output yields its optimal solution.

Grading

For each test case, the following method will be used to determine your score out of 10:
If your output is invalid, then you will score 0 points.
If your output executes more than 10⁶ lines of storyboard, then you will score 0 points.
If your output allows the story to terminate normally, then you will score 1 point.
If your output allows the story to terminate normally, and your EXP at the end is a positive value, then you will score 2 points.
We have set up 8 parameters a₃, a₄, …, a₁₀.
If your output allows the story to terminate normally, and your EXP at the end is no less than a_S, then you will score S points.
If multiple of the above conditions are satisfied, the one with the greatest score will be counted.
Formally speaking, if your solution is valid and yields a final value of v₁ for variable 1, then your score will be given in accordance to the following table.

Score	Condition
10	`v`₁ ≥ `a`₁₀
9	`a`₉ ≤ `v`₁ < `a`₁₀
8	`a`₈ ≤ `v`₁ < `a`₉
7	`a`₇ ≤ `v`₁ < `a`₈
6	`a`₆ ≤ `v`₁ < `a`₇
5	`a`₅ ≤ `v`₁ < `a`₆
4	`a`₄ ≤ `v`₁ < `a`₅
3	`a`₃ ≤ `v`₁ < `a`₄
2	0 < `v`₁ < `a`₃
1	`v`₁ ≤ 0

Experimentation

We provide a tool train_check.py for you to help check if your output program is valid. The usage for this program is:

train_check.py <case_no>

where <case_no> is the number of the test case. For example:

train_check.py 3

will test train3.out to determine whether it is accepted.

After you invoke this program, the checker will provide the result to the execution of your output file in one of the following ways:

Abnormal termination: An unknown error occurred.
Input/Output file does not exist.: We cannot load your input or output file.
Output invalid.: There is an error with your output file. A general error message may now be included.
Correct! Your answer is x.: Your output is acceptable. The final value of the EXP variable is x.