Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Положение] [Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

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

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

(Время: 1 сек. Память: 16 Мб Баллы: 100)

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
13Spring
215Error

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

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Вместо того чтобы делать уроки, Вася смотрел футбольный матч и записывал счет, который показывался на табло, после каждого забитого гола. Например, у него могла получиться такая запись: 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 выведите одно число – общее количество забитых мячей.

Пример

INPUT.TXTOUTPUT.TXT
1155

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

(Время: 1 сек. Память: 16 Мб Баллы: 100)

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

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

В первой строке входного файла INPUT.TXT записано число N (1 ≤ N ≤ 100). Во второй строке записаны натуральные числа a1, a2, …, aN (1 ≤ ai ≤ 100).

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

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

Пример

INPUT.TXTOUTPUT.TXT
18
3 1 4 1 5 9 2 6
5

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

(Время: 1 сек. Память: 16 Мб Баллы: 100)

Преподаватель читает курс лекций, в рамках которого обычно доказывается N различных теорем. Некоторые теоремы могут ссылаться в доказательстве друг на друга. Более точно, каждая теорема Ti зависит от некоторого набора из Ci других теорем; доказать ее можно лишь доказав не менее половины теорем из данного набора. При этом структура курса такова, что нет такой теоремы, от которой зависели бы две или более различных теоремы, а также нет цепочки теорем (Ti1,Ti2, . . . , Tis) такой, что Ti1 зависит от Ti2, Ti2 зависит от Ti3, …, Tis−1 зависит от Tis, а Tis – от Ti1.

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

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

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

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

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

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

Примеры

INPUT.TXTOUTPUT.TXT
12
2 0
0
2
2
1
26
2 3 6 0
4 0
0
0
0
5 0
4
4
3
2
1
33
0
1 0
2 0
1
1


Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru