Петя и Вася — одноклассники и лучшие друзья, поэтому они во всём помогают друг другу. Завтра у них контрольная по математике, и учитель подготовил целых K вариантов заданий.
В классе стоит один ряд парт, за каждой из них (кроме, возможно, последней) на контрольной будут сидеть ровно два ученика. Ученики знают, что варианты будут раздаваться строго по порядку: правый относительно учителя ученик первой парты получит вариант 1, левый — вариант 2, правый ученик второй парты получит вариант 3 (если число вариантов больше двух) и т.д. Так как K может быть меньше чем число учеников N, то после варианта K снова выдаётся вариант 1. На последней парте в случае нечётного числа учеников используется только место 1.
Петя самым первым вошёл в класс и сел на своё любимое место. Вася вошёл следом и хочет получить такой же вариант, что и Петя, при этом сидя к нему как можно ближе. То есть между ними должно оказаться как можно меньше парт, а при наличии двух таких мест с равным расстоянием от Пети Вася сядет позади Пети, а не перед ним. Напишите программу, которая подскажет Васе, какой ряд и какое место (справа или слева от учителя) ему следует выбрать. Если же один и тот же вариант Вася с Петей писать не смогут, то выдайте одно число - 1.
В первой строке входных данных находится количество учеников в классе 2 ≤ N ≤ 109. Во второй строке — количество подготовленных для контрольной вариантов заданий 2 ≤ K ≤ N. В третьей строке — номер ряда, на который уже сел Петя, в четвёртой — цифра 1, если он сел на правое место, и 2, если на левое.
Если Вася никак не сможет писать тот же вариант, что и Петя, то выведите - 1. Если решение существует, то выведите два числа — номер ряда, на который следует сесть Васе, и 1, если ему надо сесть на правое место, или 2, если на левое. Разрешается использовать только первые N мест в порядке раздачи вариантов.
25
2
1
2
2 2
25
13
7
1
-1
В первом примере вариантов 2, поэтому наилучшее место для Васи находится сразу за Петей. Во втором примере Петя будет единственным, кто получит вариант 13.
Каждый тест в задаче оценивается отдельно. Программа, выдающая правильный ответ только на тесты из условия и тесты с ответом - 1, не оценивается. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются.
Подзадача 1. N ≤ 100. Оценивается из 52 баллов.
Подзадача 2. N ≤ 109. Оценивается из 48 баллов.
На день рождения маленький Ипполит получил долгожданный подарок — набор дощечек с написанными на них буквами латинского алфавита. Теперь-то ему будет чем заняться долгими вечерами, тем более что мама обещала подарить ему в следующем году последовательность целых неотрицательных чисел, если он хорошо освоит этот набор. Ради такого богатства Ипполит готов на многое.
Прямо сейчас юный исследователь полностью поглощён изучением хорошести строк. Хорошестью строки называется количество позиций от 1 до L - 1 (где L — длина строки), таких, что следующая буква в строке является следующей по алфавиту. Например, хорошесть строки "abcdefghijklmnopqrstuvwxyz" равна 25, а строки "abdc" — только 1.
Ипполит размышляет над решением закономерно возникающей задачи: чему равна максимально возможная хорошесть строки, которую можно собрать, используя дощечки из данного набора? Вы-то и поможете ему с ней справиться.
Первая строка ввода содержит единственное целое число N — количество различных букв в наборе (1 ≤ N ≤ 26). Обратите внимание: в наборе всегда используются N первых букв латинского алфавита.
Следующие N строк содержат целые положительные числа ci — количество букв соответствующего типа (1 ≤ ci ≤ 109). Таким образом, первое число означает количество букв "a", второе число задаёт количество букв "b" и так далее.
Выведите единственное целое число — максимально возможную хорошесть строки, которую можно собрать из имеющихся дощечек.
3
1
1
1
2
2
3
4
3
В первом тесте имеется по одной дощечке с каждой из 3 различных букв. Ответ 2 достигается на строке "abc"
Каждый тест в данной задаче оценивается отдельно. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются.
Подзадача 1. Во всех тестах данной группы ci ≤ 100. Данная подзадача оценивается из 40 баллов.
Подзадача 2. Во всех тестах данной группы ci ≤ 1 000 000. Данная подзадача оценивается из 30 баллов.
Подзадача 3. Во всех тестах данной группы ci ≤ 109. Данная подзадача оценивается из 30 баллов.
Летом Максим съездил в Летнюю Какую-то Школу, где, помимо учёбы, ему очень запомнилась игра «Шляпа», в которую он вместе с друзьями играл всю смену. Опишем правила игры, которых они придерживались. Обратите внимание: эти правила немного отличаются от общепринятых.
Изначально в шляпу помещают некоторое количество бумажек с написанными на них словами. После этого команды из двух человек по очереди и в случайном порядке начинают отгадывать слова - один член команды объясняет другому написанное на бумажке слово, не используя однокоренные. Если партнёр отгадывает его, то команде засчитывается одно очко, слово выкидывается, а команда достаёт из шляпы новое, если у неё ещё осталось время в этом раунде. Если команда не успевает отгадать очередное слово, то бумажка на которой оно написано, возвращается в шляпу, и ход передаётся какой-то случайной команде, возможно, той же самой. Игра продолжается, пока все слова из шляпы не будут отгаданы.
Теперь Максим провёл турнир для N команд из своей школы и должен определить победителя. Он неаккуратно вёл записи игры и не отмечал, сколько слов отгадала каждая из команд, зато он записывал в хронологическом порядке каждый раз, когда какая-либо команда доставала какую-либо бумажку из шляпы. Всего таких записей M, и они следуют в хронологическом порядке. Помогите Максиму восстановить по сделанным записям, сколько слов отгадала каждая из команд.
В первой строке дано количество команд N и количество попыток отгадать слова M (1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000). В следующих M строках сначала указывается номер ni команды, пытавшейся отгадать слово, а через пробел дано слово wi, написанное на бумажке. Номера команд лежат в диапазоне от 1 до N. Все слова wi состоят из строчных латинских букв и имеют ненулевую длину, не превосходящую 10 букв.
Выведите в одну строку N чисел, i-ое число должно равняться количеству слов, отгаданному i-ой командой.
2 3
1 hat
1 shirt
2 hat
1 1
3 2
1 mom
3 dad
1 0 1
В первом примере первая команда отгадала слово shirt, а вторая слово hat.
Каждый тест в данной задаче оценивается отдельно. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются.
Подзадача 1. 1 ≤ N ≤ 2000, 1 ≤ M ≤ 2000. Каждое слово встречается только один раз. Оценивается из 20 баллов.
Подзадача 2. 1 ≤ N ≤ 2000, 1 ≤ M ≤ 2000. Оценивается из 30 баллов.
Подзадача 3. 1 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000. Оценивается из 50 баллов.
Юный спортсмен Гамп собирается пробежать по дорожке, состоящей из клеток.
Бег происходит следующим образом: изначально Гамп занимает ногой на дорожке только клетки - A + 1, ..., 0, где A — длина стопы Гампа.
\)A = 2\(; до начала бега
Затем он делает шаг и занимает ногой только клетки B, ..., B - A + 1, где B — длина шага Гампа. После следующего шага он занимает только клетки 2B, ..., 2B - A + 1 и так далее. Другими словами, каждый раз занимаемая область сдвигается на B клеток вправо.
\)A = 2\(, \)B = 3\(; после первого шага
\)A = 2\(, \)B = 3\(; после второго шага
Непосредственно перед забегом выяснилось, что некоторые клетки дорожки были только что покрашены. Гамп не хочет отстирывать свои любимые кроссовки, поэтому он решил отступить на несколько клеток назад перед тем, как начать забег.
Гамп может отступить на любое количество клеток строго меньшее B (а может и вовсе не отступать), после чего начать забег по описанным выше правилам.
\)A = 2\(, \)B = 3\(; отступ — 2 клетки; до начала бега
\)A = 2\(, \)B = 3\(; отступ — 2 клетки; после первого шага
\)A = 2\(, \)B = 3\(; отступ — 2 клетки; после второго шага
Помогите Гампу выбрать отступ, начав с которого он наступит на минимальное количество покрашенных клеток.
В первой строке содержатся два целых числа A и B — длины стопы и шага Гампа соответственно (1 ≤ A ≤ B ≤ 200 000).
Во второй строке содержится единственное целое число N — количество покрашенных клеток (1 ≤ N ≤ 200 000).
В третьей строке содержатся N целых чисел — номера покрашенных клеток в возрастающем порядке. Все номера не меньше 1 и не превосходят 109.
Выведите два числа — на сколько клеток нужно отступить Гампу, чтобы наступить на минимально возможное количество покрашенных клеток, и это количество соответственно.
Если правильных ответов несколько, выведите любой из них.
2 3
2
2 5
2 0
1 5
9
1 2 3 4 5 6 7 8 9
0 1
В первом примере возможны следующие варианты:
\)A = 2\(, \)B = 3\(; отступ — 0; наступил на две покрашенные
\)A = 2\(, \)B = 3\(; отступ — 1; наступил на две покрашенные
\)A = 2\(, \)B = 3\(; отступ — 2; не наступил на покрашенные
Во втором примере отступать не нужно:
\)A = 1\(, \)B = 5$; отступ — 0; наступил на одну покрашенную
Каждый тест в данной задаче оценивается отдельно. Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются.
Подзадача 1. B, N ≤ 100. Номера покрашенных клеток не превосходят 100. Оценивается из 20 баллов.
Подзадача 2. B, N ≤ 1000. Оценивается из 20 баллов.
Подзадача 3. B, N ≤ 200 000. Номера покрашенных клеток не превосходят 200 000. Оценивается из 30 баллов.
Подзадача 4. B, N ≤ 200 000. Оценивается из 30 баллов.
В известной сети гипермаркетов Heap-Hop ежегодно проводится следующая акция.
В декабре при покупке любого товара стоимостью не меньше 1 000 руб., за каждую целую тысячу рублей в стоимости одного товара выдаётся купон номиналом в 500 руб. Например, если мы покупаем в декабре один товар стоимостью 1 001 руб., а второй — 2 999 руб., то получим купон в 500 руб. за первый и всего два купона за второй. В январе полученные купоны можно использовать для оплаты 20% стоимости уже всей покупки в целом. То есть вне зависимости от стоимости отдельных товаров, если в январе общая сумма покупки в нашем примере будет не меньше 7 500 руб., то 1 500 мы оплатим купонами, а если меньше, то мы не сможем использовать все купоны полностью. Но даже за покупку стоимостью меньше 500 руб. мы сможем получить скидку в 20%, отдав купон номиналом 500 руб.
Семья Бережливых давно присмотрела ряд товаров в одном из гипермаркетов этой сети. Зная условия акции, они решили распределить покупки на два месяца так, чтобы в итоге заплатить за все товары вместе как можно меньше. Младший сын Бережливых Иван взялся написать программу, которая и выдаст соответствующие рекомендации, но родители не уверены, что его программа будет находить минимально возможную сумму денег, которой можно обойтись при покупке всех необходимых товаров с учётом акции. Поэтому подобную программу предлагается написать вам.
В первой строке входных данных находится число N — количество товаров, которые хочет купить семья Бережливых. Во второй строке записаны через пробел целые положительные числа ci — цены товаров. Каждого товара необходимо купить ровно одну единицу, но стоимости различных товаров могут совпадать.
Выведите одно вещественное число — минимальное количество рублей, которым можно обойтись при оплате всей покупки с использованием акции. Обратите внимание, ответ всегда выражается целым количеством копеек.
2
1000 1000
1800.00
3
1000 2000 500
3000.00
2
1001 1002
1802.60
В первом примере мы покупаем любой из предметов в первый месяц и получаем купон на 500 рублей. Тем не менее при покупке второго предмета можно будет оплатить не более 20% стоимости, что составит 200 рублей.
Решение тестируется на основном наборе тестов только при прохождении всех тестов из условия. При этом тесты из условия не оцениваются.
Подзадача 1. 1 ≤ N ≤ 20, стоимость любого товара не превосходит 5 000. Оценивается из 40 баллов. Баллы начисляются только при прохождении всех тестов данной подзадачи. Решения, не прошедшие все тесты в этой подзадаче, дальше не тестируются.
Подзадача 2. 1 ≤ N ≤ 100, стоимость любого товара не превосходит 5 000. Оценивается из 30 баллов. Каждый тест оценивается отдельно.
Подзадача 3. 1 ≤ N ≤ 1 000, стоимость любого товара не превосходит 50 000. Оценивается из 30 баллов. Каждый тест оценивается отдельно.