Блог пользователя stoundmire

Автор stoundmire, 13 лет назад, По-английски
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.
  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
thanks a lot for analysising so carefully !!!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Может кто-то перевести как решить задачу C. А то на английском я не понял ни чего (дажу гугл переводчик не помог:(). Или как нить более понятно объяснить.
Спасибо большое.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Идея следующая(более расширенно чем перевод)
    1. Чтобы из одной клетки добраться до другой, разность по x и по y должна делиться на s - то есть условно можно разбить все клетки на классы по достижимости. Это будет соответствовать взятию по модулю s для каждой из координат. x-y=0(mod x) => x=y(mod x)
    2. Теперь надо найти количество остатков по модулю s, у которых больше класс(т.е. больше клеток, в которые можно придти). Утверждается, что это n%s, если n не делится на s или n иначе. Другими словами это (n-1)%s+1. Для m всё аналогично.
    3. Однако надо посчитать не количество классов, а количество элементов в лучших классах. В одном классе будет ceil(n/s), т.е. наименьшее число, большее или равное n/s. Т.к. все классы одинаковы по размеру, то можно умножить количество элементов в одном классе на количество классов.
    4. Координаты не связаны - надо перемножить результат для x и для y.
    В итоге получается формула(ceil(n/s) == (n+s-1)/s == (n-1)/s+1):
    ((n-1)%s+1)*((n+s-1)/s)*((m-1)%s+1)*((m+s-1)/s)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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.
»
23 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I will write solutions for Problem E after I solve it.

Still thinking? :D