Задачи муниципального этапа олимпиады школьников по информатике 2008

Иван Петрович преподает в школе №100 физкультуру, но интересуется также математикой, в основном, с практической точки зрения. Например, его интересует вопрос, сколько различных построений существует для группы из `N` человек. Иван Петрович выяснил, что если `N` – простое число, то получается только 2 построения: в колонну по одному (`1\ times\ N`) и в шеренгу (`N\ times\ 1`). Эти тривиальные построения возможны для любого `N\ >\ 1` (для `N\ =\ 1` существует только одно построение `1\ times\ 1`, которое не является ни шеренгой, ни колонной). Если `N` – составное число, то существует и другие нетривиальные построения. Для 100 человек существует девять построений: `1\ times\ 100`, `2\ times\ 50`, `4\ times\ 25`, `5\ times\ 20`, `10\ times\ 10`, `20\ times\ 5`, `25\ times\ 4`, `50\ times\ 2` и `100\ times\ 1`.

Напишите программу, которая находит число различных построений для группы из `N` человек.

В первой строке ввода содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 10^9`).

Вывести одно целое число – количество различных построений для группы из `N` человек.

100

9

В школе №100 у каждого школьника есть свой личный номер ICQ. В школе распространено мнение, что чем меньше значение номера ICQ, тем более продвинутым является школьник. Известен список всех школьников с номерами ICQ. Требуется вывести список `K` самых продвинутых школьников.

В первой строке ввода содержится количество учеников в школе `N` (`1\ ≤\ N\ ≤\ 100`) и число `K` (`1\ ≤\ K\ ≤\ N`). Далее следует `N` строк, в каждой строке содержится фамилия школьника (без пробелов, содержит не более 20 строчных латинских букв) и через пробел номер `"ICQ"` (`1\ ≤\ "ICQ"\ ≤\ 10^9`). Номера ICQ и фамилии у школьников различны.

Вывести фамилии `K` самых продвинутых школьников в лексикографическом порядке (по алфавиту). Каждая фамилия выводится на отдельной строке.

3 2
ivanov 170
semenova 320
antonov 201

antonov
ivanov

В школе № 100 школьники любят играть в "морской бой". Каждый из игроков на доске 10x10 расставляет один корабль из 4 клеток, 2 корабля из 3 клеток, 3 корабля из 2 клеток и 4 корабля из одной клетки таким образом, чтобы они не соприкасались даже углами. Затем один из игроков "стреляет", называя номер одной из клеток. Если "выстрел" не попадает ни по одному из кораблей, то результатом "выстрела" является "промах". Если "выстрел" попадает в один из кораблей, но у этого корабля остаются части, в которые не попал ни один выстрел, то результат "выстрела" – повреждение корабля, если все части корабля повреждены, то результат – уничтожение корабля.

Для проведения чемпионата школы по игре в "морской бой" разрабатывается сервер, на который игроки загружают расположения своих кораблей и затем отправляют "выстрелы" по кораблям противника. Требуются написать один из ключевых модулей этого сервера – программу, которая вычисляет результаты "выстрелов".

В первой строке ввода содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество "выстрелов". Далее следует 10 строк по 10 символов – расположение кораблей противника. Пустая клетка обозначается символом '.', а клетка с частью корабля – символом '#'. Далее следует `N` строк, в каждой строке – номер клетки, по которой игрок сделал выстрел. Клетки доски пронумерованы целыми числами слева направо и сверху вниз от 1 до 100 (см.рис.).

Вывести `N` строк с результатами "выстрелов". В `i`-й строке должен быть результат `i`-го "выстрела". В случае промаха вывести сообщение "missed", повреждения корабля – "damaged", уничтожения корабля – "sinked", повторного "выстрела" по клетке – "repeated".

3
..####.###
#.........
#.#.......
..#....#..
..#.......
........#.
##...##...
..........
.......#..
...#......
1
11
21

missed
damaged
sinked

Экскурсии под руководством Ивана Петровича проходят всегда очень организованно. Ивану Петровичу особенно нравятся построения в форме квадрата, так как если какой-то школьник отстанет от группы, его отсутствие в квадрате является более заметным, чем при использовании построения в форме шеренги и колонны по одному. Поэтому школьники разбиваются на несколько групп, для которых возможно построение в форме квадрата. Чтобы разные группы были хорошо различимы визуально, требуется, чтобы в разных группах было разное число школьников. Из 100 школьников можно сделать одну группу `10\ times\ 10`, или две группы `6\ times\ 6` и `8\ times\ 8`, но лучше с точки зрения Ивана Петровича сделать 5 групп `1\ times\ 1`, `3\ times\ 3`, `4\ times\ 4`, `5\ times\ 5` и `7\ times\ 7`.

Напишите программу, которая находит разбиение `N` школьников на группы в форме квадратов, среди которых нет двух одинаковых по количеству. Количество групп в разбиении должно быть как можно больше.

В первой строке ввода содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 10^5`) – число школьников, отправляющихся на экскурсию.

Если разбиение найдено, то вывести в первой строке количество групп в разбиении, а во второй строке – в порядке возрастания размеры стороны квадратных групп. Если существует несколько разбиений с максимальным количеством групп, то можно вывести одно из них (любое). Если разбиения не существует, в первой строке вывести 0.

100

5
1 3 4 5 7