stoundmire's blog

By stoundmire, 11 years ago, In English
Problem A is quite straight-forward. You can simply enumerate all pairs using two for loops since N is not greater than 1000. Or you can sort the list and for every Ai, find the first Aj such that Aj-Ai>d in the range [i+1,N] using binary search.

Problem B doesn't need an array at all. You can consume a single character at a time using getchar and then output a '0' if the character is '.' or consume another character to determine whether to output '1' or '2' otherwise.

Problem D requires you to scan the map multiple times with increasing radii.

Problem C is a little tricky. Two cells are reachable from each other if and only if their horizontal or vertical distance is exactly S if they are on the same row or column, which is identical to the property that their indexes of one dimension is the same while those of the other are congruent modulo S. So you are to count the number of remainders modulo S whose occurrence is more frequent than others, which equals N%S when S divides N or N when not for rows. The number of such occurrences is the ceiling of N/S, the smallest integer no smaller than N/S. Multiplying the product of these two numbers for rows and that of the other two for columns together gives the answer.
I failed the test of this problem for a silly typing error.

I will write solutions for Problem E after I solve it. My knowledge and skills of computing geometry was poor, so I didn't have enough time coding during the contest.

This is the first time I participated in the contest, for previous contests were always at midnight.
Really enjoy it.
  • Vote: I like it
  • +22
  • Vote: I do not like it

11 years ago, # |
  Vote: I like it +3 Vote: I do not like it
thanks a lot for analysising so carefully !!!
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For the problem C you can simply note that if you stand at position k (0-based), then the number of positions you can reach is 1 + k/s + (n-k-1)/s. Then just calculate this number for each k and find the number of occurrences of the maximal one. This saves some thinking, IMHO.
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
^ ^