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.
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.
Спасибо большое.
- Чтобы из одной клетки добраться до другой, разность по x и по y должна делиться на s - то есть условно можно разбить все клетки на классы по достижимости. Это будет соответствовать взятию по модулю s для каждой из координат. x-y=0(mod x) => x=y(mod x)
- Теперь надо найти количество остатков по модулю s, у которых больше класс(т.е. больше клеток, в которые можно придти). Утверждается, что это n%s, если n не делится на s или n иначе. Другими словами это (n-1)%s+1. Для m всё аналогично.
- Однако надо посчитать не количество классов, а количество элементов в лучших классах. В одном классе будет ceil(n/s), т.е. наименьшее число, большее или равное n/s. Т.к. все классы одинаковы по размеру, то можно умножить количество элементов в одном классе на количество классов.
- Координаты не связаны - надо перемножить результат для x и для y.
В итоге получается формула(ceil(n/s) == (n+s-1)/s == (n-1)/s+1):I will write solutions for Problem E after I solve it.Still thinking? :D