База знаний гимназии 1 им. Барсукова

1. Потерянная страница

Выходя из школьного автобуса, Лиза не заметила, что Нельсон подставил ей подножку. Собрав разлетевшиеся при падении страницы своего доклада, Лиза их пересчитала и обнаружила, что одна из страниц пропала. Напишите программу, которая поможет Лизе определить номер потерянной страницы.

Первая строка ввода содержит одно целое число — количество страниц в докладе N (1 ≤ N ≤ 30000). Далее следует N−1 строка, каждая из которых содержит одно целое число от 1 до N – номера собранных страниц. Все номера страниц различны.

Вывести одно целое число – номер потерянной страницы.

2. Резервное копирование

Профессор Фринк хочет скопировать информацию о своих изобретениях из своего компьютера на CD. Для уменьшения количества дисков он придумал следующий алгоритм. На первом этапе файлы упорядочиваются в порядке уменьшения их размера (при совпадении размеров первым должен быть файл, указанный в списке копируемых файлов раньше). На втором этапе файлы записываются на диски. Для записи очередного файла выбирается диск с наименьшим номером среди тех используемых для копирования дисков, на который данный файл может поместиться. Если ни одного такого диска нет, к набору дисков добавляется новый диск, на который записывается файл.

Напишите программу, определяющую какие файлы на какой диск будут записаны при использовании этого алгоритма. При записи нужно учитывать, что файл должен занимать целое число кластеров и, если размер кластера равен C, файл размером от 1 до C байт занимает C байт на диске, файл размером от C+1 до 2·C занимает 2·C байт на диске и так далее.

Первая строка ввода содержит три целых числа - количество файлов N (1 ≤ N ≤ 1000), размер одного диска S (10³ ≤ S ≤ 10⁹) и размер кластера C (1 ≤ C ≤ S, S кратно C). Вторая строка ввода содержит N целых чисел в диапазоне от 1 до S – размеры файлов. В первой строке выведите одно целое число M – количество дисков, использованных для записи. Далее выведите M строк, в (i+1)-й строке выведите номера файлов, которые нужно записать на i-й диск, в порядке их записи.

3. Построения

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

Напишите программу, которая находит число различных построений для группы из N человек. В первой строке ввода содержится одно целое число N (1 ≤ N ≤ 10⁹).

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

4. ICQ

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

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

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

5. Морской бой

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

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

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