В очередной раз вместо того, чтобы пойти погулять в хорошую погоду целый день писал контесты: сначала июльский ZOJ Monthly, на котором умудрился занять 11 место, решив 4 задачи, а затем с перерывом в 7 часов – Google Code Jam Round 1b. Браузеры всячески пытались помешать мне написать GCJ – сначала Opera не захотела заходить в контест после начала, потом Firefox не захотел скачивать hard-тест к 3-й задаче, включив, однако, счетчик времени. Но, преодолев их сопротивление и собственную невнимательность, сдал полностью все 3 задачи и в итоге занял 19-е место, что не может не радовать :) Интересен странный подход к подсчету шртафного времени – это время сдачи последнего сданного easy-теста. Это приводит к тому, что все пытаются как можно быстрее решить easy-тесты сомнительной сложности, и получается, что выше тот, кто быстрее печатает. Далее – небольшой обзор задач GCJ.

Задача A. Crop Triangles

В задаче требуется посчитать, сколько треугольников можно составить из заданного набора точек с целочисленными координатами так, что координаты центра тяжести каждого треугольника также целочисленные. Идея очевидная: нам нужны не сами координаты, а только остатки от деления их на 3, иными словами – нужно сжать все точки в квадрат 3 x 3. Далее – элементарная комбинаторика.

Задача B. Number Sets

Дан целочисленный интервал [A; B] (A, B < 10 ^ 12, B <= A + 10 ^ 6) и число P (2 <= P <= B). Изначально каждое число составляет отдельное множество из одного элемента. Рассмотрим все пары чисел: если найдется такая пара, что оба числа делятся на простое число, не меньшее P, то объединим множества, содержащие эти числа. Будем повторять эту операцию пока это возможно. Требуется посчитать, сколько множеств останется в итоге.

Наблюдение: если P > 0.5 B, то не существует двух таких чисел из интервала [A; B], что они оба делятся на P или что-либо большее. Из этого и из ограничений на размер интервала следует, что максимальное простое число, деление на которое нужно рассматривать, не больше 10 ^ 6. Далее элементарно: для каждого простого, не меньшего P и не большего B (и 10 ^ 6), объединим в одно множество все кратные ему числа из нашего интервала. Естественно желательно при этом использовать систему непересекающихся множеств с объединением по рангу и сжатием путей.

Задача C. Mousetrap

Имеется набор из N карт, пронумерованных от 1 до N (N <= 10^6). Проделываются следующие действия:

  1. счетчик = 0;
  2. ++счетчик;
  3. возьмем карту сверху колоды;
  4. если номер карты совпадает со значением счетчика, то выпишем ее номер, выкинем и, если остались карты, вернемся к шагу 1;
  5. если же номер карты не совпадает со значением счетчика, то положим ее под низ колоды и вернемся к шагу 2.

Нам нужно расставить карты так, чтобы в итоге была выписана последовательность 1, 2, 3, … N.

Решение для небольшого теста очевидно: поставить карту 1 на первое место, отсчитать 2 пустых места и поставить карту 2, отсчитать 3 пустых места и поставить 3 и т.д. Для большого теста можно делать то же самое, но не отсчитывая пустые места по одному, а прыгать сразу туда, куда надо. Этого можно добиться, храня свободные места, например, в дереве Фенвика для суммы и используя бинарный поиск.