Page 1 of 1
11194 - Stone Grid
Posted: Sun Mar 04, 2007 12:56 pm
by JL
This last sample case outputs 4:
Which 2 of these are not a solution and why?
Code: Select all
0 0
-1 -1
0 0
0 0
-1 -1
1 1
0 0
-1 -1
2 2
1 1
-1 -1
0 0
2 2
-1 -1
0 0
1 1
-1 -1
1 1
Posted: Sun Mar 04, 2007 1:11 pm
by Erik
Hi,
I got the same question and sent a clarification request, which is not answered yet.
Anyway I solved it now. It's about the interpretation of
For the same reason, they do not want the final arrangement to have more stones than the initial grid configuration does.
It means that in the end no cell may contain more marbles than it had initially. Hence, solutions
would be considered wrong.
I got Accepted this way.
Cu, Erik
Posted: Sun Mar 04, 2007 7:50 pm
by sclo
It turns out that I have badly misintepreted this problem during the contest, and that's why I keep getting WA. They should rewrite the problem statements to make it a little more clear.
So L is the maximum total number of stones allowed in an arrangement, and each cell can't have more stones than what it has in the initial configuration.
I'll have to rewrite much of my program to fix this.
Posted: Tue Mar 06, 2007 6:41 am
by rushel
A small hint on a problem please.
thanks
Posted: Tue Mar 06, 2007 8:02 am
by sclo
A small hint:
Each cell is either odd or even. A cell (i,j) is odd(even) iff (i+j)%2 is odd(even).
A bigger hint:
Think about connected components.
There exists a sequence of moves to move any stone on odd(even) cell to any other odd(even) cell in the same component, leaving the number of stones on all other cells unchanged.
Another hint:
If we remove any stones from an odd(even) cell, we must remove an equal number of stones from an adjacent even(odd) cell.
My hints are enough to solve this problem.
Posted: Wed Mar 07, 2007 5:41 am
by rio
Could someone verify my IO ? Thanks in advance.
Input:
Code: Select all
5
1 2 0
-1 1
3 2 4
1 1
-1 1
1 0
4 4 20
8 9 0 -1
-1 2 1 9
9 2 3 6
5 -1 -1 -1
4 4 10
3 9 0 -1
-1 -1 -1 9
0 2 3 6
5 -1 2 -1
4 4 14
9 9 0 -1
-1 -1 -1 9
7 2 -1 6
5 -1 2 -1
Posted: Wed Mar 07, 2007 7:37 am
by LayCurse
>rio
My AC program gives the same output as yours.
Posted: Wed Mar 07, 2007 9:00 am
by rio
Thanks LayCurse. I found the bug and got AC. My code was overflowting with big test cases.
----
ところで十号館の住人だったりする？