No.5002 stick xor
タグ : / 解いたユーザー数 88
作問者 :
Note from the Organizers
The contest is scheduled to end at2018-06-01 22:00:00. It is unrated.After a submission, unless its result is
CE, you cannot submit again for 5 minutes.We apologize for the inconvenience, but for the rankings, please refer to the score order tab above rather than the contest standings.
Problem Statement
There is a grid of size $N\times N$. Each cell of the grid is painted either pure white or jet black.
For the cell $(y,x)$, which is the $y$-th from the top and the $x$-th from the left, $A_{y,x} = 0$ if it is pure white and $A_{y,x} = 1$ if it is jet black.
You perform $K$ operations on this grid.
In the $i$-th operation, you choose a rectangle within the grid with height $L_i$ and width $1$, or with height $1$ and width $L_i$ (that is, either vertical or horizontal),
and flip the cells in the rectangular region: pure white cells become jet black and jet black cells become pure white.
Let $W_0$ be the number of pure white cells before the operations and $W_K$ be the number of pure white cells after the $K$ operations. Your points are then $W_K-W_0$.
Find a placement of the rectangles that makes your points as high as possible.
Since this is a score-based problem, you do not need to find an optimal solution.
Your score is the sum of the points over all test cases. There are 32 test cases.
Input
$N$ $K$
$L_1$ $\ldots$ $L_K$
$A_{1,1}$ $\ldots$ $A_{1,N}$
$\ldots$
$A_{N,1}$ $\ldots$ $A_{N,N}$
$N = 60$
$K = 500$
$1 \le L_i \le 25$
$A_{i,j} \in \{0,1\}$
All values are integers.
There are no separators, such as spaces, between $A_{i,j}$ and $A_{i,k}$.
Test Case Generation
All test cases are randomly generated. There are no artificial test cases (such as an entirely white grid).
- Each $L_i$ is chosen with equal probability from the values satisfying the constraints.
- Each cell is generated as a jet black cell with probability
1/2.
Output
$a_1$ $b_1$ $c_1$ $d_1$ $\ldots$ $a_K$ $b_K$ $c_K$ $d_K$
$1 \le a_i \le c_i \le N$
$1 \le b_i \le d_i \le N$
Either $a_i=c_i, d_i-b_i+1=L_i$ or $b_i=d_i, c_i-a_i+1=L_i$ must be satisfied.
Output $K$ lines.
The $i$-th line means that the rectangle $長方形(a_i,b_i,c_i,d_i)$ is chosen for the $i$-th operation.
Here, the rectangle $長方形(a,b,c,d)$ is the set of cells $\{(y,x)|a\le y\le c,b \le x\le d\}$.
This is a score-based problem.
Any output that satisfies the format gets AC, but please aim for as high a score as possible.
Visualizer
The visualizer is available here
Note: Please end your standard output with a newline. Otherwise, it may not work.
2018/05/26 10:26 It now works with or without a trailing newline.
Sample
Sample 1
Input
3 3 2 1 3 001 110 000
This input does not satisfy the problem's constraints, so it is not included in the test cases. It also does not work in the visualizer.
Sample Output
1 3 2 3 2 1 2 1 2 1 2 3
After the 1st operation, the grid is in the following state.
000 111 000After the 2nd operation, the grid is in the following state.
000 011 000After the 3rd operation, the grid is in the following state.
000 100 000The number of pure white cells has increased from the original 6 to 8, so you get 2 points.
Sample 2(gen_case1.txt)
Input
It is available on Github Gist.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。