В последнее время крупные магазины все чаще стали предлагать своим покупателям различные дисконтные программы. И если в некоторых магазинах условия получения скидки запутанны и сложны, то в гипермаркете «Скип» все предельно ясно: каждый K-й товар в чеке достается покупателю бесплатно.
Студент всегда не прочь сэкономить. Но голова студента забита совсем другими вещами, поэтому он вспоминает о действующей системе скидок только тогда, когда все его N товаров уже выложены на конвейерную ленту перед кассой.
Кассир берёт товары с ленты по очереди. В этот момент студент может попросить кассира пока не пробивать взятый им товар, и переложить его в конец ленты. Кассир и вся очередь терпеливо ждут, пока студент переложит товар в конец ленты, после чего ситуация повторяется снова. Если студент решает не перекладывать товар, то он пробивается в чек и исчезает с ленты. Если какой-то товар студент уже перекладывал, то, чтобы не нервировать очередь за собой, он в любом случае разрешает кассиру пробить его в чек. Известно, что все товары, приобретаемые студентом, различны, хотя и могут иметь одинаковую стоимость.
Рассмотрим пример. Пусть стоимости товаров на ленте в порядке от ближайшего к кассиру до самого дальнего составляют 4, 1, 3 и 2 рубля, соответственно. Тогда при K = 2 студенту придется заплатить всего 7 рублей. Однако если бы товары лежали на конвейерной ленте в порядке 1, 3, 2, 4, то студент заплатил бы всего 3 рубля. Чтобы из первой ситуации получить вторую, студент может переложить товар стоимостью 4 рубля в конец ленты, сэкономив таким образом 4 рубля.
Зная цены товаров, их первоначальный порядок на ленте, а так же число K, помогите студенту определить минимальное количество денег, необходимое для приобретения всех товаров.
В первой стоке заданы числа N (1 ≤ N ≤ 500) и K (1 ≤ K ≤ N ≤ 500).
В следующей строке через пробел задано N чисел Ai (1 ≤ Ai ≤ 106) — стоимости товаров, приобретаемых студентом, в первоначальном порядке от ближайшего к кассиру до самого дальнего.
Выведите единственное число — минимальное сумму денег, за которую студент может приобрести все товары.
4 2
4 1 3 2
3
7 3
1 4 1 2 5 1 1
6
9 3
1 1 100 1 100 1 1 100 1
6
В последние годы всё более популярными становятся двигатели, работающие на солнечных батареях. В ближайшие дни даже планируется организовать полёт самолёта вокруг земного шара с использованием только солнечной энергии!
Подготовка кругосветного перелёта самолёта на солнечных батареях включает в себя ряд испытательных полётов. Во время каждого испытательного полёта самолёт стартует из некоторого аэродрома Ai и по кратчайшему маршруту летит к аэродрому Ai + 1. Таким образом, за исключением первого полёта самолёт всегда вылетает из аэродрома, в котором закончился предыдущий испытательный полёт.
Известно, что аэродромы, на которых проводятся испытательные полёты, расположены строго в линию от 1-го до N-го. Для каждой пары соседних аэродромов, согласно метеоусловиям и расстоянию между ними, известна дельта энергии Δ Qi, i + 1, которая затрачивается (если Δ Qi, i + 1 < 0) или приобретается (если Δ Qi, i + 1 ≥ 0) самолётом при перелете между ними. При перелёте между любой парой аэродромов u и v, не являющихся соседними, дельта энергии определяется по формуле:
Вам необходимо найти любую последовательность A из K номеров различных аэродромов такую, что сумма модулей дельт энергии S при перелётах между аэродромами в порядке, заданном этой последовательностью, была наименьшей.
В первой строке задано общее число N (2 ≤ N ≤ 105) аэродромов и длина K (2 ≤ K ≤ N) искомой последовательности аэродромов.
Во второй строке заданы N - 1 целых чисел Δ Q1, 2, Δ Q2, 3, ..., Δ Qn - 1, n — дельты энергии при перелёте между парами соседних аэродромов (|Δ Qi, i + 1| ≤ 106).
В первой строке выведите минимально возможную сумму S.
Во второй строке выведите K чисел через пробел — искомую последовательность A номеров аэродромов (нумерация с 1).
Если решений существует несколько, выведите любое.
4 3
-3 2 10
3
2 3 1
6 4
-3 2 1 -2 -1
2
2 6 5 3
Чтобы повысить интерес студентов к своему предмету, некоторые преподаватели придумывают нестандартные творческие задания. Такие задания нравятся студентам гораздо больше скучных лекций.
В начале одной из лекций преподаватель написал мелом на доске два числа N и X. После этого он объявил студентам, что отпустит их с лекции, как только они назовут все числа Y в диапазоне 0 ≤ Y < 2N такие, что количество единиц в двоичном представлении побитовой суммы 
будет нечетным.
Поначалу студенты с энтузиазмом участвовали в выполнении задания, выкрикивая с мест ответы. Однако очень скоро они поняли, что уйти раньше времени с лекции не получится, потому что в задании кроется какой-то подвох...
Когда энтузиазм угас вовсе и над аудиторией повисла гробовая тишина, преподаватель пообещал зачёт автоматом тому, кто скажет, сколько всего существует подходящих значений Y в заданных ограничениях.
Помогите студентам решить эту задачу и сможете автоматом получить зачтённую задачу!
В единственной строке задаются числа N (1 ≤ N ≤ 100) и X (0 ≤ X ≤ 1018).
Выведите количество подходящих значений Y по модулю 109 + 3.
2 3
2
5 17
16
Умудренные опытом студенты знают, что гораздо чаще не студенты избегают встреч со строгими профессорами, а профессора пытаются скрыться от назойливых студентов-должников.
Территория университета представляет собой N зданий, связанных между собой N - 1 дорогами так, что из каждого здания можно добраться до любого другого.
Группа студентов, задолжавшая несколько лабораторных работ, пытается разыскать профессора. Профессор так увлечён работой, что никогда не покидает территорию университета, однако по слухам каждый день он двигается по одному из K маршрутов, представляющих собой кратчайший путь между некоторой парой зданий Xi и Yi.
План состоит в том, чтобы ежедневно выбирать один из возможных маршрутов профессора и расставлять своих наблюдателей возле всех зданий, через которые проходит маршрут. Однако прежде чем приступить к реализации плана, студенты решили посчитать, сколько непересекающихся ни в одном здании пар маршрутов есть среди K маршрутов профессора.
В первой строке задано число N (1 ≤ N ≤ 105) зданий на территории университета.
В следующих N - 1 строках задаются дороги в виде пар номеров зданий Ui и Vi (1 ≤ Ui, Vi ≤ N).
В следующей строке задаётся число возможных маршрутов профессора K (1 ≤ K ≤ 105).
В следующих K строках задаются маршруты профессора в виде пар номеров зданий Xi и Yi (1 ≤ Xi, Yi ≤ N, Xi ≠ Yi) — начальной и конечной точек i-го маршрута.
Выведите единственное число — искомое количество пар непересекающихся ни в одном здании маршрутов профессора.
5
1 2
2 3
2 4
4 5
4
1 3
4 1
4 5
2 3
2
Студент знает, что число 42 — это и есть ответ на главный вопрос жизни, вселенной и всего такого. Поэтому когда он видит в учебнике некоторое число N, он тут же пытается изменить его так, чтобы оно делилось на 42. При этом какое бы число ему ни попалось, внутренний голос заставляет его всегда изменять ровно 2 цифры в этом числе.
Зная исходное число N Вам необходимо найти количество различных чисел, которые могут получиться в результате изменений, сделанных студентом. Все действия производятся в десятичной системе счисления.
В единственной строке задается число N (10 ≤ N ≤ 10100000).
Выведите искомое количество чисел.
43
2
100
7
Среди студентов очень популярна игра в спортивный "Что? Где? Когда?". Смысл игры заключается в том, что несколько соревнующихся команд последовательно отвечают на различные вопросы, используя логику, эрудицию, а зачастую и просто интуицию. Побеждает команда, давшая максимальное количество правильных ответов.
Студенческая команда, проигравшая важнейшую игру сезона, решила разобраться, что послужило причиной такого провала? Капитан команды резонно предположил, что главная ошибка — неправильный выбор стартового состава на игру и замен в процессе игры.
В команде играют N человек. При этом за игровым столом при обсуждении вопроса всегда должно находиться ровно K игроков. После каждого вопроса команда может либо оставить состав игроков за столом неизменным, либо сделать ровно одну замену — убрать из-за стола одного игрока, и посадить туда игрока, который не был за столом во время обсуждения предыдущего вопроса.
Известно, что команда гарантированно отвечает правильно на вопрос только в том случае, если все игроки за столом имеют правильные версии. Для каждого игрока известно, на какие вопросы у него есть правильная версия ответа, а на какие — нет. Вам необходимо определить такой стартовый состав на игру и последовательность замен, при которых команда гарантированно бы ответила правильно на все Q вопросов в игре.
В первой строке задано общее число N (1 ≤ N ≤ 100) игроков в команде, число игроков за столом K (1 ≤ K ≤ N) и количество вопросов Q (1 ≤ Q ≤ 1000).
В следующих N строках задаются описания игроков. Каждое описание содержит строку Si (|Si| = Q) из нулей и единиц, такую что если Si, j = 1, у i-го игрока есть правильная версия ответа на j-й вопрос, а если Si, j = 0 — правильной версии нет.
Если есть решение, гарантирующее правильные ответы команды на все Q вопросов, выведите в первой строке WIN.
Во второй строке выведите последовательность A (1 ≤ Ai ≤ N, |A| = K), состоящую из K номеров игроков, — стартовый состав команды, находящийся за столом при ответе на первый вопрос.
В третьей строке выведите количество замен Z.
В следующих Z строках в хронологическом порядке выведите описания производимых замен в формате Ti Xi Yi, где Ti (1 ≤ Ti ≤ Q - 1, Ti + 1 > Ti) — вопрос, после ответа на который производится замена; Xi — номер игрока, уходящего из-за стола; Yi — номер игрока, садящегося за игровой стол.
Если существует несколько решений, выведите любое.
Если решений не существует, выведите единственное слово FAIL.
4 3 7
1110111
0111111
1011111
1111100
WIN
1 3 4
3
1 3 2
2 1 3
5 4 1
2 2 4
1100
1010
FAIL
Многие преподаватели считают, что тестирование лабораторных работ, выполняемых студентами, совсем необязательно. Разве можно не поставить зачёт студенту, если у него есть отчёт с распечатанным программным кодом и какие-никакие теоретические познания? В конечном итоге студенты привыкают, что программный код совсем не обязательно отлаживать, и очень часто пытаются сдавать абсолютно неработоспособные программы.
В рамках одной из лабораторных работ от студента требовалось реализовать структуру данных, которая бы инициализировалась неубывающей последовательностью из N чисел, и поддерживала следующие типы запросов:
1. Удалить M-й элемент в порядке возрастания из последовательности.
2. Определить, какое число является K-м по возрастанию в текущей последовательности.
Вместо того чтобы изучить теорию и написать новую структуру, студент решил упростить себе задачу, поместив все элементы последовательности в обычный массив без изменений и реализовав ответы на запросы следующим образом:
1. Поменять местами M-й элемент массива с последним элементом массива, после чего удалить последний элемент из массива.
2. Вернуть K-й элемент массива.
Когда студент пришёл сдавать лабораторную работу, его ожидал неприятный сюрприз — преподавателя замещал аспирант кафедры, который много лет участвовал в соревнованиях по программированию и не принимает работы, не протестировав хотя бы минимальную функциональность.
Сегодня студентов, пришедших сдавать лабораторные работы, очень много, и поэтому аспирант вынужден тестировать каждую программу следующим образом: на вход подаётся некоторая последовательность чисел A, затем выполняется один запрос 1-го типа (выполняется условие 1 ≤ M ≤ N), а после него — один запрос 2-го типа (выполняется условие 1 ≤ K ≤ N - 1). Лабораторная работа считается зачтённой, если программа выдаст правильный ответ на выполненный запрос 2-го типа.
От однокурсников студент узнал последовательность чисел A, на которой выполняется тестирование всех программ, однако значения M и K узнать не удалось — аспирант выбирает их случайным образом равновероятно из всего множества допустимых значений.
Студент очень переживает, что ему придётся всё переделывать и идти на пересдачу, и поэтому просит Вас посчитать вероятность того, что ему удастся получить зачёт по лабораторной работе со своей программой.
В первой строке задаётся число N (2 ≤ N ≤ 105) — длина исходной последовательности A.
Во второй строке через пробел задаются N чисел исходной неубывающей последовательности A (|Ai| ≤ 106, Ai < = Ai + 1).
Все числа во входных данных целые.
Выведите вероятность успешной сдачи лабораторной работы студентом в виде десятичной дроби. Ваш ответ будет засчитан, если абсолютная или относительная ошибка не превысит 10 - 6.
3
1 2 2
1.0000000000
5
-1 2 2 3 3
0.8000000000