|
|
back to boardShow all messages Hide all messagesJust use diagonal painting:
1 2 3 ... k ... (total n times)
2 3 4 ... 1 ... (total n times)
. . . ... . ... (total n times)
Calculate, how many 1,2, ... k in this table. Answer will be minimal
of them(every rectangle 1xK covers K different colors).
I don't no is this mathematically correct, but this solution got AC.
Don't forget, that if N < K answer is 0.
P.S. Sorry for bad English. > Just use diagonal painting:
> 1 2 3 ... k ... (total n times)
> 2 3 4 ... 1 ... (total n times)
> . . . ... . ... (total n times)
> Calculate, how many 1,2, ... k in this table. Answer will be minimal
> of them(every rectangle 1xK covers K different colors).
> I don't no is this mathematically correct, but this solution got AC.
> Don't forget, that if N < K answer is 0.
> P.S. Sorry for bad English. email me: caa@baga.ac.net.ru >>> vasilisk_voin@mailru.com Can anybody give me example for this table?Please...
For example what table will be if n=5 k=3 ? if N=5 and K=3 the correct answer is 8 but not 7. To see the solution don't use the square (3,3) in the 5*5 grid
Edited by author 13.11.2005 13:39
Edited by author 13.11.2005 13:39 Why such found minimal value really
achivable in all cases? its because for each number in the table there you can put 1*K piece so that it won't intersect with others.And answer is minimum value because each piece lays on K diffirent numbers so you can't put more pieces that numimum value of 1...k
PS. Thanks! It's really easy to solve with O(1) time with your tips! This is only your belive...
Told property has only minimal number. THE PROOF
1) if you "stack" the coffins, you use up all of the graveyard, except for N%K square in the corder.
2) if you "spiral" the coffins, you leave N-2(N%K) square in the middle after the first spiral, N-4(N%K) square after the second spiral, until you use up all of the graveyard, except for (N-2(N%K))%K square in the middle.
(N-2(N%K))%K = (-N)%K = K-N%K
3) if we use the better of the two strategies, we use up all of the graveyard, except for M=min(N%K, K-N%K) square. How many colors will it have?
The first row will be colored 1..M, the second 2..M+1, the last M..2M-1
All K colors will be present iff 2M-1>=K
4) M=min(N%K, K-N%K) guarantees M<=K/2
Therefore, the remaining square will not have all K colors.
This proves that using the better of the two strategies exhausts at least one of the K colors, QED. please tell your idea more in detail thanks, i got AC when i use your idea.
but i dont why it's true?
who's know?
|
|
|
