У Марфы Геннадьевны есть любимая курица, которую она назвала Марфой.
В определённые дни Марфа давала по яйцу, и Марфа Геннадьевна в тот же день
съедала его. Марфа Геннадьевна записывала, в какие дни Марфа давала яйцо.
Однажды Марфа Геннадьевна где-то прочитала, что рекомендуется съедать
не более двух яиц в неделю. Марфа Геннадьевна заинтересовалась, нарушала
ли она хоть раз это правило, то есть найдётся ли промежуток из семи
подряд идущих дней, в который она съедала более двух яиц.
Напишите программу, принимающую на вход список номеров дней, в которые
Марфа Геннадьевна съедала яйца, и определяющую, съедала ли она хоть раз
более двух яиц в неделю.
Формат входного файла
Входной файл содержит целое число N.
Далее следуют N целых чисел ai — номера дней, в которые Марфа Геннадьевна
съедала яйцо.
Формат выходного файла
Требуется вывести в выходной файл слово GOOD, если Марфа Геннадьевна съедала
не более двух яиц в неделю, и слово BAD, если найдётся хотя бы один промежуток
из семи подряд идущих дней, в который она съедала более двух яиц.
Имеется N кубиков, на гранях которых написаны буквы.
Требуется определить, можно ли из этих кубиков составить данное слово длиной K символов,
и если да, то вывести номера использованных кубиков.
При этом каждый кубик можно использовать только один раз.
Если решений несколько, выдать любое из них.
Формат входного файла
В первой строке входного файла содержится количество кубиков N.
Во второй строке — слово, в следующих N строках — по шесть символов без разделителей,
определяющих буквы на гранях кубиков. (Порядок букв не имеет значения).
Формат выходного файла
Выходной файл должен содержать последовательность из K различных целых чисел от 1 до N,
задающих номера кубиков для каждой буквы слова, начиная с первой.
Если решения нет, выходной файл должен содержать единственное число 0.
Оперативная память компьютера имеет объём V байт, пронумерованных от 0
до V − 1.
Выделенные блоки памяти задаются последовательностью адресов
(a1, b1),
(a2, b2), …
(aN, bN).
Блоки отсортированы по адресам и не перекрываются, т. е.
0 ≤ ai ≤ bi < ai + 1
< V.
Операционная система пытается выделить память под ещё один блок объёмом M байт.
Если свободное пространство такого размера отсутствует, она может попытаться
переместить какой-нибудь один из блоков, чтобы освободить непрерывный участок
нужной длины.
Требуется выбрать для перемещения блок наименьшей длины. Если таких вариантов несколько,
следует выбрать блок с наименьшим начальным адресом.
Формат входного файла
Во входном файле расположены целые числа VNM.
Далее идут N пар чисел aibi.
Формат выходного файла
Выходной файл должен содержать единственное целое число:
номер блока, который нужно перемещать;
0, если блоки перемещать не нужно (непрерывный участок нужного объёма есть сразу);
−1, если решения нет (пространство нужного объёма освободить не удаётся).
Шифрование строки подстановочным шифром производится путём замены каждого символа алфавита на другой символ.
Разумеется, для однозначного шифрования и дешифрования необходимо, чтобы каждому символу исходного алфавита
соответствовал ровно один символ зашифрованного, и наоборот.
Например, при помощи шифра M->A, A->R, Y->K слово MAYA будет зашифровано в ARKR.
Даны две строки одинаковой длины, состоящие из заглавных латинских букв.
Требуется найти подстановочный шифр, при помощи которого первая строка шифруется во вторую, или определить,
что такого не существует. Например, для слов "GOOD" и "WELL" шифра не существует, потому что с одной
стороны, буква "O" преобразуется одновременно в "E" и "L", а с другой стороны,
буквы "O" и "D" обе превращаются в "L".
Формат входного файла
Входной файл содержит две строки.
Формат выходного файла
Выходной файл должен содержать последовательность пар символов, обозначающих замену при шифровании первого символа пары на второй. Пары должны быть расположены по одной в строке и отсортированы по алфавиту.
В случае, если шифра не существует, следует вывести в выходной файл строку "--" (два знака минус).
Слова марсианского языка записываются малыми латинскими буквами.
При этом буквы a, e, i, o, u, y считаются гласными,
а остальные — согласными.
Марсианские слова состоят из необязательной приставки, корня,
и необязательного суффикса.
При этом все приставки заканчиваются на согласную букву,
а все суффиксы — начинаются с согласной буквы.
Например, слово marsianin
может быть записано в виде приставка(корень)суффикс как:
m(arsianin), mar(sia)nin, (mar)sianin, и другими способами.
Марсианские слова называются однокоренными, если каждое из них можно
разделить на приставку, корень и суффикс так, чтобы корни совпадали.
Требуется по данным двум марсианским словам определить,
являются ли они однокоренными.
Формат входного файла
В первой строке входного файла содержится первое слово, во второй — второе слово.
Формат выходного файла
Выходной файл должен содержать слово YES,
если слова однокоренные, и NO в противном случае.
Недавно Ассоциация Ловцов Шушанчиков известила крокодила Гену о
приближающемся ежегодном конкурсе по ловле этих зверьков. Гена сразу же стал
собираться в путь к месту соревнований. Первым делом он решил купить новые
чемоданы из крокодиловой кожи. Большой опыт Гены говорит о том, что в
путешествие следует брать не более K плоских чемоданов квадратной формы.
В ассортименте чемоданного магазина имеется неограниченное количество
плоских квадратных чемоданов с любой целочисленной длиной стороны. Стоимость
каждого чемодана в рублях равняется квадрату длины его стороны —
пропорционально площади, обтянутой дорогостоящей кожей.
Ассоциация выдала Гене N рублей на затраты, связанные с поездкой. Однако
бухгалтерия Ассоциации требует, чтобы каждый участник конкурса полностью
потратил выделенные ему средства. Лишних денег у Гены тоже нет, так что ему
необходимо купить чемоданы на сумму ровно N рублей.
Теперь Гену интересует, возможно ли потратить ровно N выданных рублей,
купив не менее одного, но и не более K чемоданов.
Формат входного файла
В единственной строке входного файла содержатся целые числа N и K.
Формат выходного файла
Если интересующая Гену покупка невозможна, то в выходном файле должна
содержаться строка NO. В противном случае в первой строке выходного
файла должно содержаться YES, а во второй строке — длины сторон
чемоданов, которые следует приобрести, записанные через пробел в
произвольном порядке. Если существует несколько решений, вывести любое из
них.
Для изготовления качественной табуретки необходимы 4 ножки одинаковой длины.
На табуреткоизготовительную фабрику поступило N ножек,
имеющих слегка различающиеся длины L1, L2, …, LN.
Требуется определить максимальное количество качественных табуреток,
которые можно изготовить из данных ножек.
Формат входного файла
Входной файл содержит число N, за которым следуют N чисел
Li — длины ножек. Все числа целые.
Формат выходного файла
В выходной файл следует вывести единственное целое число —
максимальное количество табуреток.
Для изготовления качественной табуретки необходимы 4 ножки одинаковой длины.
На табуреткоизготовительную фабрику поступило N ножек,
имеющих слегка различающиеся длины L1,
L2, … LN.
Научно-исследовательский отдел фабрики обнаружил,
что выпуск табуреток можно увеличить, если укорачивать некоторые ножки.
При этом отпиленная часть выбрасывается.
Требуется определить минимальное количество распилов, необходимых для
для изготовления N / 4 качественных табуреток.
Формат входного файла
Входной файл содержит число N, за которым следуют N чисел
Li — длины ножек. Все числа целые.
Формат выходного файла
В выходной файл следует вывести единственное целое число — минимальное
количество распилов.
Ограничения
1 ≤ N ≤ 10000, N mod 4 = 0,
1 ≤ Li ≤ 100.
Огород, по которому бегает собачка, представляет собой квадрат размером
N × N метров.
Разумеется, это не первая среди собак, бегавших по этому огороду,
и каждая из них хотя бы раз закапывала в нем косточки.
Поэтому в разных местах огорода присутствует
вкусный запах разной интенсивности.
Огород разделён на N2 квадратиков, в квадратике
с координатами (i, j) интенсивность запаха равняется ai,j.
Квадратик с координатами (1, 1) расположен в левом верхнем углу огорода.
Первая координата откладывается по горизонтали, вторая — по вертикали.
Вначале собака находится в квадратике с координатами (i0, j0).
На каждом шаге собака перемещается в соседний (слева, сверху, справа
или снизу) квадратик, в котором запах самый сильный и сильнее, чем
в квадратике, в котором находится собака. Если такого квадратика
не оказалось, то собака останавливается.
Напишите программу, позволяющую найти траекторию собаки.
Формат входного файла
Входной файл содержит целые числа Ni0j0.
Далее следуют N2 целых чисел ai,j.
Формат выходного файла
Выходной файл должен содержать пары целых чисел —
траекторию собаки.
Входные данные таковы, что траектория собаки определена однозначно.
Мальчик Петя придумал страшного Бармаглота, хватающего детей.
Когда Петя зашёл в свою комнату, чтобы ложиться спать, он увидел, что одеяло на кровати
очень похоже на Бармаглота. Требуется по заданной форме одеяла и форме Бармаглота
определить, может ли Бармаглот поместиться под одеялом, и, соотвественно,
следует ли Пете испугаться и заплакать или спокойно пойти спать.
Одеяло и Бармаглот имеют форму ломаных, заданных целочисленными координатами вершин
(x1, y1),
(x2, y2), …
(xN, yN)
для одеяла,
(u1, v1),
(u2, v2), …
(uM, vM)
для Бармаглота.
При этом
xi + 1 > xi и
ui + 1 > ui для всех i.
Чтобы спрятаться под одеялом, Бармаглот должен полностью под него поместиться,
т.е. описывающая его ломаная должна целиком находиться ниже ломаной, описывающей одеяло.
Касания ломаных разрешены.
Формат входного файла
Во входном файле расположены числа Nx1y1x1y1 …
xNyN Mu1v1u1v1 …
uMvM
Формат выходного файла
Выходной файл должен содержать единственную строку CRY,
если Бармаглот может поместиться под одеялом или SLEEP, если не может.
Ограничения
3 ≤ M, N ≤ 100,
0 ≤
xi, yi,
ui, vi ≤ 10000,
x1 = u1,
xN = uM.
Руководство российского НИИ Абсолютно Симметричных Моделей (АСМ) решило внедрить
систему электронного документооборота, включающую в себя контактные данные работников.
Сотрудник отдела кадров столкнулся с проблемой:
система позволяет вводить телефонные номера только в международном формате,
а номера в анкетах работников записаны в произвольном
формате, лишь позволяющим отделить код региона от локального номера.
Более того, цифры, образующие локальный номер, могут быть разделены
на группы с произвольным количеством цифр в каждой.
Российский телефонный номер в международном формате выглядит следующим образом:
+7␣код_региона␣локальный_номер.
В зависимости от длины кода региона существует 4 допустимых варианта записи:
+7␣123␣123-45-67
+7␣1234␣12-34-56
+7␣12345␣1-23-45
+7␣123456␣12-34
+7, код региона и локальный номер отделяются друг от друга пробелом (ASCII 32),
цифры внутри локального номера
делятся на группы символом "тире" (ASCII 45) только так, как описано выше,
другие варианты, например, 1-23-45-67 и т. д. недопустимы.
Сотрудник отдела кадров НИИ АСМ просит Вас написать программу,
конвертирующую телефонный номер в международный формат.
Формат входного файла
Входной файл содержит единственную строчку с телефонным номером.
Формат выходного файла
Выходной файл должен содержать единственную строчку — телефонный номер в международном формате.
Ограничения
Каждый телефонный номер работника начинается с подстроки +7 после которой следует код региона
и локальный номер.
Код региона — первый блок подряд идущих цифр после +7.
В качестве символов разделителя могут быть использованы пробелы (ASCII 32) и тире (ASCII 45).
Код региона может быть также обрамлён
круглыми скобками (ASСII 40 и ASСII 41), в этом случае символы разделителя вокруг скобок могут быть опущены.
Суммарное количество цифр в коде региона и локальном номере равно 10.
Длина входной строки не превышает 25 символов.
Крокодил Гена решил поступить в университет.
Для поступления ему нужно пройти тест, состоящий из Q вопросов.
На каждый из них можно ответить либо "Да", либо "Нет".
Количество баллов, получаемых абитуриентом за тест,
равно количеству данных им правильных ответов.
Все абитуриенты проходят тест с одними и теми же вопросами.
Поскольку Гена не подготовился к тесту, он решил схитрить.
Для этого он подговорил P шушанчиков, чтобы они прошли тест до него.
Каждый шушанчик запомнил, как он отвечал на каждый из вопросов,
и сколько баллов получил.
По этим данным Гена должен определить правильные ответы.
Формат входного файла
В первой строке входного файла содержатся числа PQ.
Далее следует P описаний шушанчиков, по две строки на описание:
В первой строке описываются ответы, данные шушанчиком.
Они задаются строкой длинной Q, состоящей из символов
+ (ASCII 43) или - (ASCII 45)
для ответов "Да" или "Нет" соответственно.
На i-ой позиции строки находится ответ на i-ый вопрос.
Во второй строке содержится целое число — количество баллов.
Формат выходного файла
В выходном файле должна содержаться единственная строка,
состоящая из Q символов + (ASCII 43) или - (ASCII 45) —
правильные ответы к тесту.
Если существует несколько вариантов правильных ответов, вывести любой из них.
Так, во втором примере допустим также ответ -+++.
Ограничения
1 ≤ P ≤ 1000, 1 ≤ Q ≤ 15
Исходные данные таковы, что существует хотя бы один вариант решения.
Рассмотрим правильный треугольник. Разделим каждую его сторону на N равных частей точками и проведём
через эти точки прямые, параллельные сторонам треугольника.
Спрашивается: сколько всего треугольников на рисунке? (Учитываются треугольники разных размеров.)
Формат входного файла
Входной файл содержит единственное целое число N.
Формат выходного файла
Требуется вывести в выходной файл единственное целое число — количество треугольников.
Однажды программист Вася решил научиться играть на гитаре.
Первым делом он выучил правила настройки гитары.
Первая струна настраивается по камертону. Каждая следующая струна настраивается по предыдущей, а именно:
вторая струна, зажатая на пятом ладу, звучит в унисон с открытой первой;
третья струна, зажатая на четвёртом ладу, звучит в унисон с открытой второй;
четвёртая струна, зажатая на пятом ладу, звучит в унисон с открытой третьей;
пятая струна, зажатая на пятом ладу, звучит в унисон с открытой четвёртой;
шестая струна, зажатая на пятом ладу, звучит в унисон с открытой пятой.
Настроив первую струну, Вася проверяет звучание всех остальных, и хочет определить что нужно
делать с каждой из ненастроенных струн (натянуть или ослабить).
Помогите Васе выяснить это.
Формат входного файла
Во входном файле содержится строка из 5 символов, описывающая звучание соседних струн относительно друг друга.
i-ый символ входной строки показывает как звучит (i + 1)-ая струна относительно i-ой, а именно:
< (ASCII 60) — (i + 1)-ая струна, зажатая на соответствующем ладу, звучит ниже открытой i-ой;
= (ASCII 61) — (i + 1)-ая струна, зажатая на соответствующем ладу, звучит в унисон с открытой i-ой;
> (ASCII 62) — (i + 1)-ая струна, зажатая на соответствующем ладу, звучит выше открытой i-ой.
Формат выходного файла
В выходном файле должна содержаться строка из 5 символов, описывающая действия, которые требуется
произвести для настройки гитары. В i-ой позиции строке должен содержаться символ, описывающий действие
над (i + 1)-ой струной:
X командный чемпионат Санкт-Петербурга по программированию - V Открытая Кировская командная олимпиада
Ограничение времени:
2 сек
Входной файл:
a.in
Ограничение памяти:
8 Мб
Выходной файл:
a.out
Условие
Одна из команд-участниц олимпиады решила вернуться домой на электричках.
При этом ребята хотят попасть домой как можно раньше.
К сожалению, не все электрички идут от города, где проводится олимпиада, до станции,
на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции,
останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях,
мимо которых они идут).
Все станции на линии пронумерованы числами от 1 до N.
При этом станция номер 1 находится в городе, где проводится олимпиада,
и в момент времени 0 ребята приходят на станцию.
Станция, на которую нужно попасть ребятам, имеет номер E.
Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время,
за которое ребятам удастся добраться домой.
Формат входного файла
Во входном файле записаны сначала числа N и E.
Затем записано число M, обозначающее число рейсов электричек.
Далее идет описание M рейсов электрички.
Описание каждого рейса электрички начинается с числа Ki — количества станций,
на которых она останавливается, а далее следует Ki пар чисел,
первое число каждой пары задает номер станции, второе — время
(время выражается целым числом из диапазона от 0 до 109).
Станции внутри одного рейса упорядочены в порядке возрастания времени.
В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.
Формат выходного файла
В выходной файл выведите одно число - минимальное время,
когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они
добраться не смогут, выведите -1.
Математик Николай Николаевич очень любит красивые числа.
Причем красивым он считает такое число, запись которого
начинается с единицы, далее следуют несколько нулей, и заканчивается опять единицей.
Его коллега Юрий Александрович считает,
что если такое красивое число возвести в некоторую степень, то оно станет еще лучше.
Николай Николаевич сомневается, но хочет проверить это.
Вдруг получившиеся числа понравятся ему больше!
Так как вручную возводить в степень тяжело,
а в программировании он разбирается не так хорошо, как в математике,
вам придется ему помочь.
Формат входного файла
Во входном файле находятся два целых числа: NK, где
N — количество нулей в записи числа,
K — степень, в которую нужно возводить число.
Таким образом, если входной файл содержит 3 5,
это значит, что нужно число 10001 возвести в пятую степень.
Обратите внимание, что если указано 0 нулей, подразумевается число 11, а не 1.
Формат выходного файла
В выходном файле должно содержаться заданное число, возведенное в заданную степень.
Пришла осень, каникулы закончились, и Чебурашке снова нужно идти в школу.
Он заранее готовился к этому: накупил карандашей, ручек, тетрадей.
Среди покупок, кроме обычных тетрадей, были также и двойные,
каждая из которых предназначена сразу для двух предметов.
Каждый день Чебурашке нужно брать с собой тетради для всех предметов,
которые будут преподаваться в его классе в этот день.
Тетради тяжелые, а носить лишний вес в школу не хочется.
Поэтому он пытается распределить предметы по тетрадям таким образом,
чтобы за неделю переносить наименьший возможный вес.
Помогите ему это сделать.
У Чебурашки есть NS одинарных и ND двойных тетрадей.
Все одинарные тетради имеют вес WS, а все двойные — вес WD.
Чебурашка учится N дней в неделю.
Он изучает M предметов, пронумерованных от 1 от M.
Вес, который Чебурашке придётся перенести за один день,
равен сумме весов всех тетрадей, которые он должен будет взять.
Требуется написать программу, вычисляющую наименьший возможный вес,
который Чебурашке придется перенести в сумме за все дни недели.
Формат входного файла
Во входном файле содержатся числа NMNSNDWSWD.
Далее следует расписание, состоящее из N дней.
Каждый день описывается одной строкой.
В начале строки содержится Ki — число уроков в i-ый день,
за которым следует Ki чисел — номера предметов.
Все числа во входном файле целые.
Формат выходного файла
В выходном файле должно содержаться единственное число — минимальный возможный вес.
Марсианская федерация автогонок ввела стандарт публикации результатов квалификационных заездов.
Согласно этому стандарту, стартовая решетка любого гран-при имеет вид таблицы, составленной по
определенным правилам. Правила оказались слишком сложными для хозяев автодромов, и они
попросили Вас написать программу для вывода этой таблицы.
В квалификационную сессию допускается N участников.
На марсианских гоночных трассах каждый стартовый ряд состоит из M позиций,
схема расположения которых на трассе такова:
Первая позиция находится в левой части трассы на уровне стартовой линии.
Внутри одного стартового ряда каждая последующая позиция находится правее и
дальше предыдущей на фиксированное расстояние.
Каждый следующий стартовый ряд формируется путем параллельного переноса предыдущего.
Из-за несоответствия некоторых гоночных болидов регламенту на старт выходят лишь
K ≤ N участников, при этом все они сохраняют свои стартовые позиции.
Правила публикации таблицы выглядят следующим образом:
Таблица разбита на блоки описания стартовых рядов.
Блоки разделены строкой из символов '=' (ASCII 61) во всю ширину таблицы.
Перед описанием ряда во всю ширину таблицы выводится заголовок — номер ряда и фраза 'starting line'.
После заголовка выводится строка из символов '-' (ASCII 45) и '+' (ASCII 43)
во всю ширину таблицы.
Далее следует информация о стартующих гонщиках данного ряда,
для ее вывода используются M строк и M столбцов.
Если гонщик занимает i-ое место в данном ряду, то его имя должно быть напечатано
на i-ой строке i-го столбца, если же гонщика не допустили к гонке, то эта ячейка пуста.
Если в ряду не оказывается ни одного гонщика, то блок с описанием этого ряда опускается.
Столбцы внутри ряда разделяются символами '|' (ASCII 124).
Граница всей таблицы состоит из символов '#' (ASCII 35).
Имена гонщиков и заголовки рядов выравниваются по центру с помощью пробелов.
Если строгого выравнивания достичь невозможно, то отступ слева должен быть на 1 меньше отступа справа.
Имена гонщиков и заголовки рядов отделяются от границ минимум одним пробелом слева и справа.
Все столбцы таблицы имеют равную, минимально возможную ширину.
Никакое имя гонщика не начинается с пробела и не заканчивается им.
Формат входного файла
Во первой строке входного файла содержатся числа K и M, в следующих 2 * K строках
для каждого гонщика указано имя, а затем стартовая позиция.
Список отсортирован по возрастанию позиций.
Формат выходного файла
В выходном файле должна содержаться таблица с
описанием стартовой решетки по марсианским правилам.
Ограничения
1 ≤ N, M, K ≤ 100
Длина строки с именем гонщика не превосходит 100 символов.
Примеры тестов
№
Входной файл (input.txt)
Выходной файл (output.txt)
1
1 1
Michael Schumacher
1
######################
# 1 starting line #
#--------------------#
# Michael Schumacher #
######################
В тридевятом царстве жила-была Баба Яга. А в тридесятом царстве жил-был Кощей Бессмертный.
Однажды Баба Яга решила слетать в гости к Кощею в своей ступе.
Баба Яга будет лететь строго в плоскости, перпендикулярной земле.
Пусть тридевятое царство, в котором живёт Баба Яга, находится в точке (x = a, y = 0),
а тридесятое царство, в котором живёт Кощей Бессмертный, находится в точке (x = b, y = 0),
a < b.
Между этими царствами гористая местность. Профиль гор в плоскости полёта Бабы Яги задаётся
ломаной с координатами вершин (x = xi, y = yi), i = 1, 2, ..., N,
a = x1 < x2 < ... < xN = b, yi ≥ 0, y1 = yN = 0.
Ступе будет сообщена некоторая начальная скорость, после чего она полетит в поле
тяжести Земли по параболе (сопротивлением воздуха пренебрегаем).
Баба Яга хочет попасть в точности в тридесятое царство, чтобы потом не пришлось идти пешком
или запускать ступу ещё раз.
Баба Яга должна пролететь так, чтобы не врезаться в гору.
Баба Яга страшно боится высоты, поэтому она хочет, чтобы максимальная высота, на которую
она поднимется, была минимальной.
Напишите программу для вычисления минимально возможной максимальной высоты.
Формат входного файла
Входной файл содержит целое число N.
Далее следуют N пар целых чисел xiyi.
Числа a и b определяются так: a = x1, b = xN.
Формат выходного файла
Требуется вывести в выходной файл единственное вещественное число — минимально возможную
максимальную высоту — с точностью до 4-х знаков после запятой.
Ограничения
3 ≤ N ≤ 1000
0 ≤ a = x1 < x2 < ... < xN = b ≤ 1000
0 ≤ yi ≤ 1000, y1 = yN = 0
Примеры тестов
№
Входной файл (input.txt)
Выходной файл (output.txt)
1
3
1 0
2 1
3 0
1.0000
2
3
1 0
2 1
4 0
1.1250
3
4
2 0
3 9
4 5
6 0
12.0000
Задача N. Езда по тротуарам на велосипеде во Владивостоке
≡
Один владивостокский Программист очень любит ездить не велосипеде.
Его маршрут на карте имеет вид ломаной с N вершинами
в плоской прямоугольной системе координат.
Владивосток — большой город! Потеряться в нем легко, особенно на велосипеде.
К счастью, у Программиста с собой карта с маршрутом, а велосипед имеет
счётчик пройденного пути.
Исходя из этих данных, помогите найти текущие координаты программиста.
Формат входного файла
Во входном файле в содержится целое число N,
за которым идёт действительное L — текущий показатель счётчика.
Далее расположены N пар целочисленных координат xiyi — вершины маршрута.
Гарантируется, что L не превышает длины маршрута.
Некоторые вершины ломаной, в том числе идущие одна за другой, могут совпадать.
Формат выходного файла
Выведите два действительных числа — координаты искомой точки
с точностью до трех знаков после запятой.
Обычно последний урок в четверти посвящён определению четвертных оценок.
Четвертная оценка школьника вычисляется как округлённое до ближайшего целого
среднее арифметическое всех его оценок в течение четверти.
Например, Вася, получивший в течение четверти оценки
3, 4, 2, 3, 3, 5, будет иметь среднюю оценку 20 / 6 = 3.3333...
и получит итоговую оценку 3.
Средние оценки 1.5, 2.5, 3.5 и 4.5 округляются
до 2, 3, 4 и 5 соответственно.
Кроме того, на последнем уроке каждый школьник может один раз вызваться отвечать,
чтобы попытаться улучшить свою четвертную оценку.
Конечно, такое улучшение возможно только для тех,
у кого средняя оценка достаточно близка к следующему баллу.
Например, если Вася на последнем уроке сумеет получить пятёрку,
то его средняя оценка станет равна 25 / 7 = 3.571... и итоговая оценка
повысится до 4 баллов.
По данному списку учеников и их оценок требуется
определить, кто из них имеет шанс улучшить четвертную оценку
на последнем уроке.
Формат входного файла
Входной файл содержит целое число N — количество учеников,
за которым следует N списков оценок.
Список оценок i-го ученика состоит
из целого числа Qi — количества оценок,
за которым следуют Qi целых чисел в диапазоне от 1 до 5 —
сами оценки.
Формат выходного файла
Выходной файл должен содержать количество учеников,
которые могут улучшить свои оценки.
В олимпиаде приняли участие N школьников. Вам известно количество баллов, которое набрал
каждый из них. Сколько баллов получил участник, занявший третье c конца место? Если несколько участников
набрали одинаковое количество баллов, то они все равно некоторым образом распределены по местам,
то есть невозможно разделить место.
Формат входного файла
Во входном файле содержится число N, за которым следует N чисел ai - баллы, набранные участниками.
Формат выходного файла
В выходной файл выведите единственное число - количество баллов, которое набрал участник, занявший
третье с конца место.
Недавно на кружке по программированию Петя узнал об обходе в глубину.
Обход в глубину используется во многих алгоритмах на графах. Петя сразу
же реализовал обход в глубину на своих любимых языках программирования —
паскале и си.
var
a: array [1..maxn, 1..maxn]
of boolean;
visited: array [1..maxn]
of boolean;
procedure dfs(v: integer);
var
i: integer;
begin
writeln(v);
visited[v] := true;
for i := 1 to n do begin
if a[v][i] and
not visited[i] then
begin
dfs(i);
writeln(v);
end;
end;
end;
procedure graph_dfs;
var
i: integer;
begin
for i := 1 to n do
if not visited[i] then
dfs(i);
end;
int a[maxn + 1][maxn + 1];
int visited[maxn + 1];
void dfs(int v) {
printf("%d\n", v);
visited[v] = 1;
for (int i = 1; i <= n; i++) {
if ((a[v][i] != 0) &&
(visited[i] == 0)) {
dfs(i);
printf("%d\n", v);
}
}
}
void graph_dfs() {
for (int i = 1; i <= n; i++) {
if (visited[i] == 0) {
dfs(i);
}
}
}
Петина программа хранит граф с использованием матрицы смежности в массиве "a"
(вершины графа пронумерованы от 1 до n).
В массиве "visited" помечается, в каких вершинах обход в глубину уже побывал.
Петя запустил процедуру "graph_dfs" для некоторого неориентированного графа G
с n вершинами и сохранил ее вывод.
А вот сам граф потерялся. Теперь Пете интересно, какое максимальное количество
ребер могло быть в графе G. Помогите ему выяснить это!
Формат входного файла
Первая строка входного файла содержит два целых числа: n и l —
количество вершин в графе и количество чисел в выведенной последовательности.
Следующие l строк по одному числу —
вывод Петиной программы. Гарантируется, что существует хотя бы один граф,
запуск программы Пети на котором приводит к приведенному во входном файле
выводу.
Формат выходного файла
На первой строке выходного файла выведите одно число m — максимальное
возможное количество ребер в графе. Следующие m строк должны содержать по два
целых числа — номера вершин, соединенных ребрами. В графе не должно быть
петель и кратных ребер.
Сотрудники Научно-исследовательского института алгебры, геометрии и анализа
(НИИ АГА) по заказу метеорологов разработали новый вид осадкомерных стаканов
с основанием в виде прямого угла.
Преимущество такого стакана перед обычным круглым очевидно: его можно
закрепить в любом месте и на любой почве, не боясь, что он опрокинется.
Задача наблюдателя-метеоролога — после каждого дождя находить установленные
в определённых местах стаканы и измерять количество попавшей в них воды.
Сотрудникам НИИ АГА нужна программа, принимающая на вход угол наклона стакана
α и уровень воды в стакане h и вычисляющая площадь части прямого
угла, занятой водой.
Формат входного файла
Входной файл содержит вещественные числа α h.
Угол задан в градусах. Уровень воды задан в миллиметрах.
Формат выходного файла
Требуется вывести вещественное число — площадь части прямого угла, занятой
водой, в мм2.
Ответ вывести с точностью не менее 5-ти знаков после запятой.
Гистограмма (или столбчатая диаграмма) — это способ графического изображения набора чисел,
при котором каждое число изображается прямоугольным столбцом с высотой, пропорциональной
значению числа.
По данным целым числам a1, a2, …, aN
требуется построить гистограмму. Гистограмма должна состоять из N столбцов,
i-й столбец должен изображаться прямоугольником высотой ai и шириной в 3 символа.
Столбцы должны быть:
заполнены символом '#' (ASCII 35),
ограничены сверху и снизу символами '-' (ASCII 45),
ограничены слева и справа символами '|' (ASCII 124),
ограничены по углам символами '+' (ASCII 43).
Промежуток между столбцами, а также поля слева, справа и сверху гистограммы должны составлять один символ.
В основании (нижней строке) гистограммы промежутки и поля должны изображаться символом '-' (ASCII 45),
все остальные промежутки и поля — символом '.' (ASCII 46).
Формат входного файла
Входной файл содержит число N, за которым следуют числа a1, a2, …, aN.
Формат выходного файла
Выходной файл должен содержать max(ai) + 3 строк длиной 6N + 1
символов каждая — изображение гистограммы.
Дана последовательность из N целых чисел. Найдите любую из ее подпоследовательностей,
сумма элементов которой равна w, либо установите,
что искомой подпоследовательности не существует.
Формат входного файла
Во входном файле находятся числа N и w, а за ними следует последовательность
из N целых чисел ai.
Формат выходного файла
Если искомая подпоследовательность существует, выведите N чисел 0 или 1, разделенных пробелами.
Единица на позиции i означает, что элемент последовательности ai принадлежит найденной
подпоследовательности, 0 означает обратное. В противном случае выведите − 1.
Ваша программа должна вывести в выходной файл изображение гирлянды.
Гирлянда состоит из N звеньев, каждое из которых имеет вид ромба, состоящего
из символов '#' (ASCII 35) для нечётных звеньев,
либо '*' (ASCII 42) — для чётных звеньев.
Размер i-го звена задаётся целым числом Ai.
Каждая сторона ромба размером Ai состоит из Ai + 1 символа.
Гирлянда должна быть изображена на фоне прямоугольника, заполненного символами '.' (ASCII 46).
Каждое звено, начиная со второго, расположено вертикально
под предыдущим и "сцеплено" с ним, как изображено в примере.
Формат входного файла
Во входном файле находится целое число N, за которым следует N чисел A1…AN —
размеры звеньев.
Формат выходного файла
Выходной файл должен содержать изображение гирлянды.
В бесконечном квадратном парке деревья образуют квадратную решётку с шагом 1 метр.
Часть парка было решено оградить забором, который представляет собой многоугольник с
заданными координатами вершин. Деревья, которые в точности попадают на
вершины или стороны многоугольника, придётся срубить. Необходимо выяснить количество таких деревьев.
Программа должна, получив на входе число вершин многоугольника N и их
целочисленные координаты (x1, y1), …,
(xN, yN), определить количество точек с целочисленными
координатами, лежащих на границе этого многоугольника.
Стороны многоугольника не самопересекаются.
Формат входного файла
Входной файл содержит число N, за которым следует N пар координат
x1y1 … xNyN
Формат выходного файла
Выходной файл должен содержать единственное число — количество точек.
Ограничения
3 ≤ N ≤ 1000,
0 ≤ xi, yi ≤ 107,
исходные данные таковы, что результат не превосходит 231−1.
Дан массив A, состоящий из N неотрицательных целых чисел.
Назовём правым (левым) соседом нулевого элемента ближайший к
нему справа (слева) ненулевой элемент.
Требуется построить массив B, который получается из массива A заменой
каждого нулевого элемента на его ближайшего соседа в массиве A.
Если оба соседа отсутствуют либо расстояния до них равны,
замена не производится (элемент остаётся нулевым).
Формат входного файла
Входной файл содержит число N, за которым следует N целых чисел — элементы массива A.
Формат выходного файла
Выходной файл должен содержать N целых чисел — элементы массива B.
В армии некоторого государства построение солдат по росту производится следующим образом:
сначала выбирается самый высокий солдат, после чего он несколькими последовательными переменами
местами с непосредственными соседями передвигается в начало строя. Далее выбирается самый
высокий из оставшихся и ставится на второе место и т. д. Если в строю несколько солдат имеют наибольший
рост, то из них выбирается тот, который стоит ближе к началу строя.
Один талантливый полководец заметил, что построение таким образом занимает слишком много времени,
и предложил своему начальнику новый способ решения этой задачи. Начальник, будучи человеком
консервативным, усомнился в способе, предложенным своим подчиненным, и предложил простой
способ проверки: построить солдат старым образом, переписать имена солдат в порядке обхода
строя от самого высокого к самому низкому, после чего повторить эту процедуру для нового способа
и сравнить результаты.
В результате выполнения многократных проверок начальник убедился в правоте своего подчиненного.
Реализуйте один из способов, которым мог решить задачу талантливый полководец.
Формат входного файла
Первая строка содержит число солдат N. В последующих строках содержатся N описаний каждого солдата:
рост Ri и имя Si.
Формат выходного файла
Выходной файл должен содержать N строк, в каждой из которых содержится имя очередного солдата из
строя, упорядоченного по росту от большего к меньшему.
Ограничения
1 ≤ N ≤ 1000000 ≤ Ri ≤ 1000000 (действительное число)
Длина имени солдата не превосходит 255 символов.
Один из интернет-провайдеров решил опробовать новую технологию — передачу данных по линиям электропередач.
Для этого на подстанциях были установлены N ретрансляторов.
Рассмотрим i-й ретранслятор и провод от него к другому ретранслятору.
Количество ретрансляторов, сигнал от которых к i-му проходит через рассматриваемый провод,
назовем нагрузкой на данный провод для i-го ретранслятора.
Максимум из нагрузок на все провода для i-го ретранслятора
называется нагрузкой на данный ретранслятор.
Известно, что по проводам электросети сигнал может пройти
от одного ретранслятора к другому единственным образом.
Требуется написать программу, которая по заданной схеме электросети
подсчитает нагрузку на каждый ретранслятор.
Формат входного файла
Во входном файле содержится число N — количество ретрансляторов, за которыми
следуют N − 1 пар чисел uivi, означающих,
что i-ый провод соединяет ретрансляторы ui и vi.
Формат выходного файла
В выходном файле должно содержаться N чисел a1a2… aN,
где ai — нагрузка на i-ый ретранслятор.
Мальчик Петя придумал страшного Бармаглота, хватающего детей.
Когда Петя зашёл в свою комнату, чтобы ложиться спать, он увидел, что одеяло на кровати
очень похоже на Бармаглота. Требуется по заданной форме одеяла и форме Бармаглота
определить, может ли Бармаглот поместиться под одеялом, и, соотвественно,
следует ли Пете испугаться и заплакать или спокойно пойти спать.
Рассмотрим правильный треугольник. Разделим каждую его сторону на 
