Задачи олимпиады "Школьный этап ВОШ Красноярского края по информатике, 9-11 классы"
Задача A. Настольный теннис
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Андрей хочет купить ракетки и шарики для игры в настольный теннис. Один комплект ракеток стоит A рублей, один шарик стоит B рублей. У Андрея есть C рублей. Он покупает один комплект ракеток и шарики на оставшиеся деньги. Сколько шариков купит Андрей?
Входные данные
Входной файл INPUT.TXT содержит натуральные числа A, B и С, не превосходящие 1000. Каждое число записано в отдельной строке. Гарантируется, что A ≤ C.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число - ответ на задачу.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
20 10 50
3
Задача B. Время суток
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Нам известно условное деление суток на четыре части: утро, день, вечер и ночь. Деление условно потому, что здесь нет четких границ. Например, кто-то считает время 15:30 уже вечерним, а кто-то думает, что это еще день. Более того, многие из нас могут относить одно и то же время к разным временным промежуткам. Например, мы практически все говорим "три часа тридцать минут ночи" и в тоже время можем сказать, что это "полчетвертого утра". Во многих европейских странах считают, что ночь - это промежуток от полуночи до 6 утра, далее идет утро до полудня, а затем день до 6 вечера, а после уже вечер до полуночи. А вот англоязычная часть населения утром считает время от полуночи до полудня, то есть для них считается нормой поприветствовать кого-либо в полвторого часа ночи фразой "Good morning!", что в буквальном переводе с английского означает "Доброе утро!".
В этой задаче определим четкие границы для времен суток, которые приблизим к типичному представлению о них для русскоязычного населения. Будем считать, что утро начинается c 04:30 и заканчивается в 11:30, далее идет день до 15:30, а потом вечер до 23:30, остальное время - это ночь. Заметим, что 11:30 - это уже день, так же как 15:30 - вечер, а 23:30 - ночь.
Напишите программу, которая по указанному времени, заданному в часах и минутах, определит время суток.
Входные данные
Входной файл INPUT.TXT содержит время в формате ЧЧ:ММ. Часы определены в диапазоне от 0 до 23, а минуты - от 0 до 59.
Выходные данные
В выходной файл OUTPUT.TXT выведите англоязычный аналог названия времени суток согласно заданному во входных данных времени (morning - утро, day - день, evening - вечер и night - ночь).
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
07:15
morning
2
12:00
day
3
20:17
evening
4
02:30
night
Задача C. Прямоугольник
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Катя нарисовала на клетчатой бумаге прямоугольник по линиям сетки. После этого она подсчитала количество узлов сетки, оказавшихся строго внутри прямоугольника и количество единичных отрезков сетки строго внутри прямоугольника и сообщила эти два числа Маше.
Напишите программу, которая поможет Маше определить длины сторон прямоугольника.
Входные данные
Во входном файле INPUT.TXT записаны два целых неотрицательных числа K и L – количество узлов и единичных отрезков сетки соответственно. Оба числа не превосходят 109.
Выходные данные
В выходной файл OUTPUT.TXT выведите два натуральных числа – длины сторон прямоугольника в любом порядке. Если ответов несколько, выведите любой из них. Гарантируется, что ответ всегда существует.
Примеры
№
INPUT.TXT
OUTPUT.TXT
Пояснение
1
2 7
2 3
2
1 4
2 2
Система оценки
Решения, работающие только для K,L ≤ 103, будут оцениваться в 50 баллов.
Решения, работающие только для K,L ≤ 106, будут оцениваться в 75 баллов.
Задача D. Скачки
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Всем известны конные скачки, в которых принимают участие несколько лошадей, ведомых жокеями. Безудержный азарт, рискованные ставки, нарядные дамы и джентльмены – это то, что часто связывают с данным мероприятием. Но здесь мы рассмотрим особый тип тотализатора для болельщиков.
Перед началом соревнований болельщикам предложили сделать по две ставки на результаты забега. Каждая ставка должна иметь вид «Лошадь A придет к финишу раньше, чем лошадь B». Организаторы решили выяснить, могут ли лошади прийти в таком порядке, что у каждого болельщика сыграет ровно одна ставка из двух: то есть одна из ставок сыграет (окажется верной), а другая – не сыграет (будет неверна). Будем считать, что современный фотофиниш гарантирует то, что никакие две лошади не могут оказаться одновременно на финише.
Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа K и N – количество лошадей и количество болельщиков соответственно (K ≤ 10, N ≤ 100). Все лошади пронумерованы от 1 до K. Каждая из следующих N строк описывает ставку очередного болельщика: содержит 4 натуральных числа A, B, C и D, не превосходящих K, разделенных пробелами, и соответствует ставкам «Лошадь A придет к финишу раньше, чем лошадь B» и «Лошадь C придет к финишу раньше, чем лошадь D».
Выходные данные
В выходной файл OUTPUT.TXT выведите такую одну из возможных последовательностей прихода лошадей на финиш, что у каждого из болельщиков сыграет ровно одна ставка (сначала нужно вывести номер лошади, пришедшей на финиш первой, затем номер лошади, пришедшей на финиш второй и так далее).
Если решения не существует, то следует вывести единственное число 0.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3 2 1 2 3 2 2 1 2 3
1 2 3
2
3 4 1 2 2 3 1 2 3 2 1 2 1 3 1 2 3 1
0
Система оценки
Решения, работающие только при K=3, будут оцениваться в 25 баллов.
Задача E. Школа побитового ИЛИ
(Время: 3 сек. Память: 128 Мб Баллы: 100)
Это были самые сложные два часа за всю учебную историю Георга: он сдавал зачёт по побитовым мемам. Эта дисциплина относится к разделу информатики, который более тщательно изучается в Школе Побитового ИЛИ (ШПИЛИ), поэтому учителя стараются не занижать планку требуемых знаний от года к году и не прощать ученикам даже самые маленькие ошибки, допущенные на зачёте.
ШПИЛИ знаменита тем, что возле её выхода установлена огромная квадратная таблица побитового ИЛИ размера 2n×2n. Клетка таблицы, расположенная на пересечении строки r (0 ≤ r < 2n) и столбца c (0 ≤ c < 2n) содержит результат применения операции побитового ИЛИ к числам r и c. Разумеется, каждый ученик третьего класса и выше в ШПИЛИ обязан знать таблицу побитового ИЛИ наизусть.
Неподалеку от выхода из школы, Георг неожиданно остановился: он совсем забыл, что чтобы выйти, нужно ответить охраннику на
q вопросов, причем ответ на i-й вопрос - это ki-е по величине число, записанное в таблице побитового ИЛИ. Он так устал, что не в состоянии решить эту задачу. Помогите ему!
Входные данные
В первой строке входного файла INPUT.TXT записаны два целых числа n и q такие, что число 2n равно числу строк и столбцов квадратной матрицы побитового ИЛИ, а q равно числу вопросов, которые задаст охранник на выходе (0 ≤ n ≤ 30,1 ≤ q ≤ 218).
В следующей строке через пробел записаны q целых чисел ki - сами вопросы охранника (1 ≤ ki ≤ 4n,1 ≤ i ≤ q).
Выходные данные
В выходной файл OUTPUT.TXT выведите q ответов на вопросы охранника (через пробел) в том порядке, в котором они даны во входных данных.
Примеры
№
INPUT.TXT
OUTPUT.TXT
Матрица побитового ИЛИ
1
0 1 1
0
2
1 4 4 1 2 3
1 0 1 1
3
2 16 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
3 0 1 1 1 2 2 2 3 3 3 3 3 3 3 3
Система оценки
Решения, работающие только для n < 10, будут оцениваться в 20 баллов.
Решения, работающие только для n < 20, будут оцениваться в 40 баллов.
