Задачи олимпиады "Полуфинал XII Всероссийской командной олимпиады школьников по программированию (Восточно-Сибирский регион)"
Задача A. Всем известно
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Всем известно, что многие олимпиадные задачи начинаются со слов «Всем известно». Но мало кто знает, что начинающему программисту Паше такие задачи меньше всего нравятся. Потому что обычно после слов «всем известно» описывается такой факт, о котором он даже не догадывался. После очередной подобной задачи Паша решил проверить, а действительно ли всем известно, что сумма первых N нечетных чисел равняется N2:
Для этого Паша провел опрос всех людей, попавшихся ему под руку в известной социальной сети. Результаты опроса он записал в текстовый файл. Он ставил цифру один, если человеку был действительно известен данный факт, в противном случае в файл записывался нуль. Все было хорошо, пока Паша не открыл файл и не ужаснулся, увидев длинную последовательность из единичек. Как же он теперь будет искать среди них нули?
Уже всем известно, что Паша – начинающий программист, поэтому для обработки результатов исследования он обратился к вам за помощью.
Входные данные
Входной файл INPUT.TXT содержит непустую последовательность из нулей и единиц. Длина последовательности не превышает 104.
Выходные данные
В выходной файл OUTPUT.TXT выведите слово «YES», если факт был известен всем опрошенным людям, и слово "NO" в противном случае.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
11111101010011
NO
2
11
YES
Задача B. Шары
(Время: 2 сек. Память: 16 Мб Баллы: 100)
В пространстве расположен шар, заданный координатами своего центра X,Y,Z и радиусом R. К нему добавляется не более N новых шаров, которые также описываются координатами центров Xi, Yi, Zi и радиусами Ri (1 ≤ i ≤ N).
Шары добавляются до тех пор, пока есть хоть один шар, не пересекающийся с другими шарами. Требуется определить номер шара, после которого процесс добавления шаров можно прекратить.
Примечание:
Взаимное пересечение абсолютно всех шаров не требуется, т.е. решением является и наличие непересекающихся групп пересекающихся шаров;
Касание шаров не является пересечением.
Вложение одного шара в другой является пересечением.
Входные данные
Входной файл INPUT.TXT содержит четыре вещественных числа разделенных пробелами X, Y, Z, R - параметры исходного шара (|X, Y, Z| ≤ 30000; 0 < R ≤ 30000). Вторая строка содержит целое число N - количество шаров, которые предполагается добавить (1 ≤ N ≤ 5000). Следующие N строк содержат по четыре вещественных числа Xi, Yi, Zi, Ri - параметры i-го шара (1 ≤ i ≤ N; |Xi, Yi, Zi| ≤ 30000; 0 < Ri ≤ 30000).
Выходные данные
В выходной файл OUTPUT.TXT выведите номер шара, после которого процесс добавления шаров можно остановить, или 0 - если даже после добавления всех имеющихся шаров остается хотя бы один шар, не пересекающийся с другими.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
2 2 1 1
3
5 2 2 1
3 3 3 1.5
8 8 8 1
2
Задача C. Окружности
(Время: 1 сек. Память: 16 Мб Баллы: 100)
На какое максимальное число областей можно разбить плоскость при помощи N окружностей одинакового радиуса?
Входные данные
Входной файл INPUT.TXT содержит целое число N – количество окружностей, 0 ≤ N ≤ 33333.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – максимальное количество областей, на которое можно разбить плоскость при помощи N окружностей одинакового радиуса.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
0
1
2
3
8
Задача D. Деление-2
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Рассмотрим дробь 1/N. Чтобы преобразовать эту обыкновенную дробь в дробь десятичную, следует разделить числитель на знаменатель. Результат может иметь конечное число знаков, но может быть и бесконечной периодической дробью.
Примеры:
N = 2: 1/2 = 0,5 – конечное число знаков.
N = 7: 1/7 = 0,(142857) – бесконечная периодическая дробь.
N = 28: 1/28=0,03(571428) – бесконечная периодическая дробь с предпериодом (предпериод - минимальная по длине часть после запятой, которая не входит ни в один период).
Если десятичная дробь имеет конечное число знаков, то будем говорить, что она не имеет периода.
Ваша задача – написать программу, которая по заданному N определит, есть ли у дроби 1/N в десятичной записи период, или нет.
Входные данные
Входной файл INPUT.TXT содержит натуральное число N, не превосходящее 1018.
Выходные данные
В выходной файл OUTPUT.TXT выведите «YES» – если у дроби 1/N есть период, иначе выведите «NO».
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2
NO
2
3
YES
Задача E. Экзамены
(Время: 1 сек. Память: 16 Мб Баллы: 100)
В этом году при поступлении в университет абитуриентам требовалось успешно сдать экзамены по математике и физике. К сожалению, с этим испытанием справились не все. Известно, что на экзамены пришло N абитуриентов, из них M – сдали математику, F – сдали физику, а L – не сдали ни одного предмета. Найдите, сколько абитуриентов сдали оба предмета и стали студентами, а также определите, сколько абитуриентов сдали один экзамен: только по математике или только по физике.
Входные данные
Входной файл INPUT.TXT содержит четыре целых числа, разделенных пробелами: N (0 < N ≤ 2×109), M, F, L (0 ≤ M, F, L ≤ 2×109).
Выходные данные
В выходной файл OUTPUT.TXT выведите три числа через пробел:
a) количество абитуриентов, сдавших оба экзамена;
b) количество абитуриентов, сдавших только математику;
с) количество абитуриентов, сдавших только физику.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2 2 1 0
1 1 0
2
10 5 5 5
5 0 0
3
10 5 5 0
0 5 5
Задача F. Поля
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Геннадий учится в сельской школе и мечтает стать агрономом. На уроке геометрии Геннадий познакомился с новой фигурой – прямоугольником. Освоив вычисление площади прямоугольника, Гена подумал о том, что квадратные поля гораздо удобнее, нежели прямоугольные. Поразмыслив еще немного, Гена столкнулся с интересной задачей: существует ли такое квадратное поле, у которого площадь в точности равна площади заданного поля прямоугольной формы, чтобы при этом длины сторон обеих полей были бы целыми числами?
Входные данные
Входной файл INPUT.TXT содержит целые числа a и b – длины сторон прямоугольника (1 < = a*b ≤ 1014).
Выходные данные
В выходной файл OUTPUT.TXT выведите либо одно целое число c – длину стороны квадрата, либо 0, если квадрата с целочисленной длиной стороны не существует.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
1 4
2
2
2 8
4
3
15 42
0
Задача G. Гиганты
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Астроному Василию по роду службы часто приходится иметь дело с невероятно большими числами. Очень часто такие числа приходится возводить в не менее огромные степени. К счастью, для предварительных расчетов Василию не понадобится весь результат расчетов – вполне хватит последней цифры.
Входные данные
Входной файл INPUT.TXT содержит два натуральных числа X и Y, не превосходящих 1040.
Выходные данные
В выходной файл OUTPUT.TXT выведите последнюю цифру числа XY.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
7 3
3
2
2 5
2
Задача H. Герои
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Коварный кардинал Ришелье вновь организовал похищение подвесок королевы Анны; вновь спасать королеву приходится героическим мушкетерам. Атос, Портос, Арамис и д’Артаньян уже перехватили агентов кардинала и вернули украденное; осталось лишь передать подвески королеве Анне. Королева ждет мушкетеров в дворцовом саду. Дворцовый сад имеет форму прямоугольника и разбит на участки, представляющие собой небольшие садики, содержащие коллекции растений из разных климатических зон. К сожалению, на некоторых участках, в том числе на всех участках, расположенных на границах сада, уже притаились в засаде гвардейцы кардинала; на бой с ними времени у мушкетеров нет. Мушкетерам удалось добыть карту сада с отмеченными местами засад; теперь им предстоит выбрать наиболее оптимальные пути к королеве. Для надежности друзья разделили между собой спасенные подвески и проникли в сад поодиночке, поэтому начинают свой путь к королеве с разных участков сада. Двигаются герои по максимально короткой возможной траектории.
Марлезонский балет вот-вот начнется; королева не в состоянии ждать героев больше L минут; ровно в начале L+1-ой минуты королева покинет парк, и те мушкетеры, что не успеют к этому времени до нее добраться, не смогут передать ей подвески. На преодоление одного участка у мушкетеров уйдет ровно по минуте. С каждого участка мушкетеры могут перейти на 4 соседние. Требуется выяснить, сколько подвесок будет красоваться на платье королевы, когда она придет на бал.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа N и M (1 ≤ N,M ≤ 20) – размеры сада. Далее идут N строк по M символов в каждом; символы '0' соответствуют участкам, на которых нет засады, символы '1' – участкам, на которых разместились гвардейцы. В N+2-ой строке теста записано три целых числа: координаты участка, на котором королева будет ждать мушкетёров (Qx, Qy) (1 < Qx < N, 1 < Qy < M) и время в минутах до начала балета (1 ≤ L ≤ 1000). В N+3-ей строки записаны через пробел целые числа координаты участка, с которого стартует Атос (Ax,Ay) (1 < Ax < N, 1 < Ay < M) и количество подвесок, хранящихся у него (1 ≤ Pa ≤ 1000). В N+4, N+5 и N+6-ой строках аналогично записаны стартовые координаты и количество подвесок у Портоса, Арамиса и д’Артаньяна.
Выходные данные
В выходной файл OUTPUT.TXT выведите количество подвесок, которое королева успеет получить у мушкетеров до начала балета.
Катя и Таня играли в слова. Одна из девочек называла слово на английском языке, вторая должна найти анаграмму. Анаграмма – это слово, полученное из другого слова путем перестановки всех без исключения букв первого слова.
Написать программу, которая проверит, правильно ли девочки создают анаграммы.
Входные данные
Входной файл INPUT.TXT содержит два слова на английском языке в нижнем регистре, разделенные пробелом. Каждое слово содержит от 1 до 20 символов.
Выходные данные
В выходной файл OUTPUT.TXT выведите «YES», если анаграмма подобрана правильно, иначе выведите «NO».
