В Берляндии вышел новый смартфон berPhone V. И сейчас он стоит целых n бурлей.
Поликарп узнал, что цена нового смартфона будет снижаться ежедневно, причём каждый день продавцы будут либо вычитать из цены 1 (если она строго больше 1), либо стирать последнюю цифру в цене (если она строго больше 9). Таким образом, цена никогда не станет меньше одного бурля.
Поликарп не знает как будут действовать продавцы. В кошельке у Поликарпа есть k бурлей — ровно такую сумму он хочет потратить на berPhone V, ни бурлём больше, ни бурлём меньше.
Определите минимальное количество дней, по истечении которых цена может стать ровно k бурлей и Поликарп купит себе новый смартфон.
В первой строке следует целое число n (1 ≤ n ≤ 109) — начальная стоимость berPhone V.
Во второй строке следует целое число k (1 ≤ k ≤ n) — точная цена, за которую Поликарп хочет приобрести новый смартфон.
Выведите минимальное количество дней, по истечении которых цена может стать ровно k бурлей, и Поликарп купит себе новый смартфон.
100
9
2
23
23
0
54321
54
3
В первом примере Поликарп сможет купить berPhone V через два дня, если в первый день продавцы вычтут из стоимости 1 (цена станет равна 99), а во второй день сотрут последнюю цифру в цене. После этого стоимость berPhone V станет равна 9, именно такую сумму Поликарп хочет потратить на покупку смартфона.
Во втором примере начальная цена смартфона равна цене, по которой Поликарп хочет его купить, поэтому Поликарпу не нужно ждать ни одного дня.
В третьем примере Поликарп сможет купить berPhone V через три дня, если продавцы в каждый из трёх дней будут стирать последнюю цифру в цене смартфона (
).
Макару срочно нужно получить справку в больнице. Всего в больнице есть n кабинетов, пронумерованных целыми числами от 1 до n.
Так как везде царит бюрократия, посетитель больницы, пришедший в кабинет i, будет отправлен из него в кабинет ai (i ≠ ai).
Зная информацию о том, из какого кабинета в какой отправляют посетителей больницы, определите, сколько кабинетов посетит Макар перед тем, как впервые попадёт в кабинет, в котором уже побывал. Сразу после прихода в больницу Макар пойдёт за справкой в кабинет номер 1.
В первой строке следует целое число n (2 ≤ n ≤ 100) — количество кабинетов в больнице.
Во второй строке следует последовательность целых чисел a1, a2, ..., an (1 ≤ ai ≤ n, i ≠ ai), где ai равно номеру кабинета, в который отправляют посетителей кабинета i.
Выведите количество посещенных Макаром кабинетов перед тем, как он впервые попадёт в кабинет, в котором уже побывал.
3
3 3 1
2
5
2 3 4 5 2
5
В первом примере Макара из первого кабинета отправят в третий, а из третьего кабинета отправят в первый. Так как Макар уже был в первом кабинете, то ответ равен двум (то есть Макар посетит первый и третий кабинет перед тем, как попасть в кабинет, в котором уже был).
Во втором примере Макара отправят из первого кабинета во второй, из второго — в третий, из третьего — в четвёртый, из четвёртого — в пятый, а из пятого — во второй, то есть в кабинет, в котором Макар уже был. Таким образом, он посетит все пять кабинетов до того, как придёт в кабинет, в котором уже был.
Берляндская авиакомпания получила грант на создание самолёта нового поколения, и вот наступило время испытаний. Испытания будут проводиться в присутствии независимых экспертов в виде сравнительных тестовых полетов самолётов нового и старого поколений.
Самолёты будут летать по очереди — сначала самолёт нового поколения, затем самолёт старого поколения. Для каждого самолёта будет подсчитано расстояние, которое он пролетит за T секунд.
По полученным данным эксперты решат, прошел ли самолёт нового поколения испытания. Во время принятия решения они руководствуются двумя правилами:
Таким образом, испытания будут объявлены успешными, если не произошла ни одна из описанных в пунктах выше ситуаций.
Для обоих самолётов известны их минимальные и максимальные скорости полета: minn и maxn м/с для самолёта нового поколения и mins и maxs м/с — для старого. Во время тестового полета самолёты могут развивать любую скорость от их минимальной до максимальной включительно. Самолёты могут менять скорость моментально.
К сожалению для авиакомпании, пилота самолёта нового поколения подкупили конкуренты, и теперь он сделает все возможное, чтобы испытания были объявлены неуспешными. Пилот самолёта старого поколения, зная результаты полета самолёта нового поколения, напротив, сделает все возможное, чтобы испытания были объявлены успешными.
Авиакомпании надо срочно оценить риски, поэтому они просят вас определить, могут ли испытания пройти успешно, независимо от действий пилота самолёта нового поколения.
В первой строке через пробел заданы четыре целых числа: minn, maxn, mins и maxs (1 ≤ minn ≤ maxn ≤ 1 000, 1 ≤ mins ≤ maxs ≤ 1 000) — минимальные и максимальные скорости для самолётов нового и старого поколений, соответственно.
Во второй строке через пробел заданы два целых числа T и D (1 ≤ T ≤ 1 000, 1 ≤ D ≤ 1 000) — время полета каждого самолёта и максимально допустимая разность пройденных расстояний.
Выведите единственное слово «YES» (без кавычек), если испытания будут объявлены успешными, независимо от действий пилота самолёта нового поколения.
Выведите единственное слово «NO» (без кавычек), если пилот самолёта нового поколения может совершить полёт так, что испытания будут объявлены неуспешными, независимо от полёта самолёта старого поколения.
5 6 2 5
10 10
NO
3 4 2 5
100 1
YES
5 6 2 5
9 10
YES
3 3 5 5
1 1
NO
В первом примере самолёт нового поколения может всё время лететь со скоростью 6 м/c. Как бы не летел самолёт старого поколения, за 10 секунд он отстанет от самолёта нового поколения не менее чем на 10 метров, так как максимальная скорость самолёта старого поколения равна 5 м/c. Отставание на 10 метров, согласно второму пункту из условия, приведет к объявлению испытаний неуспешными.
При передаче по сети числа k минимальное количество бит, которые необходимо передать, равно длине этого числа в двоичной записи. Например, для передачи по сети числа 13 необходимо передать 4 бита (так как 1310 = 11012), а для передачи числа 181 необходимо передать 8 бит (так как 18110 = 101101012).
При передаче по сети последовательности чисел их двоичные записи выравниваются нулями до длины наибольшего числа. Например, если необходимо передать последовательность чисел [8, 181, 13], то будет передано 3·8 = 24 бита. Число 8 будет передано в виде «00001000», число 181 будет передано в виде «10110101», а число 13 будет передано в виде «00001101».
У Поликарпа есть n целых чисел. Из этих чисел он может выбрать любой набор, сформировать из него новую последовательность и передать ее по сети.
Определите наибольшее количество чисел, которые Поликарп сможет передать за один раз как последовательность, используя не более b бит.
В первой строке следуют два целых числа n и b (1 ≤ n ≤ 2·105, 1 ≤ b ≤ 109) — количество чисел, которые есть у Поликарпа, а также максимальное количество бит, которые он может использовать для передачи чисел.
Во второй строке следует последовательность целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — числа, которые есть у Поликарпа.
Выведите наибольшее количество чисел, которые сможет передать Поликарп за один раз, используя не более b бит.
3 4
1 3 2
2
5 19
15 77 16 1 16
3
В первом примере Поликарп сможет передать любые два числа. Например, он может передать числа 1 и 2, потратив ровно 4 бита, так как для представления числа 2 нужно ровно 2 бита.
Во втором примере Поликарп обязательно должен передать числа 1 и 15, а также одно число 16. На это он потратит 15 бит, так как для представления числа 16 нужно 5 бит. Оставшихся четырёх бит не хватит, чтобы передать ещё одно число 16 и, тем более, число 77.
Между Берляндией и Байтландией война!
Берляндские разведчики с помощью военных дронов сделали цифровую фотографию территории Байтландии. Фотография представляет собой прямоугольник размера n × m пикселей. Каждый пиксель либо белого цвета, либо чёрного. Пиксель белого цвета на фотографии обозначается символом '.', а пиксель чёрного цвета — символом '*'.
Известно, что в Байтландии все здания имеют особую форму. На фотографии каждое здание имеет форму чёрного «креста», все четыре луча которого имеют ширину, равную одному пикселю, положительную длину и параллельны сторонам фотографии. Иными словами, каждое здание выглядит как пара перпендикулярных пересекающихся внутренним образом отрезков из звездочек. Каждый отрезок в паре имеет длину не менее трёх и параллелен сторонам фотографии.
Известно, что на фотографии все чёрные пиксели соответствуют зданиям, каждое здание целиком помещается на фотографии, никакие два здания не пересекаются и не касаются (как стороне так и по углу).
Ниже изображены примеры фотографий:
На фотографиях изображены три, четыре и два здания соответственно. Здание является военным объектом, если оно абсолютно симметрично, то есть если длины всех четырех лучей равны между собой. На рисунке выше на левой фотографии два военных объекта, на центральной фотографии четыре военных объекта, а на правой фотографии один военный объект.
Помогите спецслужбам Берляндии определить количество зданий на фотографии, являющихся военными объектами.
В первой строке следуют два целых числа n и m (3 ≤ n, m ≤ 1 000) — размеры фотографии.
В следующих n строках следуют по m символов '.' и '*' — описание территории Байтландии. Если очередной символ равен '.', то соответствующий пиксель белый на фотографии. Если очередной символ равен '*', то соответствующий пиксель чёрный на фотографии.
Гарантируется, что фотография содержит только здания, имеющие описанный выше вид. Каждое знание целиком помещается на фотографию. Никакие два здания не пересекаются и не касаются (как по стороне, так и по углу). Возможно, что на территории Байтландии нет ни одного здания, то есть все пиксели белые.
Выведите количество зданий на фотографии Байтландии, являющихся военными объектами.
9 8
..*.....
..*.....
*****...
..*.....
..*..*..
.....*..
....***.
.....*..
.....*..
1
12 3
.*.
***
.*.
...
.*.
.*.
***
.*.
...
.*.
***
.*.
2
4 4
....
....
....
....
0
В первом примере здание с центром в точке (3, 3) является военным объектом, так как все лучи, исходящие из этой точки имеют одинаковую длину, равную двум пикселям. Здание с центром в точке (7, 6) не является военным объектом, так как два луча, исходящие из этой точки имеют длину один пиксель, а два других — длину два пикселя.
Во втором примере только здания с центрами в точках (2, 2) и (11, 2) являются военными объектами. Здание с центром в точке (7, 2) не является военным объектом, так как три луча, исходящие из этой точки имеют длину один пиксель, а четвёртый луч имеет длину два пикселя.
В третьем примере на фотографии нет ни одного здания, поэтому количество военных объектов равно нулю.
Пётр работает в рекламном отделе Берляндской социальной сети БК. Руководство БК решило добавить таргетированную рекламу в свою социальную сеть. Для эффективного показа таргетированной рекламы Петру дали задание собрать следующую информацию о каждом пользователе: пол пользователя и факт наличия у него детей.
К сожалению для Петра, не все пользователи полностью заполняют свой профиль. Однако иногда информацию о пользователе можно узнать из профилей других пользователей, воспользовавшись логикой. Например, если пользователь A указал, что пользователь B является его матерью, то мы можем понять, что пол пользователя B — женский, даже если пользователь B не указал свой пол в профиле.
Пётр имеет доступ к части базы данных соцсети БК. Пользователи в базе представлены их уникальными идентификаторами (id) — целыми числами от 1 до n. Все записи базы данных, доступные Петру, можно отнести к одному из следующих четырёх типов:
Берляндия находится в параллельной вселенной, а потому там действуют дополнительные правила относительно вступления в брак и рождения детей:
Помогите Петру собрать информацию о пользователях БК. На основании доступных записей базы данных для каждого пользователя определите, если возможно, его пол и факт наличия детей. Считайте, что пользователи БК не указывают в своих профилях недостоверную информацию.
В первой строке следуют два числа n и m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105) — количество пользователей БК и количество записей в базе данных, доступных Петру.
В следующих m строках следуют записи базы данных, по одной в строке. Каждая запись представлена тремя числами ti, xi, yi (1 ≤ ti ≤ 4, 1 ≤ xi, yi ≤ n, xi ≠ yi) — тип записи и два id пользователей социальной сети БК, в соответствии с описанными выше правилами хранения записей в базе данных.
Гарантируется, что записи в базе данных корректны и не противоречат друг другу.
Выведите n строк. В i-ю строку выведите два символа ai и bi через пробел. Если пользователь с id i мужского пола, ai должно быть равно 'm', если женского — 'f', а если определить пол по доступной информации невозможно, ai должно быть равно '?'. Если у пользователя с id i точно есть дети, bi должно быть равно '+'. В противном случае bi должно быть равно '-'.
5 4
1 3 1
4 3 4
3 3 2
2 4 5
f +
m +
? -
? -
m +
4 2
4 1 3
3 4 3
? +
? -
? +
? -
3 2
4 1 2
1 3 2
m +
f +
? -
В первом примере по имеющимся данным из базы данных можно определить следующую информацию:
Невозможно однозначно определить пол пользователей с id=3 и с id=4, а также невозможно определить факт наличия детей у этих пользователей.
Очень скоро сдача проекта, а ещё ничего не готово! Компании нужно срочно распланировать, кто и чем будет заниматься, чтобы всё успеть.
Всего в компании работает n человек, причём n — чётное положительное число. Они работают в парах: первый со вторым, третий с четвёртым, ..., (n - 1)-й с n-м. Проект, над которым работает компания, также состоит из n частей, при этом сложность i-й части равна ai.
До срока сдачи проекта осталось ровно n дней, и, согласно политике компании, был установлен следующий план работ: каждый день n частей проекта должны быть распределены среди n работников так, что каждый работник в течение всего дня занимается только одной частью проекта и каждой частью проекта занимается ровно один работник. При этом каждый работник за n дней должен поработать над каждой частью проекта.
Работник, выполняя свою часть проекта в очередной день, испытывает стресс, если сложность работы его напарника в этот день меньше, чем у него самого. При этом величиной стресса будем считать модуль разности между сложностями частей проекта. Например, если пятый сотрудник выполняет часть проекта со сложностью 10, а шестой сотрудник — со сложностью 15, то величина стресса пятого сотрудника будет равна 0, а величина стресса шестого сотрудника будет равна |10 - 15| = 5.
Компания очень дорожит своими работниками, а потому хочет распределить части работы по сотрудникам таким образом, чтобы минимизировать суммарный стресс, получаемый работниками за все n дней работы над проектом. Если таких распределений несколько, компанию устроит любое из них.
Составьте оптимальное распределение работы на n дней, которое минимизирует суммарный стресс сотрудников.
В первой строке следует целое число n (2 ≤ n ≤ 150) — количество работников, количество частей проекта и количество дней до срока сдачи. Гарантируется, что n — чётное число.
Во второй строке следует последовательность целых чисел a1, a2, ..., an (1 ≤ ai ≤ 5 000), где ai равно сложности i-й части проекта.
В первую строку выведите минимально возможный суммарный стресс, который могут получить сотрудники компании.
В каждую из следующих n строк выведите по n целых чисел, при этом j-е число в i-й строке должно быть равно номеру части проекта, над которой должен работать j-й сотрудник в i-й день в оптимальном распределении.
2
3 1
4
1 2
2 1
4
2 2 2 3
4
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
4
4 4 7 1
24
1 4 2 3
3 1 4 2
2 3 1 4
4 2 3 1
Посчитаем для каждого примера суммарный стресс, полученный работниками.
В первом тесте:
(|a1 - a2| + 0) +
(0 + |a2 - a1|) = 2 + 2 = 4.
Во втором тесте:
(0 + 0 + 0 + |a4 - a3|) +
(0 + 0 + |a4 - a1| + 0) +
(0 + |a4 - a3| + 0 + 0) +
(|a4 - a1| + 0 + 0 + 0) = 1 + 1 + 1 + 1 = 4.
В третьем тесте:
(|a1 - a4| + 0 + 0 + |a3 - a2|) +
(|a3 - a1| + 0 + 0 + |a2 - a4|) +
(0 + |a3 - a2| + |a1 - a4| + 0) +
(0 + |a2 - a4| + |a3 - a1| + 0) = 24.
Вот уже n дней Вася следит за погодой и записывает температуру воздуха в каждый из этих дней.
Вася решил сверить свои записи с данными на сайте гидрометцентра. Оказалось, что он верно записывал температуру в каждый из n дней, но Вася нашёл на сайте ошибку. Там было указано, что средняя температура воздуха за последние n дней равна a (a — это сумма температур за все n дней, делённая на количество дней n, округленная вниз), но в действительности это значение было равно другому числу.
Васе стало интересно, какое минимальное количество дней m нужно еще измерять температуру воздуха, чтобы средняя температура за все n + m дней стала равна a (округление вновь производится вниз). Вася считает, что будет статистически достоверно, если все добавляемые значения температур будут целыми числами не меньше минимума и не больше максимума из температур за последние n дней.
В первой строке следуют два целых числа n и a (1 ≤ n, a ≤ 100) — количество дней, в которые Вася измерял температуру, а также средняя температура воздуха за последние n дней, которая указана на сайте.
Во второй строке следует последовательность t1, t2, ..., tn (1 ≤ ti ≤ 100), где ti равно температуре воздуха в i-й день измерений.
Гарантируется, что на сайте гирометцентра ошибочно указана средняя температура a, и нужно измерять температуру ещё хотя бы один день. Иными словами, средняя температура за последние n дней, округлённая вниз, не равна a.
Если невозможно достичь средней температуры a ни при каких условиях, выведите -1.
В противном случае, в первую строку выведите целое число m — минимальное количество дней, которые нужно ещё измерять температуру. Во вторую строку выведите m целых чисел — какая температура воздуха должна быть в эти дни, чтобы средняя температура воздуха за n + m дней стала равна a.
4 20
10 11 12 30
2
28 29
2 3
9 1
1
1
В первом примере температуру нужно измерять ещё минимум два дня. Нужно, чтобы в первый из этих дней температура была, например, 28 градусов, а во второй — 29. Тогда последовательность температур будет иметь вид 10, 11, 12, 30, 28, 29 c суммой 10 + 11 + 12 + 30 + 28 + 29 = 120, а средняя температура будет равна 120 / 6 = 20.
Во втором примере нужно измерять температуру минимум один день, и в этот день температура должна быть равна 1. Тогда последовательность температур будет иметь вид 9, 1, 1 с суммой 9 + 1 + 1 = 11, а средняя температура будет равна 3, так как 11 / 3 = 3.(6), а округляя вниз это число, получаем 3.
Таня придумала игру и теперь целыми днями играет в неё. Игра называется «Музыкальные классики». До начала игры она на асфальте рисует n одинаковых квадратов, выстроенных в ряд слева направо. Квадраты пронумерованы от 1 до n слева направо. В каждом квадрате она рисует одну из семи нот, которые обозначает латинскими буквами от 'A' до 'G', причём i-й квадрат содержит ноту ti.
После этого она выбирает некоторую мелодию s, которая состоит из m нот, воспроизводимых последовательно. Ноты в мелодии пронумерованы от 1 до m в порядке воспроизведения.
До начала воспроизведения Таня встает в некоторый квадрат, в котором записана первая нота мелодии (иными словами, буква s1). Если таких квадратов несколько, то она сама выбирает, в какой из них ей встать.
После этого Таня включает мелодию и в момент, когда начинает звучать вторая нота, она должна перепрыгнуть в квадрат с этой нотой (то есть с буквой s2). Когда начинает звучать третья нота, Таня должна перепрыгнуть в квадрат с третьей нотой (то есть буквой s3). Так она продолжает игру до её окончания. Допустимо, что во время звучания очередной ноты Таня подпрыгнет на месте и приземлится в том же квадрате. Это может произойти, если очередная нота совпадает с предыдущей.
Таня не умеет прыгать дальше, чем на d квадратов влево или вправо. Например, если d = 1, то Таня может прыгать не дальше соседних по стороне квадратов, а если d = 0, то Таня может прыгать только на тот квадрат, в который встанет изначально. Левее квадрата номер один и правее квадрата номер n Таня прыгать не будет, так как это не по правилам!
Игра может закончиться по двум причинам — либо мелодия будет полностью воспроизведена, либо Таня не сможет сделать очередной прыжок. Во втором случае игра тут же прекращается.
Найдите наибольшую возможную продолжительность игры Тани при её наилучшей стратегии. Если первая нота из мелодии не написана ни в одном из квадратов, то продолжительность игры равна нулю.
В первой строке следуют три целых числа n, m и d (1 ≤ n, m ≤ 100, 0 ≤ d ≤ n - 1) — количество квадратов с нотами, количество нот в мелодии и максимальная дальность прыжка Тани.
Во второй строке следует строка t длины n, где ti равно ноте, записанной в i-м квадрате. Гарантируется, что строка t содержит только прописные латинские буквы от 'A' до 'G'.
В третьей строке следует строка s длины m, где sj равно j-й ноте в мелодии. Гарантируется, что строка s содержит только прописные латинские буквы от 'A' до 'G'.
Выведите максимальное количество нот, на протяжении воспроизведения которых Таня сможет играть по правилам и игра не закончится.
8 3 2
AGFEDCBA
ACF
2
2 4 1
AB
ABAA
4
6 3 4
EAGCBF
DAC
0
В первом примере Таня должна изначально встать в квадрат номер 8, в котором написана нота 'A'. После воспроизведения первой ноты она должна прыгнуть в квадрат номер 6, в котором записана вторая нота мелодии 'C'. После этого игра прекратится, так как Таня не сможет допрыгнуть до единственного квадрата с нотой 'F'.
Во втором примере Таня сможет играть на протяжении воспроизведения всех четырёх нот мелодии. Для этого ей нужно изначально встать в квадрат номер 1, затем прыгнуть в квадрат номер 2, после этого прыгнуть в квадрат номер 1 и перед воспроизведением четвёртой ноты подпрыгнуть на месте, то есть остаться в квадрате номер 1.
В третьем примере первая нота мелодии, равная 'D', не записана ни в одном из квадратов, поэтому ответ равен нулю.
Недавно Люба купила себе набор домино, состоящий из n доминошек. Открыв набор, она сильно удивилась, потому что доминошки были необычными. Доминошка — это прямоугольник размера 1 × 2. В этом наборе есть только 3 типа доминошек:
В прилагаемых к набору правилах было сказано, что играть в них должен только один человек и его главная задача — положить эти доминошки в горизонтальный ряд длины 2·n так, чтобы в получившемся ряду было ровно k отрезков чёрного цвета. Любую чёрно-белую доминошку можно развернуть на 180 градусов при помещении в ряд.
Отрезком черного цвета называется такой набор подряд идущих квадратов, каждый из которых имеет черный цвет, а слева и справа набор ограничен белыми квадратами или границами ряда.
На представленном рисунке выложено 5 доминошек, и они образуют 3 отрезка чёрного цвета Люба, конечно же, хочет выиграть, но так как доминошек могло быть очень много, она обратилась за помощью к вам! Напишите программу, которая составляет из всех имеющихся доминошек горизонтальный ряд, в котором есть ровно k отрезков чёрного цвета, либо сообщите, что с данным набором домино выиграть нельзя. Каждая доминошка из набора должна быть выложена ровно один раз.
В первой строке следуют четыре целых числа k, n1, n2 и n3 (0 ≤ k ≤ 3·105, 0 ≤ n1, n2, n3 ≤ 105, n1 + n2 + n3 > 0) — требуемое количество отрезков черного цвета, количество доминошек первого, второго и третьего типа, соответственно.
Выведите «Impossible» (без кавычек), если с данным набором выиграть нельзя.
В противном случае, выведите строку длины 2·n, соответствующую искомому ряду из n доминошек. Первый и второй символ должны соответствовать первой выложенной доминошке, третий и четвёртый — второй выложенной доминошке, и так далее. Соответственно, (2·n - 1)-й и (2·n)-й символы должны соответствовать n-й выложенной доминошке. При этом, если i-й символ выведенной строки
Каждая доминошка из набора должна быть выведена ровно один раз. Если ответов несколько, разрешается вывести любой из них.
4 1 2 3
111010101100
2 3 0 4
00011000011000
1 2 0 4
Impossible
В первом примере один из подходящих вариантов выкладывания следующий:
Таким образом, получится 4 отрезка чёрного цвета, что и необходимо для победы в игре.
Иван — студент Берляндского государственного университета. Начался новый учебный год, и Иван хочет подключить мобильный интернет, поэтому ему нужно внести необходимую сумму на счёт телефона. К сожалению, у Ивана есть только наличные деньги, поэтому всю сумму придётся вносить через банкомат.
В Берляндии существуют купюры девяти различных номиналов: 10, 20, 50, 100, 200, 500, 1 000, 2 000 и 5 000 бурлей (и все эти купюры принимаются банкоматами). У Ивана есть какое-то количество купюр каждого номинала, и он собирается взять какие-то из этих купюр и перевести их на счёт своего мобильного телефона через банкомат. Этих купюр может не хватить, чтобы набрать нужную сумму. Может быть и наоборот: Ивану придётся внести на счёт больше, чем требуется для подключения интернета. Но, если Иван сможет оплатить интернет, то он хочет внести на счёт как можно меньшую сумму, которой будет достаточно для оплаты.
Иван пока не решил, какой именно тариф он хочет подключить. Всего ему доступны q тарифов, i-й из которых характеризуется натуральным числом ki — количеством бурлей, необходимых для подключения интернета по этому тарифу. Иван хочет для каждого из тарифов узнать, хватит ли у него денег на его подключение, и если да, то какую минимальную сумму ему нужно будет внести на счёт (с учётом того, что он выбирает какую-то часть своих купюр для оплаты). Иван уже попытался выполнить все необходимые вычисления самостоятельно, но запутался в них. Помогите Ивану определить нужную ему информацию!
Обратите внимание: Иван в этой задаче не тратит деньги, то есть каждый тариф рассматривается независимо с учётом тех денег, которые были у Ивана изначально.
В первой строке следуют 9 целых чисел a10, a20, a50, a100, a200, a500, a1 000, a2 000 и a5 000, где ai равно количеству купюр номинала i, имеющихся у Ивана (0 ≤ ai ≤ 1012).
Во второй строке записано целое число q (1 ≤ q ≤ 105) — количество тарифов.
В третьей строке записаны q целых чисел k1, k2, ..., kq (1 ≤ ki ≤ 1015), где ki равно стоимости подключения интернета по i-му тарифу.
В единственную строку выходных данных выведите через пробел q целых чисел. i-е из них должно быть равно минимальной сумме, которую Иван должен внести в банкомат для подключения i-го тарифа (или -1, если Ивану не хватит денег для подключения этого тарифа).
0 3 1 0 0 0 0 0 0
4
45 55 70 150
50 60 70 -1
1 1 1 1 1 1 1 1 1
7
4999 7004 8090 9000 8841 8880 8881
5000 7010 8100 -1 8850 8880 -1
В первом примере у Ивана есть только три купюры номиналом 20 бурлей и одна купюра номиналом 50:
Во втором примере у Ивана есть по одной купюре каждого достоинства:
Впечатлившись фильмом «Пираты Корсарского моря 8», Поликарп решил найти клад, который по легенде закопан на одном из пляжей Берляндии. Следуя советам главного героя фильма, Поликарп быстро нашел и раскопал сундук с кладом.
К его разочарованию, на сундуке висел огромный замок, состоящий из n вращающихся дисков. На каждом из дисков записаны все целые числа от - 1013 до 1013. Также на каждом диске есть ровно одна важная позиция, в которой находится ровно одно число. Каждый из дисков можно прокручивать в любую сторону, чтобы изменять числа, стоящие в важных позициях.
Чтобы открыть замок, нужно прокрутить некоторые диски таким образом, чтобы выполнялись m условий. Условие i гласит, что сумма чисел, записанных на важных позициях дисков с номерами от li до ri включительно, должна равняться числу si.
Помогите Поликрапу! Выведите расположение дисков замка, при котором его можно открыть, либо сообщите, что замок открыть невозможно.
В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 3·105) — количество дисков на замке и количество необходимых для его открытия условий.
В каждой из следующих m строк следуют по три целых числа li, ri и si (1 ≤ li ≤ ri ≤ n, - 3·107 ≤ si ≤ 3·107) — описание очередного условия. Сначала следует номер самого левого диска, затем номер самого правого диска, а после этого требуемая сумма чисел на важных позициях дисков с номерами от li до ri включительно.
Если невозможно открыть замок, выведите в первую строку «NO» (без кавычек).
В противном случае, выведите в первую строку «YES» (без кавычек). Во вторую строку выведите n чисел, которые должны стоять на важных позициях дисков для открытия замка (то есть все m условий из входных данных должны выполняться для выведенного расположения дисков). Если ответов несколько, разрешается вывести любой из них.
5 4
1 2 5
1 3 8
2 5 11
4 5 3
YES
0 5 3 -8 11
5 4
2 3 5
1 3 8
2 5 11
4 5 3
NO
В первом примере суммы на соответствующих отрезках действительно равны заданным: a1 + a2 = 0 + 5 = 5 = s1, a1 + a2 + a3 = 8 = s2, a2 + a3 + a4 + a5 = 11 = s3 и a4 + a5 = 3 = s4.
Во втором примере можно доказать, что замок открыть невозможно. Для этого рассмотрим сумму на отрезке [2, 5]: с одной стороны a2 + a3 + a4 + a5 = (a2 + a3) + (a4 + a5) = s1 + s4 = 5 + 3 = 8, с другой стороны a2 + a3 + a4 + a5 = (a2 + a3 + a4 + a5) = s3 = 11.