Школьная олимпиада по информатике 2009 г.
8-9 класс
Задача 1. Спасение принцессы
Максимальное время работы на одном тесте: | 1 секунда |
Максимальная оценка: | 20 баллов |
В тридевятом царстве злой Дракон похитил принцессу и заточил ее в замке. Иван-царевич решил спасти принцессу. Чтобы добраться до принцессы, Ивану надо пройти десять комнат. В некоторых комнатах двери закрыты. Открыть их можно только с помощью волшебного ключа, который хранит Баба Яга.
Баба Яга согласилась дать Ивану-царевичу волшебный ключ только при одном условии – если он правильно угадает, сколько дверей закрыто в замке. Она называет одно число. Закрытых дверей в замке ровно столько, сколько единиц в двоичной записи этого числа.
Помогите Ивану-царевичу спасти принцессу. Найдите ответ на загадку Бабы Яги.
Входные данные
Во входном файле записано натуральное десятичное число N (1 ≤ N ≤ 1000).
Выходные данные
В выходной файл выведите одно число – количество единиц в двоичной записи числа N.
Примеры
вход (input.txt) | выход (output.txt) |
5 | 2 |
7 | 3 |
Задача 2. Карандаши
Максимальное время работы на одном тесте: | 1 секунда |
Максимальная оценка: | 20 баллов |
В трех коробках лежат карандаши. Учитель попросил Петю переложить часть карандашей так, чтобы в коробках карандашей стало поровну. Помогите Пете выполнить задание и напишите программу, которая будет определять, какое наименьшее количество карандашей требуется переложить.
Входные данные
Во входном файле записано три натуральных числа, не превосходящих 100 – количества карандашей в первой, второй и третьей коробках соответственно.
Выходные данные
В выходной файл выведите одно число – наименьшее количество карандашей, которое требуется переложить. Если это невозможно, выведите слово IMPOSSIBLE (заглавными буквами).
Примеры
вход (input.txt) | выход (output.txt) |
1 2 3 | 1 |
99 | IMPOSSIBLE |
Задача 3. Клавиатура
Максимальное время работы на одном тесте: | 1 секунда |
Максимальная оценка: | 20 баллов |
Набирая текст на клавиатуре компьютера, Петя заметил, что некоторые клавиши используются чаще, чем другие. Напишите программу, которая помогла бы Пете определить, какую клавишу придется нажимать чаще всего.
Входные данные
Во входном файле содержится строка символов, которая состоит только из строчных (маленьких) букв латинского алфавита и имеет ненулевую длину, не превосходящую 100.
Выходные данные
В выходной файл выведите символ, который придется нажимать чаще всего, и, через пробел, целое число – количество нажатий клавиши с этим символом. Гарантируется, что в данной строке такой символ только один.
Пример
вход | выход (output.txt) |
ababac | a 3 |
Задача 4. Робот
Максимальное время работы на одном тесте: | 1 секунда |
Максимальная оценка: | 20 баллов |
На доске в клетку размером N×N расставлено K пронумерованных деталей. Робот, который собирает эти детали, выходит из клетки с координатами (1,1) и должен собрать все детали в порядке возрастания их номеров.
Из клетки с координатами (x,y) робот может переместиться только в одну из четырех соседних, т. е. в одну из клеток с координатами (x+1,y), (x-1,y), (x,y+1) или (x,y-1), конечно с соблюдением условия, что он не должен выходить за границы доски.
Напишите программу, которая определит, какое минимальное количество ходов нужно сделать, чтобы собрать все детали.
Если робот проходит через клетку, где содержится деталь с большим номером, чем он сейчас должен взять, то ничего не происходит (он просто проходит, а деталь остается стоять).
Входные данные
В первой строке входного файла записаны два натуральных числа N и K, разделенные пробелом
(1 ≤ N, K ≤ 100). В последующих K строках записано K пар натуральных чисел (разделенных пробелом) – координаты x и y соответствующих деталей, то есть сначала для первой детали, затем для второй детали и т. д.
Выходные данные
В выходной файл выведите одно число – минимальное количество шагов, которое потребуется для сбора всех деталей в порядке возрастания их номеров.
Примеры
вход(input.txt) | выход (output.txt) |
4 3 3 3 1 4 2 1 | 11 |
Задача 5. Игра с карточками
Максимальное время работы на одном тесте: | 1 секунда |
Максимальная оценка: | 20 баллов |
Петя придумал новую игру. На столе в ряд раскладываются карточки с целыми числами. Петя решил, что из полученного ряда можно убрать карточку, если на двух соседних с ней карточках (справа и слева) записаны числа строго большие. Игра продолжается до тех пор, пока на столе не останется карточек, которые можно убрать.
Напишите программу, которая поможет Пете узнать, какой ряд карточек останется на столе в конце игры.
Входные данные
Первая строка входного файла содержит целое число N (1 ≤ N ≤ 100) – количество карточек с числами, расположенных в ряд. Следующая строка содержит N разделенных пробелом целых чисел ai
(– 100 ≤ ai ≤ 100) – записанные на карточках числа.
Выходные данные
В первой строке выходного файла выведите целое число K – количество оставшихся карточек. На следующей строке выведите через пробел числа на оставшихся карточках.
Примеры
вход(input.txt) | выход (output.txt) |
12 | 8 |
