Катерина - учитель информатики. А ещё она болеет за футбольный клуб "Зенит". В честь очередной победы любимой команды, она хочет раскрасить компьютеры в своем кабинете в сине-бело-голубые цвета. Каждый компьютер нужно покрасить в один из трех этих цветов. Количество компьютеров, раскрашенных в каждый из цветов, должно быть ненулевым. Каждый компьютер имеет свой номер от 1 до n. Катерина хочет, чтобы после покраски выполнялись следующее правила:
Наибольший номер синего компьютера должен равняться количеству белых компьютеров;
Наибольший номер белого компьютера должен равняться количеству голубых компьютеров;
Наименьший номер голубого компьютера должен равняться количеству синих компьютеров.
Для указанного варианта раскраски укажите, будет ли он подходящим для Катерины.
Формат входных данных
Первая строка входного файла содержит натуральное число n - количество компьютеров в кабинете. Во второй строке расположено n символов из набора "w" (white, белый), "b" (blue, синий) и "с" (cyan, голубой) - порядок раскраски компьютеров с первого до n-го.
Формат выходных данных
Выведите "Yes" или "No" (без кавычек) - подойдет ли Катерине такой вариант раскраски.
Ограничения
3 ≤ n ≤ 25
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примерам
В первом примере 10 компьютеров. Третий - синий, четвертый, пятый и шестой - белые, остальные - голубые. Наибольший номер синего компьютера (3) равняется количеству белых компьютеров (3). Наибольший номер белого компьютера (6) равняется количеству голубых компьютеров (6). Наименьший номер голубого компьютера (1) равняется количеству синих компьютеров (1). Все цвета использованы, все условия выполнены.
Во втором примере среди компьютеров нет ни одного синего.
Ещё совсем недавно n городов осуществляли авиационное сообщение: из каждого города можно было прямым рейсом долететь в любой другой. Но теперь границы закрыты и самолеты летают только если оба города принадлежат одному государству. Определите количество отмененных рейсов.
Формат входных данных
Первая строка входного файла содержит натуральное число n - количество государств. Во второй строке через пробел расположено n чисел xi - количество городов в i-м государстве.
Формат выходных данных
Выведите одно неотрицательное целое число - количество отмененных рейсов.
Ограничения
1 ≤ n ≤ 105
1 ≤ xi ≤ 104
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при n = 1, получат не менее 10 баллов.
Пояснение к примеру
В примере имеется 3 государства, в которых 5 городов. Сначала было 10 рейсов между городами, после закрытия границ осталось 2. Отменено 8 рейсов.
Согласно новым санитарным нормам, все учащиеся в классе должны сидеть за одноместными партами в защитных кубах с длиной ребра 1 м., при этом расстояние между ними, а также между кубом и стеной, тоже должно быть не меньше 1 м. Центры кубов должны находиться в узлах прямоугольной решетки. В классе учится n учащихся. Какую минимальную площадь будет иметь прямоугольный кабинет, в котором можно усадить всех ребят в соответствии с новыми требованиями?
Формат входных данных
Единственная строка входного файла содержит натуральное число n.
Формат выходных данных
Выведите одно натуральное число - ответ на задачу.
Ограничения
1 ≤ n ≤ 1012
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Решения, верно работающие при 1 ≤ n ≤ 106, получат не менее 60 баллов.
Пояснение к примеру
В примере нужно найти минимальную площадь кабинета для 3 учащихся. Есть два варианта размещения парт (с точностью до поворота и отражений) - они приведены на рисунке. В одном их них площадь кабинета равна 25, в другом - 21. Выберем наименьшее из чисел.
Ура, теперь ЕГЭ по информатике будет проходить с использованием компьютера! Больше остальных рад Богдан - теперь он сможет на каждое задание написать программу, проверяющую точность его расчетов, чтобы обезопасить себя от случайных ошибок. А поскольку Богдан в совершенстве владеет динамическим программированием, он сможет написать не просто переборное решение, а гораздо более эффективное. Вот взять хотя бы подсчет количества решений логического уравнения x1→ x2→ x3→ ... → xn = 1. Долго ли, зная n, решить это задание? Богдан справился за пять минут. А Вы?
Формат входных данных
Единственная строка входного файла содержит натуральное число n.
Формат выходных данных
Выведите одно натуральное число - количество различных решений уравнения.
Ограничения
2 ≤ n ≤ 52
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В примере дано n = 2. Есть три решения уравнения x1→ x2 = 1, это (0, 0), (0, 1) и (1, 1).
Наташа и Валера очень любят историю (ещё они любят друг друга, но это уже совсем другая история). Как-то раз они заспорили - кто из них лучше знает исторические факты? Чтобы решить этот вопрос они придумали такую игру:
1) Берется очень длинное натуральное число.
2) Каждый игрок в свой ход выбирает с начала числа 1, 2, 3 или 4 цифры - номер года. При этом нельзя брать номер года, если он больше 2020 - историки занимаются прошлым и настоящим. Кроме того, нельзя брать номер года, если после него в строке идет цифра 0 - в этом случае соперник в свой следующий ход не сможет выбрать корректный номер года.
3) Игрок должен назвать любое историческое событие, произошедшее в выбранный им номер года и, если он не ошибся, стереть выбранные цифры с начала исходного числа и передать ход сопернику.
4) Игра продолжается до первой ошибки любого игрока или пока от числа ничего не останется. Игрок, последним сделавший правильный ход, побеждает.
5) Игроки ходят по очереди, первый ход делает Наташа.
Так уж получилось, что и Наташа, и Валера знают абсолютно все исторические факты и способны для любого номера года назвать любое их количество. Получается, что победителя игры можно определить исключительно по исходному числу! И вот здесь уже начинается ваша история...
Формат входных данных
Единственная строка входного файла содержит одно натуральное число n. Гарантируется, что в числе нет трех идущих нулей подряд.
Формат выходных данных
Выведите имя победителя игры - 'Natasha' или 'Valera' (без кавычек).
Ограничения
1 ≤ n ≤ 10100000
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В примере исходное n = 2002021. Наташа не может выбрать одну, две или четыре цифры, в этом случае оставшееся число будет начинаться с 0. Поэтому её единственный ход - выбрать 200, назвать любое событие, случившееся в двухсотый год и передать ход Валере с n = 2021. Валера не может выиграть в один ход - для этого ему нужно выбрать всё оставшееся число, но оно соответствует будущему году, поэтому он выберет номер года 20 или 202. Независимо от его выбора, Наташа выиграет ответным ходом.
Петя придумал новую функцию f(n, k), которую назвал обнулениечисла. Она возвращает наименьшее количество цифр некоторого натурального числа n, при обнулении которых сумма цифр числа станет равна k. Например при n = 1025 и k = 6 значение функции равно 1 - достаточно в исходном числе обнулить всего одну цифру и получить число 1005.
При обнулении разрешается менять и первую цифру исходного числа. Так, f(1025, 7) = 1 (можно получить число 0025). А вот значение функции f(1025, 4) не определено - Петя не может добиться обнулением цифр исходного числа сумму, равную 4. Аналогично, не определено значение функции f(1025, 9) - сумма цифр исходного числа меньше 9.
Помогите Пете для заданных n и k определить значение функции.
Формат входных данных
Единственная строка входного файла содержит два натуральных числа, записанных через пробел: n и k.
Формат выходных данных
Выведите одно неотрицательное целое число - значение функции. Если значение функции для исходной пары чисел не определено, выведите -1.
Ограничения
1 ≤ n ≤ 10100
1 ≤ k ≤ 109
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примерам
В первом примере достаточно обнулить две цифры и получить число 120450 (или 123006).
Во втором примере обнулять цифры не нужно, их сумма уже равна 15.
В третьем примере все цифры числа четные. Получить нечетную сумму обнулением невозможно.
Чем заняться летом? Да чем угодно! Можно ходить в лес за грибами и ягодами, купаться в речке, загорать под ярким солнцем, общаться с друзьями и ... готовиться к новому учебному году. Тимофею за d дней каникул нужно прочитать k книг. Для каждой i-й книги известны два параметра: xi - количество дней, необходимых для её чтения, и yi - условные единицы удовольствия, которое получит Тимофей после прочтения этой книги. Есть, правда, еще один вариант - всю книгу целиком можно не читать, а потратить 1 день и познакомиться с её содержанием в хрестоматии "Полное собрание всех книг на лето в кратком пересказе", естественно, не получив никакого удовольствия.
Помогите Тимофею определить наибольшее удовольствие от чтения за время каникул. Тимофей - мальчик ответственный, поэтому каждая книга из списка должна быть прочитана либо полностью, либо в кратком пересказе.
Формат входных данных
Первая строка входного файла содержит два натуральных числа, записанных через пробел: d и k. Во второй строке через пробел записаны k натуральных чисел xi. В третьей строке через пробел записаны k натуральных чисел yi.
Формат выходных данных
Выведите одно неотрицательное целое число - ответ на задачу.
Ограничения
1 ≤ k ≤ 100
k ≤ d ≤ 1000
2 ≤ xi, yi ≤ 100
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примерам
В первом примере первую и четвертую книги Тимофей прочтет в хрестоматии, потратив на это два дня и не получив удовольствия. Вторую, третью и пятую книги он прочтет целиком, потратив на это 2 + 4 + 2 = 8 дней и получив 9 + 4 + 5 = 18 единиц удовольствия. Всего на чтение потрачено 10 дней.
Во втором примере у Тимофея слишком мало времени - он не успеет прочитать полностью ни одной книги. Потратив два дня на хрестоматию, Тимофей не получит никакого удовольствия.
Наконец-то и в нашем городе открылся магазин популярной торговой сети Fix Price! Все товары в нём продаются по одной и той же цене, причем для привлечения покупателей маркетологи установили эту стоимость с точностью до копейки. Только вот эти монетки давно уже не звенят в наших с вами карманах, поэтому кассирам приходится округлять итоговую стоимость покупки до целого числа рублей по обычным правилам математического округления: если число копеек составляет от 0 до 49, то они отбрасываются, в противном случае к количеству рублей добавляется еще один, а число копеек сбрасывается до нуля.
Узнав эти правила, Тимофей вдруг понял, как можно сэкономить на покупке! Например, если один товар стоит 1 рубль 75 копеек (будем обозначать 1,75), а ему нужно купить шесть таких товаров, то можно разбить покупку на две части по три товара в каждой. В этом случае стоимость каждой части составит 1,75 × 3 = 5,25, причем на кассе у него возьмут только 5 рублей. Итого стоимость покупки составит всего 5 + 5 = 10 рублей, что гораздо выгоднее, чем оплатить сразу шесть товаров, ведь в этом случае придется заплатить 1,75 × 6 = 10,50 с округлением вверх до 11 рублей.
По заданной стоимости товара и их необходимому количеству определите сумму, которую заплатит Тимофей. Он может разбить покупку на любые составные части и оплатить каждую часть отдельно.
Формат входных данных
Первая строка входного файла содержит натуральное число n - количество товаров в покупке Тимофея. Во второй строке записана цена одного товара - число рублей r и копеек k, разделенных символом ".", причем число копеек всегда записано в формате двух цифр.
Формат выходных данных
Выведите одно натуральное число - количество рублей, которое оставит Тимофей в магазине.
Ограничения
1 ≤ n ≤ 1000
1 ≤ r ≤ 99
00 ≤ k ≤ 99
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В примере Тимофею выгодно разбить покупку на три части - пять товаров, три и еще три. За первую часть он заплатит 14 рублей, за вторую и третью по 8 рублей, итого 30 рублей. Единая покупка обошлась бы в 31 рубль.
