Задачи олимпиады "Полуфинал XVI Всероссийской командной олимпиады школьников по программированию (Восточно-Сибирский регион)"
Задача A. Треугольник
(Время: 1 сек. Память: 16 Мб)
Периметр равнобедренного треугольника равен N. Найдите боковую сторону треугольника, если она на K меньше основания.
Входные данные
Входной файл INPUT.TXT содержит два целых числа, разделенных пробелом – N и K (3 ≤ N ≤ 109, 0 ≤ K < N). Длина боковой стороны и основания выражаются в целых числах.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – боковую сторону треугольника.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
23 2
7
2
18 0
6
Задача B. Блоки
(Время: 3 сек. Память: 16 Мб)
Дана последовательность из N целых чисел. Необходимо «сжать» данную последовательность, объединив одинаковые подряд идущие элементы в блоки.
Входные данные
Первая строка входного файла INPUT.TXT содержит одно натуральное число N – количество элементов последовательности (N ≤ 106). Во второй строке записаны N элементов последовательности (целые числа, разделенные пробелами, не превосходящие 109 по абсолютной величине).
Выходные данные
В выходной файл OUTPUT.TXT выведите количество блоков, а потом сами блоки – в квадратных скобках: сначала значение элемента последовательности, а потом количество одинаковых подряд идущих элементов.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
9 1 1 2 3 3 3 2 1 1
5 [1 2] [2 1] [3 3] [2 1] [1 2]
2
3 1 2 3
3 [1 1] [2 1] [3 1]
Задача C. Мосты
(Время: 1 сек. Память: 16 Мб)
Вася живет в городе С.-П. Не нужно говорить (это итак все знают), что в городе С.-П. очень много мостов. И, как любому человеку, Васе часто нужно добираться из пункта A в пункт Б.
У Васи есть детальная карта города С.-П. Карта представляет собой квадратную решетку, размером N×M, где каждая ячейка – либо свободное пространство, по которому можно двигаться, либо препятствие (дома, водоемы, и т. п.), либо мост. Север, как обычно, находится вверху карты. Все мосты расположены с запада на восток (или с востока на запад). Это значит, что если Вася войдет в клетку с мостом с запада или востока, то он окажется на мосту, и выйти с этой клетки он может только на запад или на восток. Если же Вася войдет в клетку с мостом с юга или севера, то он окажется под мостом, и выйти сможет только на юг или на север.
Помогите Васе – посчитайте, сколько клеток карты ему нужно пройти, чтобы попасть из пункта А в пункт Б (умножить ваш ответ на масштаб карты Вася может и сам).
Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – размеры карты (N, M ≤ 100). Следующие N строк содержат саму карту (по M символов в каждой строке). Символ «.» соответствует пустому пространству, символ «#» – препятствию, «B» – мосту, «S» – стартовой точке маршрута, «E» – конечной точке маршрута. Стартовая и конечная точки находятся на пустом пространстве.
Выходные данные
В выходной файл OUTPUT.TXT выведите длину кратчайшего маршрута между начальной и конечной точкой или -1, если такого маршрута не существует.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
1 2 SE
1
2
2 3 SB. #E#
-1
3
3 3 #E# SB. #..
6
Задача D. Скидки
(Время: 1 сек. Память: 16 Мб)
В супермаркете существует система скидок: из двух купленных товаров полностью оплачивается только стоимость более дорогого товара, а другой предоставляется бесплатно.
Какой суммы достаточно, чтобы оплатить покупку трех товаров, если известна цена каждого?
Входные данные
Входной файл INPUT.TXT содержит три натуральных числа, разделенных пробелами: A, B, C – стоимость первого, второго и третьего товара (A, B, C ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – минимальную сумму, достаточную для покупки всех трех товаров.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
8 11 6
17
2
10 10 10
20
Задача E. Забег
(Время: 1 сек. Память: 16 Мб)
Однажды заяц и черепаха решили устроить благотворительный забег. Они выбрали дистанцию длиной L км и позвали много-много зрителей.
Черепаха и заяц бегут с постоянной скоростью. Скорость черепахи всего V км/ч, а скорость зайца на D км/ч выше. Поэтому сразу после старта заяц обогнал черепаху и убежал далеко вперед. Но просто так выиграть гонку зайцу не интересно. Поэтому добежав до финиша, он мгновенно развернулся и побежал назад с той же скоростью, чтобы узнать положение черепахи. Добежав до черепахи, которая совсем недалеко успела убежать от старта, он снова мгновенно развернулся и побежал в сторону финиша. Так от черепахи до финиша и обратно до нового положения черепахи и бегал заяц, пока черепаха не добежала до финиша. Что самое интересное – финишную черту она пересекла одновременно с зайцем!
Если черепаха пробежала L км, то какой путь пробежал заяц?
Входные данные
Входной файл INPUT.TXT содержит четыре целых числа, разделенных пробелами: L – длина дистанции (1 ≤ L ≤ 109), V – скорость черепахи (1 ≤ V ≤ 109), D – разница в скорости зайца и черепахи (0 ≤ D ≤ 109), P – точность (0 ≤ P ≤ 6).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – пройденный зайцем путь с P знаками после запятой и с точностью 10-P .
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
30 4 2 3
45.000
2
20 5 0 0
20
3
33 80 28 1
44.6
Задача F. Формула
(Время: 1 сек. Память: 16 Мб)
Во входном файле задана без ошибок формула следующего вида:
AND обозначает логическую операцию И;
OR обозначает логическую операцию ИЛИ;
| - знак «или»;
Значение в фигурных скобках {} может повторяться ноль или более раз.
Необходимо вычислить значение данной формулы.
Входные данные
Входной файл INPUT.TXT содержит одну формулу в указанном формате без ошибок (непустая строка, содержащая не более 1000 символов).
Выходные данные
В выходной файл OUTPUT.TXT выведите значение заданной формулы.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
AND(1,OR(0,1))
1
2
OR(AND(0,0),AND(0,0,0),AND(0,0,0,0))
0
3
1
1
Задача G. Беспризорник
(Время: 1 сек. Память: 16 Мб)
Беспризорник нашел N окурков. Из K окурков он скручивает самокрутку и выкуривает. После чего от самокрутки тоже остается окурок. Для новой самокрутки беспризорник может использовать как найденные окурки, так и оставшиеся от его самокруток.
Какое максимальное количество самокруток выкурит беспризорник и сколько окурков у него останется?
Входные данные
Входной файл INPUT.TXT содержит два натуральных числа, разделенных пробелом – N и K (2 ≤ N, K ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите два числа – сколько самокруток выкурит беспризорник и сколько окурков у него останется.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
8 3
3 2
2
5 5
1 1
3
6 7
0 6
Примечание
Минздрав предупреждает: курение опасно для Вашего здоровья! Особенно курение самокруток из окурков .
Задача H. Квадратный корень
(Время: 1 сек. Память: 16 Мб)
Даны два последовательных четных (или нечетных) натуральных числа.
Необходимо их перемножить, прибавить единицу и извлечь квадратный корень. Если результат не будет целым числом, то следует округлить его до ближайшего целого по стандартным правилам.
Входные данные
Входной файл INPUT.TXT содержит два последовательных четных (или нечетных) натуральных числа, разделенных пробелом. Каждое число содержит не более 1000 разрядов.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2 4
3
2
3 5
4
Задача I. Студенты
(Время: 1 сек. Память: 16 Мб)
По данным приемной комиссии N человек были зачислены в этом году на первый курс в бакалавриат, специалитет и магистратуру СФУ.
На основе таблицы, содержащей фамилию, имя, отчество (если оно есть) и пол всех первокурсников найдите самое распространенное женское имя.
Входные данные
Первая строка входного файла INPUT.TXT содержит натуральное число N – количество первокурсников (N ≤ 1000). Далее идет N строк, в каждой из которых указаны фамилия, имя, отчество (может отсутствовать) и пол студента. Фамилия, имя и отчество – непустая строка из английских символов (не более 10), первая буква прописная, остальные строчные. Пол: символ «m» - мужской или «w» - женский. Все слова в строке разделены одним пробелом.
Выходные данные
В выходной файл OUTPUT.TXT выведите самое распространенное женское имя. Если несколько имен встречаются чаще всего – выведите их все через запятую без пробелов в порядке первого появления во входных данных. Если все женские имена встречаются только один раз – выведите «UNIQUE!» (без кавычек). Если на первый курс поступили только мужчины - выведите «NO DATA!» (без кавычек).
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
4
Petrova Anna Petrovna w
Alieva Inna w
Ivanova Inna Ivanovna w
Sidorova Anna Sidorovna w
Anna,Inna
2
1
Ivanov Ivan Ivanovich m
NO DATA!
3
2
Petrov Petr Petrovich m
Petrova Petra Petrovna w
UNIQUE!
Задача J. Слова
(Время: 1 сек. Память: 16 Мб)
Британские ученые изобрели новый способ форматирования текстовых сообщений и назвали его «лесенкой». Порядок действий при форматировании сообщения следующий:
каждое слово в сообщении выводится в отдельной строке;
перед первым словом не выводится символ «.» (точка);
перед вторым словом выводится столько точек, сколько букв в первом слове;
перед третьим словом выводится столько точек, сколько букв в первом и втором словах и т.д.;
в конце строки не должно быть точек.
Требуется написать программу для форматирования сообщений «лесенкой».
Входные данные
Входной файл INPUT.TXT содержит сообщение, состоящее не более чем из 1000 символов. Все слова в сообщении состоят из строчных и прописных английских букв и разделены одним ли несколькими пробелами. В начале или в конце сообщения тоже может быть один или несколько пробелов. Сообщение всегда содержит хотя бы одно слово. В примерах для большей наглядности пробелы заменены на плюсы!
Выходные данные
В выходной файл OUTPUT.TXT выведите сообщение, отформатированное «лесенкой».
.