Задача A. Дискретный логарифм ≡

Автор:А. Кленин, И. Лудов
Входной файл: input.txt   Ограничение времени:3 сек
Выходной файл: output.txt   Ограничение памяти:200 Мб

Условие

Даны целые положительные числа b, a1, a2, ..., aN. Требуется вычислить значения floor(logba1), …, floor(logbaN), где floor(x) — наибольшее целое, не превосходящее x.

Формат входного файла

Входной файл содержит числа N b a1 a2 ... aN по одному числу в строке.

Формат выходного файла

Выходной файл должен содержать N целых чисел — результат вычисления.

Ограничения

1 ≤ N ≤ 1000, 2 ≤ b ≤ 100, 1 ≤ ai < 101000 (т.е. числа содержат до 1000 цифр).

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1
2
1023
 
9

Задача B. Забор в парке ≡

Автор:И. Лудов, А. Кленин
Входной файл: input.txt   Ограничение времени:2 сек
Выходной файл: output.txt   Ограничение памяти:200 Мб

Условие

В бесконечном квадратном парке деревья образуют квадратную решётку с шагом 1 метр. Часть парка было решено оградить забором, который представляет собой многоугольник с заданными координатами вершин. Деревья, которые в точности попадают на вершины или стороны многоугольника, придётся срубить. Необходимо выяснить количество таких деревьев.

Программа должна, получив на входе число вершин многоугольника N и их целочисленные координаты (x1, y1), …, (xN, yN), определить количество точек с целочисленными координатами, лежащих на границе этого многоугольника.

Стороны многоугольника не самопересекаются.

Формат входного файла

Входной файл содержит число N, за которым следует N пар координат x1 y1 … xN yN

Формат выходного файла

Выходной файл должен содержать единственное число — количество точек.

Ограничения

3 ≤ N ≤ 1000, 0 ≤ xi, yi ≤ 107, исходные данные таковы, что результат не превосходит 231−1.

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3
0 0 2 0 0 2

6
0.021s 0.004s 9