No.5022 XOR Printer
タグ : / 解いたユーザー数 60
作問者 :
prussian_coder
/ テスター :
butsurizuki
Problem Statement
You are given an $N \times N$ grid. The cell $(i,j)$, which is the $i$-th from the top and the $j$-th from the left, contains an integer $A_{i,j}$ satisfying $0 \le A_{i,j} < 2^{20}$.
You also hold a number $s=0$, and you are initially at $(1,1)$.
Perform the operations below at most $T$ times, and make the final sum $S = \sum_{i=1}^{N}\sum_{j=1}^{N} A_{i,j}$ of $A_{i,j}$ when you finish as large as possible.
- Move : Move one cell up, down, left, or right (however, you cannot move off the board)
U: Move from $(i,j)$ to $(i-1,j)$ (move up)D: Move from $(i,j)$ to $(i+1,j)$ (move down)L: Move from $(i,j)$ to $(i,j-1)$ (move left)R: Move from $(i,j)$ to $(i,j+1)$ (move right)
- Write :
W― With your current cell being $(i,j)$, replace $A_{i,j}$ with $A_{i,j}$ XOR $s$ - Copy :
C― With your current cell being $(i,j)$, replace $s$ with $s$ XOR $A_{i,j}$
What is bitwise XOR?
The bitwise XOR of non-negative integers $A$ and $B$, denoted $A \oplus B$, is defined as follows.- When $A \oplus B$ is written in binary, the digit in the $2^k$ place ($k \geq 0$) is $1$ if exactly one of the digits in the $2^k$ place of $A, B$ written in binary is $1$, and $0$ otherwise.
Scoring
Your score is the value of $S = \sum_{i=1}^{N}\sum_{j=1}^{N} A_{i,j}$ when the operations are finished.
There are 50 test cases in total, and the sum of the scores over all test cases is the score of the submission.
However, if an invalid output or a time limit exceeded occurs in one or more test cases, the verdict of the entire submission will be WA or TLE.
Each participant's score can be viewed from the problem's "スコア順" (ordered by score) tab.
Input
$N$ $T$
$A_{1,1}$ $A_{1,2}$ ⋯ $A_{1,N}$
$A_{2,1}$ $A_{2,2}$ ⋯ $A_{2,N}$
⋮
$A_{N,1}$ $A_{N,2}$ ⋯ $A_{N,N}$
The input satisfies the following constraints.
- $N=10$
- $T=1000$
- $0 \le A_{i,j} < 2^{20}$ ($1 \le i, j \le N$)
- $A_{i,j}$ is an integer
Output
Let $M ( \le T)$ be the number of operations. Output in the following format.
$op_1$ $op_2$ ⋮ $op_M$
-
Each $op_k$ is one of
UDLRWC -
The following outputs will be judged as
WA- Moving off the board (a move resulting in $(i,j)$ with $i < 1$ or $i > N$ or $j < 1$ or $j > N$)
- The number of operations exceeds $T$
- Outputting an invalid operation character
Sample
Sample 1
Input
10 1000 264226 49169 452706 349656 591257 939313 965593 85397 632720 206018 566467 227769 615110 36900 345036 944860 703330 25814 842273 504621 820650 600306 657703 890023 445115 285847 371164 351616 509743 394296 81048 469097 173897 292799 386172 959727 149443 413245 589783 630430 916789 148189 268015 64518 295892 1046550 120834 270207 633559 440055 14749 933562 780924 54922 973454 480092 573280 261141 875995 51989 102482 891735 665329 563073 111119 714504 173520 502300 1015148 932589 434745 808253 755323 1034601 1032220 817896 683830 91987 707464 75264 12567 780789 971178 299603 190120 21290 1046392 559226 979416 364764 1023915 637535 261266 55386 617350 609300 1009204 1048372 583444 40394
Output
R W C D L W U
The above is an example showing the output format and does not represent an optimal solution.
Input Generation
- $A_{i,j}$ is chosen uniformly at random from integers between $0$ and less than $2^{20}$.
Tools (Input Generator and Visualizer)
- Web version: More capable than the local version and supports animated display.
- Local version: Contains sample inputs, input generation code, a local tester (C++), and more. For detailed usage, see README.md.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。