Когда-то давно во Франции жил граф по имени Бутер де Бит. С момента, как он научился писать и рисовать, он прожил n лет и n - 1 зим. И с того самого момента он вёл дневник на длинной полоске пергамента, в котором описывал лета и зимы, свидетелем которых он был.
Каждое лето он записывал цифру от 0 до 9 , характеризующую, насколько солнечным было это лето. Зимы же граф Бутер описывал проще: если снега зимой было много, значит зима удалась, если снега было мало, значит зима вышла неудачной. Каждую удачную зиму он рисовал в своём дневнике снежинку после последней записанной цифры, а каждую неудачную он не рисовал ничего. Снежинка при этом выглядела следующим образом: * .
Много лет спустя некто Артур Бабаев нашел эту полоску пергамента. На нём были написаны n цифр, и между некоторыми из них были нарисованы снежинки, которые он воспринял как знак умножения. Он быстро посчитал получившееся число, но это было слишком просто для него.
Артур принадлежит к обществу Любителей Квантовой Механики и знает, что наша вселенная не единственна. Более того, в каждой параллельной вселенной жило по такому же графу Бутер де Биту, и единственное, в чём отличалось существование разных де Битов, это удачность зим, которые они переживали. А именно, каждая из 2 n - 1 последовательностей удачных/неудачных зим встречалась ровно в одной вселенной. Аналогичным образом в каждой вселенной существовало по Артуру, нашедшему этот самый лист пергамента и посчитавшему значение выражения на нём.
Артур из нашей вселенной очень захотел посчитать сумму чисел, полученную Артурами из всех вселенных. Так как это число может быть очень большим, он будет доволен, если узнает только остаток от его деления на 10 9 + 7 .
Заметим, что ни одного из Артуров не смутит ситуация, в которой один из образовавшихся на полоске сомножителей содержит ведущие нули. Например, полоска пергамента, на которой написана строка 01 * 02 , задаёт корректное выражение, значение которого равняется 2 .
Первая и единственная строка входных данных содержит последовательность из n ( 1 ≤ n ≤ 200 000 ) цифр без пробелов, записанную де Битами во всех вселенных.
Выведите остаток от деления суммы всех чисел, посчитанных Артурами из всех вселенных, на 10 9 + 7 .
В первом примере есть 2 2 = 4 вселенные, и, соответственно, 4 полоски из пергамента. На них написаны выражения 1 * 2 * 3 , 12 * 3 , 1 * 23 , 123 , значит, соответствующие Артуры вычислили результаты 6 , 36 , 23 и 123 , дающие в сумме 188 .
123
188
0102
124
Осенью в одной провинциальной средневековой общине на юго-востоке Уэльса проходит делёж собранного урожая яблок. Эта община имеет внутреннюю иерархию, согласно которой каждый из n человек имеет ранг, являющийся целым положительным числом от 1 до n , причём все люди имеют разные ранги.
Процесс дележа урожая проходит следующим образом:
- Все члены общины в произвольном порядке встают в круг, в центре которого находится куча с собранным урожаем.
- Затем выбирается человек, который будет брать полагающуюся ему часть урожая первым.
- Этот человек подходит к куче и набирает в свой мешок количество яблок, равное его рангу.
- Затем в соответствии с тем же правилом набирает урожай человек, находящийся по правую руку от первого, затем следующий за ним и так далее, пока урожай не закончится. При этом возможно, что до одного и того же человека очередь брать яблоки будет доходить несколько раз.
- Если в куче осталось меньше яблок, чем ранг очередного подошедшего к ней человека, то этот человек берёт все оставшиеся яблоки.
Вам стало интересно, насколько данная процедура дележа яблок является честной. Определите, какое минимальное количество яблок может оказаться у человека после участия в описанной процедуре.
В единственной строке находится два целых числа n и k ( 3 ≤ n ≤ 10 000 , 1 ≤ k ≤ 10 9 ) — число людей и число яблок соответственно.
Выведите единственное целое число — минимальное количество яблок, которые могут оказаться у человека в результате описанной процедуры.
В первом примере община состоит из трёх людей, а урожай состоит из восьми яблок. Рассмотрим, например, следующий порядок рангов: 3, 1, 2.
- На первом шаге человек с рангом 3 берёт себе три яблока.
- На втором шаге человек с рангом 1 берёт себе одно яблоко.
- На третьем шаге человек с рангом 2 берёт себе два яблока.
- На четвёртом шаге человек с рангом 3 берёт себе последние два яблока в куче.
Таким образом, человеку с рангом 1 достанется одно яблоко. С другой стороны, вне зависимости от порядка людей в кругу каждому человеку достанется хотя бы одно яблоко, потому что первых шести яблок хватит на всех троих людей при любом порядке раздачи. Значит, минимальное возможное количество яблок у человека будет равно одному.
Во втором примере урожай состоит из одного-единственного яблока. В этом случае при любом порядке людей в кругу и любом выборе начинающего человека единственное яблоко достанется начинающему, а двум оставшимся людям яблок не достанется совсем. Значит, минимальное возможное количество яблок у человека будет равно нулю.
3 8
1
3 1
0
Гриша, подобно персонажу известной кинокомедии, нашел себе ночную работу в музее естественной истории. В первую же смену ему выдали его главное орудие труда — эмбоссер — и приказали провести инвентаризацию всей экспозиции.
Эмбоссер представляет собой устройство для «печати» текста на пластиковой ленте. Текст набирается последовательно, буква за буквой. В устройство входят колесо с нанесёнными по кругу строчными буквами английского алфавита, неподвижная засечка, которая указывает на текущую букву, и кнопка, печатающая выбранную букву. За одно действие можно повернуть колесо с алфавитом на одну букву влево либо вправо по циклу. Изначально засечка эмбоссера указывает на букву a. Остальные буквы расположены так, как показано на рисунке.
Наш герой боится, что некоторые особо устрашающие экспонаты могут ожить и начать за ним свою охоту, поэтому он хочет как можно быстрее напечатать все названия. Помогите ему: для данного названия экспоната определите минимальное количество поворотов колеса, необходимое для его печати.
Единственная строка входных данных содержит название экспоната — строку, состоящую из не менее, чем одного, и не более, чем ста символов. Гарантируется, что строка состоит из строчных букв английского алфавита.
Выведите единственное целое число — минимальное количество поворотов колеса, за которое Гриша сможет напечатать название экспоната.
1. от a до z (1 поворот против часовой стрелки),
2. от z до e (5 поворотов по часовой стрелке),
3. от e до u (10 поворотов против часовой стрелки),
4. от u до s (2 поворотa против часовой стрелки).
Итого потребуется 1 + 5 + 10 + 2 = 18 поворотов.
zeus
18
map
35
ares
34
Молодой известный дизайнер Пётр решил устроить мастер-класс для широких масс. Он планирует, что на мастер-классе каждый участник создаст свой неповторимый шедевр. Пётр собирается подготовить для каждого участника огромный белый холст \(h \ см \times w \ см\) (\(h\) и \(m\) — целые числа) и баночку краски чёрного цвета, которой хватает ровно на \(s \ см^2\) холста.
Незадолго до мастер-класса Петру сообщили, что широкие массы не блещут оригинальностью, и каждый участник нарисует ровно один прямоугольник, истратив при этом целиком свою баночку краски. Более того, стороны прямоугольника обязательно будут параллельны осям холста, а расстояния от сторон прямоугольника до сторон холста будут выражаться целыми числами сантиметров. Пётр заинтересовался, сколько можно нарисовать различных произведений искусства (банальных, но всё же примечательных!) в данных условиях?
В одной строке заданы три целых числа \(h, \ w, \ s \ (1 \le h, \ w \le 10^5,\ 1 \le s \le 10^9\) ) — размеры холста и площадь прямоугольника.
Выведите одно целое число — ответ на задачу.
В первом примере из условия есть два вида прямоугольников с площадью \(4 \ см^2.\) Прямоугольник \(1 \ см \times 4\) см можно разместить двумя способами, а прямоугольник \(2\) см \(\times\) \(2\) см — тремя способами.
4 2 4
5
3 2 2
7
2 3 10
0
Уже начался сезон олимпиад по программированию, а значит пора писать командные тренировки. Серёжа ведёт тренировки у своих команд не первый год и знает, что к туру надо подготовить не только набор задач и разбор. Тренировка длится несколько часов, и команды, которые в ней участвуют, успевают за это время проголодаться. Поэтому на каждую тренировку Серёжа закупает некоторое количество пицц, чтобы после окончания тура команды подкрепились и обсудили свои успехи и неудачи.
Командам предстоит написать n тренировок в течение n последовательных дней. Во время каждой тренировки на каждую команду, пришедшую в этот день, Серёжа заказывает по пицце в своей любимой пиццерии. Серёжа уже знает, что на i -ю тренировку придёт ровно a i команд.
В пиццерии проходят две акции. В рамках первой акции можно получить скидку, если купить две пиццы в один день. Вторая акция позволяет получить купон на покупку одной пиццы в день на протяжении двух последовательных дней.
Серёжины тренировки очень популярны, поэтому ему приходится часто делать заказы в этой пиццерии. Как их самый ценный клиент, он может неограниченно пользоваться указанными скидками и купонами в любых количествах в любые дни.
Серёжа хочет заказать все пиццы, пользуясь только скидками и купонами. При этом он не хочет приобретать ни в один из дней больше пицц, чем ему нужно в этот день. Помогите Серёже определить, может ли он закупить пиццу на все тренировки, пользуясь только купонами и скидками.
В первой строке находится целое число n ( 1 ≤ n ≤ 200 000 ) — количество тренировок.
Во второй строке находится n целых чисел a 1 , a 2 , ..., a n ( 0 ≤ a i ≤ 10 000 ), разделённых пробелами, — количества команд, которые придут на каждую из тренировок.
Если Серёжа может заказать все пиццы, используя только скидки и купоны и не покупая лишние пиццы ни в один из дней, выведите « YES » (без кавычек). Иначе выведите « NO » (без кавычек).
В первом примере Серёжа может воспользоваться одним купоном для покупки пицц в первый и второй день, одним купоном для покупки пицц во второй и третий день и одной скидкой в четвёртый день для покупки двух пицц. Это единственный возможный способ заказать все пиццы для данного теста.
Во втором примере Серёжа не может воспользоваться ни купоном, ни скидкой, не заказав при этом лишнюю пиццу. Обратите внимание, что в некоторые дни на тренировку может не прийти ни одной команды, как, например, во второй день в данном тесте.
4 1 2 1 2
YES
3 1 0 1
NO