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

Это старая версия документа.

---

1. Формула

При просмотре телепередачи «Форт Байан» Петя заметил, что ведущий делает какие-то вычисления, перед тем как открыть дверь и пустить участников игры на очередное испытание. Петя заметил в блокноте ведущего формулу и понял, что кодом для замка на двери комнаты N является результат вычислений по этой формуле. Напишите программу, которая поможет Пете рассчитать значение указанной формулы для различных N. Первая строка ввода содержит одно целое число N (1 ≤ N ≤ 100). Вывести одно вещественное число с точностью не менее 10⁻⁵ – результат вычислений.

2. Бинго

Во дворе форта Байан проходят соревнования по игре в «бинго». Игра проходит на поле размером 5×5 клеток, каждые 5 секунд компьютер случайно выбирает одну из пустых клеток и подсвечивает ее, тогда один из игроков команды должен встать на эту клетку или положить в нее пушечное ядро. Если команда не успевает выполнить ход за отведенное время, то ход пропускается. Если ряд из 5 клеток по горизонтали или по вертикали будет полностью заполнен, команда кричит «бинго» и клетки этого ряда освобождаются от игроков и ядер. Может получиться так, что ядро (или игрок) ставится на пересечении двух рядов, в каждом из которых было по 4 заполненных клетки, таким образом два ряда (по вертикали и по горизонтали) будут заполнены одновременно, в этом случае команда кричит «бинго» дважды, и оба этих ряда освобождаются от игроков и ядер.

Напишите программу, определяющую, сколько раз за время игры команда сможет сказать «бинго», если успеет выполнить все ходы.

Первая строка ввода содержит одно целое число N (5 ≤ N ≤ 100) – количество ходов. Далее следует N строк, содержащих по два целых числа от 1 до 5 – номер строки и номер столбца подсвечиваемой клетки. Подсвечиваются только пустые к этому моменту клетки.

Вывести одно целое число – сколько раз у команды получится «бинго».

3. Разбитая клавиатура

Перед тем как покинуть аварийный корабль, Максим захотел отправить несколько SMS своим друзьям и родственникам, но обнаружил, что некоторые клавиши на клавиатуре галактического передатчика перестали работать. Тогда он решил, что отправит только те сообщения, которые можно ввести с помощью оставшихся клавиш. Напишите программу, которая поможет Максиму определить, какие сообщения можно отправить с помощью оставшихся на клавиатуре клавиш, а какие – нет.

Первая строка ввода содержит непустой набор из прописных латинских букв – неработающие клавиши. Вторая строка содержит одно целое число N (1 ≤ N ≤ 100) – количество сообщений, которые хочет отправить Максим. Далее следует N непустых строк длиной не более 100 символов, содержащих только латинские буквы, пробелы и знаки препинания – отправляемые сообщения.

Вывести N строк. Если i-е сообщение можно отправить с помощью оставшихся клавиш, то вывести в i-й строке yes, иначе – no.

4. Замощение прямоугольника

Ограничения: время – 250ms, память – 32MiB

Необходимо с помощью плиток размером 1×2 замостить прямоугольник размером 4xN. Например, прямоугольник 4×2 может быть замощен 5 разными способами.

Напишите программу, которая считает число способов замощения прямоугольника 4xN.

Ввод содержит одно целое число N (1 ≤ N < 20).

Вывести одно целое число – число способов замощения. Гарантируется, что результат для N в указанном диапазоне не будет превышать 2³¹.

5. Саванна

Чарльз Ф. Мантц изучает животный мир саванн. Ни в одном уголке Земли нет такого изобилия крупных животных, к ак в африканских саваннах. Бесчисленные стада антилоп, зебр, буйволов, слонов, жирафов кочуют на просторах саванн, переходя с одного пастбища на другое или в поисках водопоев. У исследователя есть спутниковые снимки участка саванны и он хочет определить количество кочующих по нему стад животных.

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

В первой строке ввода содержится два целых числа, разделенных пробелом – количество животных N (1 ≤ N ≤ 1000) и расстояние D (1 ≤ D ≤ 100). Далее следует N строк, в каждой строке содержатся два целых числа Xi, Yi (0 ≤ Xi, Yi ≤ 1000) – координаты i-го животного.

Вывести одно целое число – количество стад.