| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 37 | 14 | 11 | 39.286% |
Tim has a machine for sorting balls, namely WEB machine. The WEB machine has a wheel with $n$ slots. Each slot may have a white ball (W), a blue ball (B), or it can be empty (E). Over a certain slot, the machine has a head to identify the status of the slot. The head can determine the color of the ball in the slot. It can also pick the ball in the slot or drop the ball into the slot. The head, however, can hold at most one ball at a time. The WEB machine can rotate the wheel of slots clockwise or counterclockwise. Fig. 1 shows an example of WEB machine.
Fig 1. An example of a WEB machine
The WEB machine operates according to the control instructions, namely WEB instructions, and one can write a program as a sequence of the WEB instructions. The set of WEB instructions and their meaning is defined as follows:
Pick: picks up and holds the ball in the current slot under the head,Drop: drops the ball of the head to the current slot,Left: rotates the wheel clockwise by a slot,Right: rotates the wheel counterclockwise by a slot,LeftStar $C$: rotates the wheel clockwise while condition $C$ holds and returns the number of slots rotated,RightStar $C$: rotates the wheel counterclockwise while condition $C$ holds and returns the number of slots rotated,Jump $n$: jumps to the next $n$th instruction (If $n$ is 2ドル,ドル the next instruction is skipped and the next of the next instruction is executed),Jump $n$ if $C$: jumps to the next $n$th instruction if condition $C$ holds and do nothing otherwise,Stop: stops the machine.Executing Pick or Drop, the machine does nothing for improper conditions: the slot is empty while executing Pick or the slot is not empty while executing Drop. The variable $X$ should be a capital letter other than W, E, and B. The condition $C$ in LeftStar $C,ドル RightStar $C,ドル or Jump $n$ if $C$ is either one of W, E, B, and $X$ (a variable) or one of the negated forms (!W, !E, !B, and !$X$). The condition W implies that the ball in the current slot under the head is white, B does it is blue, and E does the slot is empty. The condition $X$ holds if $X$ is nonzero ($X \ne 0$). The negated condition holds if the unattributed condition does not hold, say !E is true when E does not hold. For instance, when executing RightStar !E, the head searches for an empty slot by rotating the wheel counterclockwise. As a result, there will be an empty slot under the head if the machine has at least one empty slot. The instruction incurs an infinite loop if the machine has no empty slot.
The number $n$ in unconditional jump (Jump $n$) and conditional jump (Jump $n$ if $C$) can be a negative integer. For instance, Jump -1 branches to the previous instruction. Beware that you should not execute Jump 0 which incurs an infinite loop.
The assignment instruction $X = E$ evaluates the integral expression $E$ and stores the value in variable $X$. The expression’s value is in the range between $-200$ and $+200$ inclusive ($|E| ≤ 200$). The expression can use any variable that has been defined before. For example, K = K + 1 will increase the variable K by one if K is defined before; it is an error, otherwise. The expression can be a star instruction, either LeftStar or RightStar; the assignment will store the number of slots rotated in the target variable. For example, executing the following assignment:
X = RightStar B
on the machine of the state in Fig. 1 will make the state in Fig. 2, and the value of variable X will be two.
Fig 2. After RightStar B is executed
As another example, the following code will restore the state in Fig. 1 from the state in Fig. 2:
LeftStar !W Right Pick Drop Stop
where the third and fourth instructions are listed to demonstrate the relationship between them; Pick and Drop are the inverse operations of one another.
Note that the expression cannot be nested, i.e. it can include at most one binary arithmetic operator (either + or -) or the star instruction. From the arithmetic operators, only the addition (+) and subtraction (-) operators are allowed; the multiplication, division, and modulus operators are invalid in the WEB expressions. The assignment and arithmetic operators should be separated from their operands by space. A space should not follow the sign symbol for an integer literal, say “-12” is valid but “- 12” is not.
Tim wants to sort the balls in the WEB machine using a WEB program, a sequence of WEB instructions ending with Stop. Initially, the balls are mixed in any order though they are grouped in the wheel. Tim wants the balls to be sorted into a group of white balls and blue ones separated by a group of empty slots reading clockwise starting from the head. Though the groups of balls are separated by a group of empty slots clockwise, they are not separated counterclockwise since they are in the wheel of the machine. Let’s help Tim by writing a sequence of WEB instructions to make the balls in the wheel sorted in W, E, and B order reading clockwise starting from the head.
The WEB program consists of several lines, each of which contains a single WEB instruction. Therefore, the above WEB programs are valid, but the following one is invalid, i.e. a syntax error:
RightStar E X = 10 + 2
since the assignment is spanned over two lines; the first instruction has an extra variable at the end and the second instruction is missing the target variable of the assignment.
Make a WEB program to sort the balls as Tim wanted and submit the WEB program. Your WEB program should convert the initial configuration of a WEB machine into the final one with the balls sorted by color and must end with Stop. The initial configuration is given as input and the final one is given as output. In the initial configuration, assume that the wheel of the WEB machine has at least two empty slots. Initially, all empty slots are grouped in a sequence over the slots. Assume also that the machine has at least one white ball and one blue ball. In the final configuration, the white and blue balls should be separated by a sequence of empty slots with the head located over the leftmost white ball assuming the clockwise reading of the slots.
The initial configuration of the WEB machine is given from standard input. The first line of input contains a positive integer $s$ (5ドル ≤ s ≤ 100$), the number of slots of the machine. The second line contains a sequence of $s$ characters indicating the initial state of the wheel. The character in the second line is one of W, B, and E indicating a white ball, a blue ball, and an empty slot, respectively. The characters are given in clockwise and separated by space. The first character indicates the slot under the head of the machine. The character E’s are given consecutively in groups.
The final configuration of the machine is given from standard output. Your WEB program is to sort the balls in the initial WEB machine resulting in the final configuration. The final configuration is a sequence of $s$ characters indicating the final state of the wheel. The balls should be sorted in the order with the white ball(s), the empty slots, and the blue ball(s) clockwise starting from the head.
5 B W B E E
W E E B B
7 W B W E E E W
W W W E E E B
8 W E E W B W B B
W W W E E B B B
You have to submit a WEB program, say sort.web, to operate on the WEB machine of a given initial configuration. The WEB program should convert the initial configuration to the final configuration as Tim wanted. You should select Text as the submission language.
For testing purposes, you are provided with a WEB machine simulator, which can read the WEB program file and the initial configuration of the WEB machine. The simulator is just for your convenience, so it is not mandatory to use it. If you want to use it, you can download the attachment wm.py. It can detect some kinds of errors, either syntax or run-time errors; it shows the final configuration resulting from the execution of the WEB program given an initial configuration; it counts the number of steps required to execute the WEB program — see the function $σ$ described later. The final configuration is shown in the standard output and the errors are shown in the standard error: the syntax error is reported as Wrong Answer [1] and the run-time error is reported as Wrong Answer [2]. The number of steps is also shown in the standard error. Though the simulator is useful for testing WEB programs, it may not provide complete information for evaluating your code. You just use it as a reference for testing a WEB program. Note that passing the simulator does not guarantee that the WEB program will be accepted by the auto-judge system.
The simulator assumes the WEB program file as the first argument in the command line and the initial configuration is read from the standard input. For example, the following command will execute the WEB program file named sort.web for the first sample input using the simulator wm.py:
> python wm.py sort.web 8 B B E E E W B W
where the first character in the first line (>) denotes the prompt. The simulator is executable on a Python interpreter of version greater than or equal to 3.9. You may test the following code for sort.web to get the configuration in Fig. 2:
X = RightStar B Stop
The simulator will force to terminate the execution of the WEB program within a certain number of steps. The number of steps of instructions is calculated by the function $σ,ドル which is defined as follows:
Pick$) = 1,ドルDrop$) = 1,ドルLeft$) = 1,ドルRight$) = 1,ドルLeftStar $C) = k$ where $k$ is the number of slots rotated clockwise,RightStar $C) = k$ where $k$ is the number of slots rotated counterclockwise,Jump 0ドル) = ∞,ドルJump $n) = 1$ for nonzero $n,ドルJump 0ドル$ if $C) = ∞$ if $C$ is true and 1ドル$ otherwise,if $C) = 1$ for nonzero $n,ドルStop$) = 1$.Note that the number of steps of the star instructions (LeftStar and RightStar) can vary depending on the condition. Also, note that the number of steps of the jump instructions for 0ドル,ドル say Jump 0ドル$ or Jump 0ドル$ if $C$ for any valid condition $C,ドル is infinite. A copying assignment, say X = Y, is covered by the case of $σ(X = e)$ where $e$ is not a star instruction. Therefore, $σ($X = Y$) = 1$.
Your WEB program should complete the execution in 70ドル,000円$ steps. If the number of steps exceeds the limit, 70ドル,000円$ steps, the auto-judge and the simulator force to terminate the WEB program — it is regarded as time out.
ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Seoul Nationalwide Internet Competition 2024 K번
Text