No.2545 Divide by 3
タグ : / 解いたユーザー数 32
作問者 :
Nachia
Problem Statement
This problem is output-only.
There is a sequence $A = (A_1, A_2, \dots, A_N)$ of length $N = 100$. Initially, $A_1 = X, A_2 = 1$, and $A_i = 0$ for $i \geq 3$. Here, $X$ is a non-negative integer satisfying $0 \leq X \leq 10^9$, and it is not given in the input.
You may perform the following operations up to $1000$ times. Here, $i, j, k$ are integers satisfying $1 \leq i, j, k \leq N$.
plus i j k: Set $A_i \leftarrow A_j + A_k$.div i j: Set $\displaystyle A_i \leftarrow \left \lfloor \frac{A_j}{2} \right \rfloor$.
However, at no moment during the operations may $A_i$ become $2^{64}$ or greater.
Your goal is to have $\displaystyle A_3 = \left \lfloor \frac{X}{3} \right \rfloor$ after performing all the operations. Output one sequence of operations that achieves this.
Input
No input is given.
Output
On the $1$st line of the output, print the number of operations $M$ $(0 \leq M \leq 1000)$.
On the following $M$ lines, starting from line $2$, print the operations to perform. On line $i + 1$, print the $i$-th operation in the format given in the problem statement.
Judge
If the submitted sequence of operations does not follow the format described in the Problem Statement and Output sections, the judge result is undefined.
If the format of the submitted sequence of operations is correct, the judge program executes the sequence of operations independently for $10^4$ integers $X$ predetermined for each test case.
If, as a result of executing the sequence of operations for every $X$, $A_i$ never becomes $2^{64}$ or greater at any point during the operations and $\displaystyle A_3 = \left \lfloor \frac{X}{3} \right \rfloor$ holds after all the operations have been performed, the judge's verdict is AC. Otherwise, the verdict is WA.
Sample
An example of a sequence of operations in the correct format is shown below. In this example, for the case $X = 3$, we get $A_3 = 4$ after the operations, so the condition is not satisfied and it is judged incorrect.
5 plus 3 1 2 plus 4 4 4 div 5 3 div 5 2 plus 100 2 5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。