P1335 [NOI2013] Xiao Q's Training

Xiao Q recently found a new game whose goal is to train a novice into a master of martial arts. Facing a complex game world, Xiao Q must make careful choices for everything he encounters. For example, whether to accept a duel invitation from a stranger; whether to agree or refuse to exchange a treasured sword for someone else’s martial arts manual... Every choice Xiao Q makes may affect his future development: when facing an expert, actively dueling may cause heavy losses; but if he doesn’t duel, he might never meet that expert again. After playing many times without getting the ending he wants, Xiao Q finally managed to obtain the game’s script. Surprisingly, the script is not like the ones we usually see; it looks more like code. The script is described as follows: - Quantity: There are $2$ kinds of quantities, constants and variables. - Constant: An integer. - Variable: A mutable integer with initial value $0$. Different variables are distinguished by different positive integer IDs. - Event: The entire script consists of several events. All events are numbered in the given order starting from $1$. There are $3$ kinds of events: normal event, choice jump, and conditional jump. - Execution position: An integer indicating the event number to be executed next. If there is no event with this number, execution stops; that is, the game reaches an ending. Initially, the execution position is $1$. - Normal event: A variable increases or decreases by the value of a quantity. Afterwards, the execution position increases by $1$. - Choice jump: Two integers. When execution reaches this point, the player must choose one of the two integers, and the execution position will be set to that integer. - Conditional jump: Two quantities and two integers. When execution reaches this point, if the first quantity is less than the second quantity, the execution position will be set to the first integer; otherwise, it will be set to the second integer. Xiao Q believes the game intends to maximize a variable called "achievement value" (ID $1$).

This is an answer-submission problem. All input data `train1.in` ~ `train10.in` are provided in the attached files. The first line of input contains two positive integers $n, m$, denoting the number of events and the number of variables. Then there are $n$ lines, each describing an event. These events are numbered $1$ to $n$ in the given order. The formats for quantities and events are as follows (in the format, `#` denotes a space): ::cute-table{tuack} | Type | Format | Example | |:-:|:-:|:-:| | Constant | `c#整数` | `c -2` | | Variable | `v#正整数` | `v 5` | | Normal event | `变量#+#量` | `v 1 + c 1` | | Normal event | `变量#-#量` | `v 2 - c 2` | | Choice jump | `s#整数 1#整数 2` | `s 10 20` | | Conditional jump | `i#量 1#量 2#整数 1#整数 2` | `i c 99 v 2 0 1` |

For the given $10$ input files `train1.in` ~ `train10.in`, you need to submit your output files `train1.out` ~ `train10.out` respectively. Each file should output several lines, each line containing a single character `1` or `2`, indicating the choice made at each encountered choice jump during execution. The number of output lines must be exactly equal to the number of choice jumps encountered during this run.

Scoring For each set of data, we score as follows: - If your output is invalid, you get $0$ points. - If your output causes the script to execute more than $10^6$ lines, you get $0$ points. - If your output lets the script terminate normally, you get $1$ point. - If your output lets the script terminate normally and the final achievement value is positive, you get $2$ points. We set $8$ scoring parameters $a_3 , a_4 , \ldots , a_{10}$. If your output lets the script terminate normally and the final achievement value is at least $a_s$, you get $s$ points. If multiple items above are satisfied, the highest applicable score is taken. How to test your output We provide the tool `checker` to test whether your output file is acceptable. To use it, first open a terminal and run the following commands to enter this problem’s folder: `cd train` Then run: `./checker ` Here `case_no` is the testdata ID. For example, `./checker 3` will test whether `train3.out` is acceptable. After you invoke this program, `checker` will report the test result for your output file, including: - Abnormal exit: Unknown error. - `Input/Output file does not exist.`: Input/output file does not exist. - `Output invalid.`: The output file is incorrect; specific error messages may be included. - `Correct! Your answer is x.`: The output is acceptable, and the final achievement value is $x$. More features `checker` can also check arbitrary input/output files. In the terminal, run: `cd train` `./checker ` where `input_file_name` and `output_file_name` are the names of the input and output files, respectively. For example, `./checker train3.in train3.out` tests whether `train3.out` is acceptable. Use `-w` to print the result of each execution step. Usage: `./checker -w ` or `./checker -w ` For example, `./checker -w train3.in train3.out` Special Note If you use self-generated input files for debugging, the checker may fail due to excessive scale. If this happens, please try smaller-scale testdata. Translated by ChatGPT 5