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

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

HotLog


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

Задачи олимпиады "Полуфинал XIV Всероссийской командной олимпиады школьников по программированию (Восточно-Сибирский регион)"

Задача A. Семья

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

Известно, что отец старше сына на N лет, а сын моложе отца в M раз. Определите, сколько лет отцу и сколько лет сыну.

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

Входной файл INPUT.TXT содержит два натуральных числа N и M, разделенных пробелом (1 ≤ N, M ≤ 104). Входные данные таковы, что возраст отца и возраст сына являются целыми числами.

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

В выходной файл OUTPUT.TXT выведите два числа, разделенные пробелом: возраст отца и возраст сына.

Примеры

INPUT.TXTOUTPUT.TXT
11 22 1
220 525 5

Задача B. Паркет - 2

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

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

Напоминание: правильный многоугольник – это выпуклый многоугольник, у которого все стороны равны между собой и все углы равны между собой.

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

Входной файл INPUT.TXT содержит целое число N – количество вершин в правильном многоугольнике (3 ≤ N ≤ 1000).

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

В выходной файл OUTPUT.TXT выведите «YES», если плоскость можно замостить и «NO» в противном случае.

Примеры

INPUT.TXTOUTPUT.TXT
14YES
25NO

Задача C. Обмен

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

Как вы знаете, самый известный коллекционер фантиков в мире – это смешарик по имени Ежик. Но просто коллекционировать фантики ему не интересно, главное здесь – это обмен. Для обмена фантиками со своими друзьями Ежик придумал следующий способ: был составлен список, кто из смешариков кому отдает свои фантики. Каждый смешарик отдавал свои фантики только одному конкретному смешарику и получал фантики тоже только от одного конкретного смешарика. По правилам Ежика, фантики можно получать от того же смешарика, которому они отдаются.

Помогите Ежику подсчитать, сколько существует различных вариантов составления этого списка для N смешариков. В обмене всегда участвуют все смешарики.

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

Входной файл INPUT.TXT содержит целое число N – количество смешариков, задействованных в обмене (2 ≤ N ≤ 105).

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

В выходной файл OUTPUT.TXT выведите количество вариантов обмена фантиками по модулю 109+9.

Примеры

INPUT.TXTOUTPUT.TXT
121
232
349

Задача D. Апельсины - 2

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

На склад привезли коробку свежих апельсинов. Известно, что при поступлении апельсины весили ровно N грамм, а их влажность была F%. При хранении на складе апельсины могут либо вбирать в себя влагу из окружающего воздуха, либо терять влагу, если в помещении жарко и сухо. На складе решили апельсины ежедневно взвешивать и записывать изменения их массы в журнал: на сколько уменьшилась или увеличилась их масса по сравнению с предыдущим днем из-за поглощения влаги из воздуха или, наоборот, усыхания. Через M дней выяснилось, что апельсины необходимо перевезти на другой склад. Для этого нужно указать их текущий вес и влажность (в процентах).

Напомним, что влажность – это количество воды в веществе (в процентах) от первоначальной массы вещества.

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

Первая строка входного файла INPUT.TXT содержит три целых числа, разделенных пробелом: N – вес апельсинов (1 ≤ N ≤ 109), F – влажность апельсинов в процентах (1 ≤ F ≤ 99), M – количество дней (0 ≤ M ≤ 100). Далее идет M строк, в каждой из которых указано целое число K (|K| ≤ 107) – на сколько грамм изменился вес апельсинов по сравнению с предыдущим днем (со знаком «+», если он увеличился и со знаком «-», если уменьшился).

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

В выходной файл OUTPUT.TXT выведите два целых числа через пробел: вес в граммах и влажность апельсинов в процентах через M дней. Влажность следует округлить до целого числа.

Примеры

INPUT.TXTOUTPUT.TXT
15000 99 2
+1500
-4000
2500 98
281 20 1
+15
96 33
310 67 1
+10
20 84
41000000000 23 1
+10000000
1010000000 24

Задача E. Ученики

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

Однажды, неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам, а внутри класса по фамилиям.

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

Первая строка входного файла INPUT.TXT содержит натуральное число N – количество учеников (N ≤ 100). Далее, для каждого ученика определены 4 строки, содержащие фамилию, имя, класс и дату рождения соответственно. Фамилия и имя – строки, не превышающие 20 символов латинского алфавита: первая буква заглавная, остальные – строчные. Класс – строка, состоящая из числа (от 1 до 11) и заглавной латинской буквы (от «A» до «Z»). Дата рождения – строка в формате «ДД.ММ.ГГ». Гарантируется, что внутри одного класса нет однофамильцев.

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

В выходной файл OUTPUT.TXT выведите список учеников, отсортированный сначала по классам (классы сравниваются по номеру, а потом по букве), а потом по фамилии. Данные об ученике выводятся в отдельной строке: класс, фамилия, имя и дата рождения через пробел.

Пример

INPUT.TXTOUTPUT.TXT
13
Sidorov
Sidor
9A
20.07.93
Petrov
Petr
10B
23.10.92
Ivanov
Ivan
9A
10.04.93
9A Ivanov Ivan 10.04.93
9A Sidorov Sidor 20.07.93
10B Petrov Petr 23.10.92

Задача F. Функция - 3

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

Найдите все корни уравнения:

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

Входной файл INPUT.TXT содержит одно вещественное число C, не превышающее 1010 по абсолютной величине.

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

В выходной файл OUTPUT.TXT выведите все корни уравнения через пробел в порядке возрастания с ровно 6 знаками после запятой. В случае отсутствия корней следует вывести сообщение «No solution».

Примеры

INPUT.TXTOUTPUT.TXT
100.000000 1.000000
2-0.472471No solution
310000000000100000.001581

Задача G. Игра - 4

(Время: 1 сек. Память: 32 Мб)

А вы играли в игру «Кота в угол»? Правила игры очень просты. Есть прямоугольное игровое поле, заполненное клетками по принципу пчелиных сот – из каждой клетки можно перейти на 6 соседних. На одной из клеток сидит кот. За один ход кот может перейти на одну из соседних клеток, если она свободна (на рисунке свободные клетки светлые, а занятые – темные). Кот хочет как можно быстрее выйти за пределы игрового поля.

Определите минимальное число ходов, за которое он сможет это сделать.

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество строк и количество клеток в строке соответственно (N, M ≤ 1000). Вторая строка содержит два натуральных числа Y, X – номер строки и номер клетки в строке, где находится кот (Y ≤ N, X ≤ M). Далее идет N строк по M символов – описание игрового поля. Свободные клетки обозначены символом «1», занятые – символом «0».

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

В выходной файл OUTPUT.TXT выведите минимальное количество ходов, за которое кот может выйти за пределы игровой области. Или «No solution» (без кавычек), если это невозможно.

Примеры

INPUT.TXTOUTPUT.TXT
17 7
4 4
1111011
1111101
0111111
1111111
1011111
0011111
1111111
4
23 3
2 2
000
010
000
No solution

Задача H. Последовательность - 6

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

Дано натуральное число A. К нему применили следующую операцию – все цифры возвели в квадрат и просуммировали.

Например, для числа 123 получим 12 + 22 + 32 = 14.

К полученному результату указанную операцию применили еще несколько раз.

Определите, какое число получится, если указанную операцию повторить ровно N раз для заданного числа A.

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

Входной файл INPUT.TXT содержит два целых числа A и N (0 ≤ A, N ≤ 109).

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

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

INPUT.TXTOUTPUT.TXT
1123 114
21000000000 10000000001
34 489

Задача I. Биты

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

Дано натуральное число N. Необходимо найти младший и старший биты двоичной записи числа N, установленные в единицу, и вывести их в десятичной системе счисления.

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

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

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

В выходной файл OUTPUT.TXT выведите два числа: младший и старший бит числа N, разделенные пробелом.

Примеры

INPUT.TXTOUTPUT.TXT
1262 16
2888 64

Пояснение

В первом примере N = 2610 = 110102. Младший бит (11010) равен 102 = 210, старший бит (11010) равен 100002 = 1610.



Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483



горшки для орхидей стеклянные