Задачи олимпиады "3й тур школьной олимпиады по Красноярскому краю"

Задача A. Время года

По заданному номеру месяца в году требуется определить время года.

Входные данные

Входной файл INPUT.TXT содержит натуральное число N (N≤100) – номер месяца.

Выходные данные

В выходной файл OUTPUT.TXT выведите для летних месяцев значение «Summer», для зимних – «Winter», для весенних – «Spring», для осенних – «Autumn». Если число не соответствует возможному значению месяца, то в этом случае следует вывести «Error».

Примеры

Задача B. Футбол

Вместо того чтобы делать уроки, Вася смотрел футбольный матч и записывал счет, который показывался на табло, после каждого забитого гола. Например, у него могла получиться такая запись: 1:0, 1:1, 1:2, 2:2, 2:3. После этого он сложил все записанные числа: 1+0+1+1+1+2+2+2+2+3=15.

По сумме, получившейся у Васи, определите, сколько всего мячей было забито в матче.

Входные данные

В первой строке входного файла INPUT.TXT записано одно целое неотрицательное число, не превосходящее 1000 – сумма, полученная Васей.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число – общее количество забитых мячей.

Пример

Задача C. Игра с пешкой

В левой нижней клетке шахматной доски размера N×N стоит пешка. Двое игроков по очереди двигают её, причём каждый может подвинуть её на одну клетку вверх или на одну клетку вправо. На диагонали доски написаны числа a₁, a₂, …, a_N. Когда пешка попадает на диагональ, игра кончается и выигрыш первого игрока равен значению числа, написанного в клетке с остановившейся пешкой. Напишите программу определения гарантированного выигрыша первого игрока.

Входные данные

В первой строке входного файла INPUT.TXT записано число N (1 ≤ N ≤ 100). Во второй строке записаны натуральные числа a₁, a₂, …, a_N (1 ≤ a_i ≤ 100).

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число – выигрыш первого игрока.

Пример

Задача D. Доказательство теоремы

Преподаватель читает курс лекций, в рамках которого обычно доказывается N различных теорем. Некоторые теоремы могут ссылаться в доказательстве друг на друга. Более точно, каждая теорема T_i зависит от некоторого набора из C_i других теорем; доказать ее можно лишь доказав не менее половины теорем из данного набора. При этом структура курса такова, что нет такой теоремы, от которой зависели бы две или более различных теоремы, а также нет цепочки теорем (T_i1,T_i2, . . . , T_is) такой, что T_i1 зависит от T_i2, T_i2 зависит от T_i3, …, T_is−1 зависит от T_is, а T_is – от T_i1.

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

Для простоты будем считать, что все теоремы доказываются за одинаковое время. Нужно доказать такое множество теорем и в таком порядке, чтобы основная теорема оказалась доказанной и чтобы общее время доказательства было минимально.

Входные данные

В первой строке входного файла INPUT.TXT записано число N (1 ≤ N ≤ 10 000) – количество теорем. Каждая из следующих N строк описывает теоремы, от которых зависит T_i−1, где i – номер этой строки во входном файле. Эти строки имеют вид A_i,1 A_i,2 ... A_i,Ci 0; здесь A_i,j – номер теоремы, от которой зависит T_i−1. Среди всех чисел A_i,j во входном файле нет двух одинаковых. Основная теорема имеет номер 1. Все числа во входном файле целые.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите K – минимальное количество теорем, которые потребуется доказать. В последующих K строках выведите номера этих теорем в порядке их доказательства, по одному числу в каждой. Если ответов с минимальным K несколько, можно вывести любой из них.

Примеры