Задачи олимпиады "Полуфинал XV Всероссийской командной олимпиады школьников по программированию (Восточно-Сибирский регион)"
Задача A. Станки
(Время: 1 сек. Память: 16 Мб)
Есть два станка, на которых выпускают одинаковые запчасти. Один производит A запчастей в час, другой – В запчастей в час.
Найдите минимальное время (в часах), необходимое для выпуска N запчастей. При этом можно использовать как один станок, так и оба одновременно.
Входные данные
Входной файл INPUT.TXT содержит три натуральных числа: N, A и B (1 ≤ N, A, B ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – минимальное время (в часах), необходимое для выпуска N запчастей.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
10 2 3
2
2
5 1 1
3
Задача B. Распродажа
(Время: 1 сек. Память: 16 Мб)
В магазине товар стоил N рублей. Он сначала подорожал на A%. После чего его стоимость округлили до целого значения по стандартным правилам. Спустя некоторое время этот товар подешевел на B%. После чего его стоимость снова округлили до целого числа по стандартным правилам.
Сколько рублей стал стоить товар?
Входные данные
Входной файл INPUT.TXT содержит три целых числа, разделенных пробелом: N (1 ≤ N ≤ 109), A (0 ≤ A ≤ 100) и B (0 ≤ B ≤ 99).
Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – стоимость товара в рублях после удешевления.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
100 10 10
99
2
1 0 50
1
3
999999995 98 5
1880999991
Задача C. Последовательность
(Время: 1 сек. Память: 16 Мб)
Дана последовательность из N целых чисел. В этой последовательности необходимо найти минимальный и максимальный элементы, которые делятся на натуральное число M.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа: N – количество элементов последовательности (1 ≤ N ≤ 104) и число М (1 ≤ M ≤ 231-1). Во второй строке записаны A[i] – N элементов последовательности (целые числа, разделенные пробелами, -231 ≤ A[i] ≤ 231-1).
Выходные данные
В выходной файл OUTPUT.TXT выведите значения минимального и максимального элементов последовательности, которые делятся на M. Если ни одного такого элемента нет – выведите «NO» (без кавычек).
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
5 3 1 -9 0 5 12
-9 12
2
3 4 -5 2 13
NO
Задача D. Обратное число
(Время: 1 сек. Память: 16 Мб)
Назовем обратным числом для натурального числа N число, получающееся по следующему правилу:
число N записывают в двоичной системе счисления;
все нули заменяют на единицы, а единицы – на нули;
результат переводится в десятичную систему счисления.
Требуется написать программу, вычисляющую обратное число для заданного числа N.
Входные данные
Входной файл INPUT.TXT содержит натуральное число N (N ≤ 1018) в десятичной системе счисления.
Выходные данные
В выходной файл OUTPUT.TXT выведите обратное число для числа N в десятичной системе счисления.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
5
2
2
12
3
3
23
8
4
8
7
5
1000000000
73741823
Задача E. Шифровка
(Время: 1 сек. Память: 16 Мб)
Британские ученые изобрели новый алгоритм шифрования. Порядок действий для шифрования сообщения следующий:
в строку записывается первое слово сообщения;
второе слово дописывается в начало строки;
третье слово дописывается в конец строки;
четвертое слово снова дописывается в начало строки и т.д.
Кроме того, в каждом слове буквы располагаются таким же образом, т.е.:
записывается первая буква;
вторая буква дописывается в начало слова;
третья буква дописывается в конец слова;
четвертая буква снова дописывается в начало слова и т.д.
При этом:
В качестве букв используются только английские строчные и прописные буквы.
Слова в сообщении разделены строго одним пробелом.
В начале и конце сообщения нет пробелов.
Требуется написать программу для расшифровки сообщения.
Входные данные
Входной файл INPUT.TXT содержит непустое секретное сообщение, состоящее не более чем из 104 символов.
Выходные данные
В выходной файл OUTPUT.TXT выведите расшифрованное сообщение.
где М обозначает функцию max – максимальный элемент, m обозначает функцию min – минимальный элемент, | - знак «или».
Требуется вычислить значение по данной формуле.
Входные данные
Входной файл INPUT.TXT содержит формулу в указанном формате без ошибок (непустую строку, состоящую не более чем из 1000 символов).
Выходные данные
В выходной файл OUTPUT.TXT выведите цифру – значение данной формулы.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
M(5,m(6,8))
6
2
M(m(1,2),m(4,3))
3
3
0
0
Задача G. Экзамены
(Время: 1 сек. Память: 16 Мб)
Вступительные испытания в вуз состоят из трех экзаменов – математики, информатики и русского языка. На каждом из них абитуриент может набрать от одного до ста баллов. По результатам сдачи экзаменов составляется экзаменационная ведомость, где для каждого студента указывается фамилия и баллы за каждый экзамен. Для определения лучших абитуриентов, данная ведомость сортируется по сумме набранных баллов по убыванию за все экзамены, а если сумма баллов совпадает – по фамилии (в алфавитном порядке, по убыванию). После чего первые M абитуриентов из списка зачисляются на первый курс и становятся студентами!
Ваша задача – по экзаменационной ведомости определить фамилию и сумму баллов последнего зачисленного абитуриента.
Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа: N – количество абитуриентов в ведомости и M – количество абитуриентов, которые будут зачислены на первый курс (M ≤ N ≤ 1000). Далее идет N строк, в каждой из которых указана фамилия студента и 3 натуральных числа – баллы за каждый экзамен. Фамилия студента – непустая строка из английских символов (не более 10), первая буква прописная, остальные – строчные.
Выходные данные
В выходной файл OUTPUT.TXT выведите фамилию и сумму баллов последнего поступившего абитуриента.
Точка C - середина отрезка AB на плоскости. Найдите координаты точки B, если известны координаты точек A и C.
Входные данные
Входной файл INPUT.TXT содержит четыре целых числа – ХА, YА, ХC, YC - координаты точек A и C соответственно (числа разделены одним пробелом и не превышают 104 по абсолютной величине).
Выходные данные
В выходной файл OUTPUT.TXT выведите два целых числа, разделенных пробелом – координаты точки B.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
-4 8 3 7
10 6
Задача I. Лабиринт минотавра
(Время: 2 сек. Память: 32 Мб)
Вы слышали про игру «Лабиринт минотавра»? В этой игре бесстрашный герой Тесей пытается выбраться из запутанного лабиринта. Лабиринт имеет прямоугольную форму – N×M клеток. За один ход Тесей может перейти на соседнюю свободную клетку по вертикали или по горизонтали, либо, если он находится на краю лабиринта, покинуть его. Клетка может быть либо свободной, либо занятой стеной или дверью. Сквозь стены проход невозможен. Сквозь двери можно проходить только при наличии ключа, который подходит ко всем дверям и хранится где-то в лабиринте!
Для поиска выхода из лабиринта Тесей применяет специальную тактику:
Сначала он пытается найти выход по свободным клеткам.
Если Тесею это не удается – он пытается отыскать ключ, чтобы открывать им двери и искать путь на свободу.
По карте лабиринта требуется определить, сможет ли Тесей выбраться из лабиринта, или же ему придется остаться в этом ужасном месте.
Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – длина и ширина лабиринта (2 ≤ N, M ≤ 1000). Далее идет N строк по M символов – описание лабиринта. Свободные клетки обозначены символом «.», стены – символом «#», двери – символом «-», «T» – положение Тесея в начальный момент времени, «K» – свободная клетка с ключом. Гарантируется, что в лабиринте только один Тесей и только один ключ.
Выходные данные
В выходной файл OUTPUT.TXT выведите:
Если Тесей может выйти за пределы лабиринта без ключа – минимальное количество ходов, которое для этого понадобится.
Если не может – напечатать «No way» (без кавычек) и дополнительно через пробел вывести:
минимальное количество ходов, которое понадобится, чтобы добраться из начальной позиции Тесея до ключа;
«No key» (без кавычек) - если ключ недостижим.
Если ключ достижим, то следует дополнительно через пробел вывести:
минимальное количество ходов после взятия ключа, которое понадобится для того, чтобы покинуть лабиринт;
«No way» (без кавычек) – если даже с ключом нельзя выбраться из лабиринта.
