Материалы к школьному этапу
Всероссийской олимпиады школьников по информатике
Рекомендуемое количество задач в варианте – 3-4.
Рекомендуемая продолжительность тура — 2 часа.
Решением каждой из предложенных задач должна являться работающая программа. Предполагается, что входные данные во всех задачах корректны, и полностью соответствуют приведенным в условии ограничениям – дополнительно проверять это не нужно.
Проверка решений осуществляется путем запуска программы, ввода тестовых данных и проверки выданных программой ответов. Тесты приведены в конце данного файла (после условий задач). Во всех задачах ответ всегда определен однозначно, т. е. для проверки правильности ответа его достаточно сравнить с приведенным.
В каждой задаче приведено 10 тестов. Каждый тест оценивается одним баллом.
Баллы за задачу получаются суммированием баллов за пройденные тесты.
1 Задача «Сверхпростые числа»
Простым числом называется натуральное число, большее единицы и делящееся только на единицу и на само себя. Выпишем все простые числа в порядке возрастания и пронумеруем их. Первым простым числом будет 2, вторым – 3, третьим – 5 и так далее.
Будем называть сверхпростыми простые числа, имеющие номера, также являющиеся простыми числами.
Напишите программу, которая по введенному числу K будет находить K-ое по величине сверхпростое число.
Формат ввода
Вводится одно натуральное число K (1 ≤ K ≤ 500)
Формат вывода
Выведите одно число – K-ое по величине сверхпростое число.
Примеры
Пример ввода | Пример вывода |
1 | 3 |
2 | 5 |
3 | 11 |
100 | 3911 |
2 Задача «Кока-кола»
Одна баночка кока-колы стоит B рублей. Пустую баночку из-под кока-колы можно сдать и получить за нее E рублей.
У Васи есть R рублей. Он покупает кока-колу, выпивает ее, сдает баночку, снова покупает кока-колу и так далее до тех пор, пока имеющихся у него денег (после сдачи очередной баночки) хватает на покупку кока-колы.
Сколько всего банок кока-колы он выпьет?
Формат ввода
Вводится три натуральных числа B, E, R (1 ≤ E < B ≤ 30000, 1 ≤ R ≤ 30000).
Формат вывода
Выведите одно число – количество баночек, которое сможет выпить Вася.
Примеры
Пример ввода | Пример вывода |
2 1 3 | 2 |
3 1 13 | 6 |
2 1 1 | 0 |
3 Задача «Манхэттенские улицы»
Система улиц Нью-Йоркского района Манхэттен весьма интересна. В Манхеттене есть N улиц, идущие с Севера на Юг (авеню), и M улиц, идущие с Запада на Восток (улицы). Ширина каждого авеню и каждой улицы равна D метров, а длина — L метров. При этом каждая улица пересекает каждый авеню и не имеет общих точек с другими улицами, а каждый авеню пересекает каждую улицу и не имеет общих точек с другими авеню.
Разумеется, все авеню и все улицы имеют асфальтовое покрытие. На перекрестках, естественно, асфальт уложен в один слой. Дорожно-ремонтные службы интересуются, сколько квадратных метров асфальта уложено на все авеню и улицы. Напишите программу, отвечающую на этот вопрос.
Формат ввода
Вводится четыре натуральных числа N, M, D, L.
1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000, 1 ≤ D ≤ 100, 1 ≤ L ≤ 10000, L > MD, L > ND.
Формат вывода
Выведите одно число – ответ на задачу.
Примеры
Пример ввода | Пример вывода |
75 | |
4 Задача «Проверка часов»
На часах отображаются часы и минуты с помощью четырех элементов, каждый из которых отображает одну цифру
Три из них состоят из семи полосок, каждая из которых может быть либо белой (неотличимой от фона), либо черной. Вид такого элемента и способ отображения цифр показаны на рисунке:
Четвертый элемент предназначен для отображения старшей цифры часа. Если она равна нулю, то элемент полностью неактивен (все полоски белые), иначе показывается соответствующая цифра. Вот как выглядит элемент и отображаемые им цифры:
Вася решил проверить – все ли в порядке с часами, а именно, нет ли таких полосок в каком-либо из элементов, которые либо всегда белые, либо всегда черные. Вася подошел к часам в некоторый момент времени, и стал внимательно за ними наблюдать. Напишите программу, которая определит, сколько минут Вася должен наблюдать за часами, чтобы убедиться, что в них все элементы работают верно.
Формат ввода
Вводится время, когда Вася подошел к часам в формате HH:MM, то есть сначала записан час, затем идет двоеточие, а после него минута. И часы, и минуты записаны с лидирующими нулями, если таковые имеются. 00 ≤ HH ≤ 23, 00 ≤ MM ≤ 59.
Формат вывода
Выведите время в минутах, которое Вася должен наблюдать за часами.
Примеры
Пример ввода | Пример вывода |
00:00 | 1200 |
02:39 | 1041 |
5 Задача «Последовательности»
Семен изобрел новый способ сжатия данных. Правда, он пока умеет сжимать только последовательность из N единиц. Метод сжатия основывается на представлении последовательности из N единиц в виде последовательности чисел от 1 до A так, чтобы суммы членов обеих последовательностей совпадали (т. е. были равны N). Например, последовательность 1,1,1,1,1 при A=3 может быть преобразована в последовательность 1,2,1,1 или 2,3 или другие последовательности.
Ваша задача – посчитать количество способов сжать заданную последовательность придуманным методом.
Формат ввода
Вводятся два числа N и A (1 ≤ A ≤ N ≤ 30).
Формат вывода
Выведите одно число – ответ задачи.
Примеры
Пример ввода | Пример вывода |
2 1 | 1 |
4 2 | 5 |
Комментарий
Последовательности, получающиеся при сжатии последовательности 1,1,1,1 и A=2:
1,1,1,1
1,1,2
1,2,1
2,1,1
2,2
Тестовые данные для проверки решений задач олимпиады
Задача «Сверхпростые числа»
№ теста | Входные данные | Ответ |
1 | 4 | 17 |
2 | 5 | 31 |
3 | 7 | 59 |
4 | 11 | 127 |
5 | 15 | 211 |
6 | 50 | 1447 |
7 | 123 | 5059 |
8 | 239 | 12547 |
9 | 400 | 24781 |
10 | 500 | 33347 |
Задача «Кока-кола»
№ теста | Входные данные | Ответ |
1 | 10 5 10 | 1 |
2 | 10 5 20 | 3 |
3 | 10 5 22 | 3 |
4 | 5 2 57 | 18 |
5 | 1 | |
6 | 50 | 6 |
7 | 50 | 5 |
8 | 1 | 3333 |
9 | 15 | 15001 |
10 | 13944 |
Задача «Манхэттенские улицы»
№ теста | Входные данные | Ответ |
1 | 8 | |
2 | 54 | |
3 | 72 | |
4 | 591 | |
5 | 444 | |
6 | 1260 | |
7 | 1 1 | 1990000 |
8 | 15 | 6169395 |
9 | 25 11 | |
10 | 1 |
Задача «Проверка часов»
№ теста | Входные данные | Ответ |
1 | 00:31 | 1169 |
2 | 08:23 | 697 |
3 | 11:09 | 771 |
4 | 13:00 | 660 |
5 | 13:44 | 616 |
6 | 16:59 | 421 |
7 | 19:59 | 541 |
8 | 20:00 | 840 |
9 | 20:01 | 839 |
10 | 23:59 | 601 |
Задача «Последовательности»
№ теста | Входные данные | Ответ |
1 | 1 1 | 1 |
2 | 12 9 | 2040 |
3 | 5 3 | 13 |
4 | 5 4 | 15 |
5 | 4 3 | 7 |
6 | 15 7 | 15808 |
7 | 25 1 | 1 |
8 | 20 10 | 521472 |
9 | 26 23 | |
10 | 30 30 |
