Надя Пивко обычная студентка обычного института. Естественно, любимое место Нади Пивко в институте – это столовая. Сегодня она в очередной раз решила покушать рис, мясо по-французски (конечно, с подливой), пирожное и чай. Сев за стол, она увидела результат работы вандала! На столе было нацарапано:
f1(n) = an - bn
Отодвинув тарелку, Надя Пивко обнаружила ещё одну надпись:
f2(n) = A * f2(n - 1) + B * f2(n - 2)
Поскольку Надя Пивко пришла в столовую одна, то ей стало скучно, поэтому она решила разгадать, что же всё-таки хотел поведать вандал, надругавшись над столом. Поразмыслив немного, Надя Пивко решила, что последовательности могут быть одинаковы, но для этого необходимо задать А и В. Внезапно прозвенел звонок и ей пришлось убежать на мат. логику и задача осталась нерешённой. Помогите Наде Пивко найти А и В, а так же f2(0) и f2(1) при заданных а и b, причём полученная последовательность f2(n) должна быть идентична последовательности f1(n).
В единственной строке даны целые числа a и b (1 ≤ a,b ≤ 109, a ≠ b).
В единственной строке выведите четыре числа через пробел – f2(0) и f2(1), а затем полученные коэффициенты А и В.
3 2
0 1 5 -6
Жил-был рыбак, которого звали Кеша Котиков. Он очень любил селёдку и, как следствие, картошечка с селёдочкой для него являлись пределом мечтаний и верхом кулинарного искусства. Однажды в жизни Кеши Котикова наступил переломный момент. Так как Кеша Котиков постоянно ел селёдку и не работал, то у него просто закончились деньги и вся селёдка. Тогда Кеша Котиков решил, что пришло время перемен, но поскольку отказаться от селедки было выше его сил, наш обжора решил ловить и солить её самостоятельно; часть её шла на то, чтобы потешить его бездонный желудок, а остатки - на продажу.
Собственно, на данный момент у Кеши Котикова уже есть А засоленных селёдок, и он только что привёз с рыбалки ещё В селёдок. Наш герой начал засаливать селёдки друг за другом. Одну за другой, одну за другой, одну за другой…
Автору задач стало интересно: сколько засоленных селёдок будет у Кеши Котикова после того, как он засолит все В пойманных селёдок? Помогите ему.
В единственной строке даны целые числа А и В (0 ≤ А,В ≤ 109).
Выведите единственное число – ответ на задачу.
175892 7564942
7740834
В стране Колбасляндия в городе Печенюшка Пингвин-Ахмед продаёт курочку гриль. В этом прекрасном процветающем государстве своеобразные правила торговли. Дело в том, что продавцы имеют право продавать курочек гриль за А тимуриков (местная валюта), либо за любое количество тимуриков В такое, что В>A и количество единичек в бинарном виде у чисел А и В одинаково.
Так как Пингвин-Ахмед не слишком глуп, у него созрел коварный план по повышению своего дохода (в дальнейшем завоевания мира, да-да-да). Он решил периодически повышать цену на свою курочку гриль и сейчас он хочет первый раз повысить цену, поэтому В должно быть минимально, чтобы клиенты Пингвина-Ахмеда ничего не заподозрили. Но так как Пингвин-Ахмед и не слишком умён – он не в состоянии найти минимальное число большее А и с тем же количеством единичек в бинарной записи. Пингвин-Ахмед попросил Вас помочь ему, а взамен он даст Вам НИЧЕГО, потому что он пингвин.
В единственной строке дано натуральное число А (А < 109).
Выведите единственное число – ответ на задачу.
5
6
128
256
В стране Колбасляндия находится огромное хранилище колбас. Палки колбасы в нём хранятся в стеллаже высотой N полок по М штук на полке, места на полках нумеруются с единицы слева направо, полки тоже нумеруются с единицы сверху вниз. В хранилище работает не самый честный охранник. Зовут его Жуль Ворн. Он каждый день утаскивает со своей работы колбасу. Естественно, Жуль Ворн не хочет, чтобы его поймали, поэтому для своего воровства он выбрал очень своеобразную схему:
- Каждый вечер он выбирает область на стеллаже колбас, рассматривая палки колбасы, которые находятся на полках с n1 по n2 и номер которых на полке больше либо равен m1 и меньше либо равен m2.
- Далее он находит палку колбасы длинной k такую, что |X-Y| минимально, где Х – количество палок колбасы из выделенной области, которые короче либо равны k, а Y – количество палок колбасы из выделенной области, которые строго длиннее k. Если таких палок колбасы несколько, то он забирает самую длинную.
- С чувством собственного превосходства он забирает эту палку колбасы себе и уходит домой под покровом ночи.
Утром приходит смотритель хранилища колбас и видя, что какой-то палки колбасы не хватает, ставит на её место новую палку колбасы той же длины. Таким образом, к приходу Жуля Ворна вся колбаса уже на месте, и он снова забирает себе колбасу по отработанной схеме. Такое беззаконие не могло длиться слишком долго, поэтому через Q дней бессовестного охранника вычислили и он понёс суровое наказание, ну а Вам предлагается выяснить и сообщить директору хранилища колбас: палки колбасы какой длины утащил Жуль Ворн за Q дней?
В первой строке указаны два числа N и M (1 ≤ N, M ≤ 103) – количество полок на стеллаже и количество палок колбас на одной полке. Далее следуют N строк по М натуральных чисел в каждой, где aij – длина колбасы, находящейся на i-ой полке на j-ом месте. Длина каждой палки колбасы не превосходит 109. Далее дано число дней Q (1 ≤ Q ≤ 105).
В следующих Q строках записано по четыре числа: n1, n2, m1 и m2 (1 ≤ n1, n2 ≤ N; 1 ≤ m1, m2 ≤ M). Причём сумма площадей всех выделенных за Q дней областей не превышает 106.
Для каждого дня выведите на отдельной строке число – длину колбасы, которую унёс Жуль Ворн в этот день.
3 3
1 2 3
4 5 6
7 8 9
4
1 3 1 3
1 2 2 3
2 3 1 3
1 1 1 1
5
3
6
1
Жил был медведь Жора-Обжора. Сегодня ему досталось N килограммов мёда. Естественно, счастью Жоры-Обжоры не было конца, если бы не одно НО. Как бы грустно это ни было, он не может съесть больше, чем р(р-1) килограммов мёда в день, где р=
(это обусловлено физиологией медведей-Жор).
Как немногие из Вас могли догадаться, мёд Жоре-Обжоре подарил автор задач и теперь он задался вопросом: на сколько дней Жоре-Обжоре хватит мёда, если он будет есть в день столько мёда, сколько сможет?
В единственной строке дано натуральное число N ≤ 10666.
Выведите единственное число – ответ на задачу – количество дней, за которое Жора-Обжора съест весь мёд.
1
1
В далёкой стране Пиццарния проходит чемпионат по дартсу. Как раз сейчас завершилась финальная битва между титанами дартса – Гавайа и Маргарита. Естественно, в стране, где так любят пиццу, мишень для дартса и дротики тоже являются пиццами. Радиус пицц-дротиков настолько мал, что их можно считать точками. В этом году на соревнованиях случилась беда – система подсчёта очков вышла из строя, а её администраторы слишком объелись пиццы, чтобы работать. Поэтому организаторы соревнований обратились за помощью к Вам.
Мишень представляет собой пиццу «Четыре сезона», состоящую из четырёх пицц: «Салями», «Четыре сыра», «Грибное ассорти» и «Курица» - то есть это круг, разделённый на четыре сектора. За попадание в каждый сектор начисляется разное количество очков:
- За попадание в «Салями» игрок получает 100 очков.
- За попадание в «Четыре сыра» игрок получает 400 очков.
- За попадание в «Грибное ассорти» игрок получает 50 очков.
- За попадание в «Курица» игрок получает 10 очков.
- При попадании на границу мишени игрок теряет 100 очков.
- При попадании на границу между секторами игрок теряет 200 очков.
- При попадании на границу и мишени, и сектора игрок теряет 300 очков.
- За попадание за границы мишени игрок получает 0 очков.
- При попадании в центр мишени игрок теряет 240 очков.
Вам даны координаты бросков каждого игрока и радиус мишени, необходимо подсчитать очки каждого игрока и сказать, кто из участников победил. Причём известно, что Гавайа совершила первый бросок и игроки кидали пиццы по очереди.
Мишень представляет собой пиццу, на которой проведены оси Ох и Оу. Начало координат находится в центре пиццы. Расположение кусочков пиццы представлено на рисунке:
В первой строке указано число N (1 ≤ N ≤ 103) – количество бросков каждого из участников.
Далее следует 2N строк. В каждой строке указаны два числа – х и у координаты попадания. Координаты представляют собой целые числа, по модулю не превосходящие тысячу. В последней строке указан радиус R мишени-пиццы (2 ≤ R ≤ 103).
Выведите имя победителя и сумму его очков в одной строке через пробел. Если победила Гавайа, то выведите «Gavaya», а если победила Маргарита, то выведите «Margarita». Если количество очков у участников одинаково, то выведите «Despair», а также сумму очков любого из игроков.
2
5 -1
-3 1
10 0
-2 -4
10
Margarita 110
3
10 10
3 0
-3 2
1 -2
1 1
6 8
10
Gavaya 150
Тёмным вечером по городу шёл парень Степан Гум. Когда-то он отучился всего 9 классов и решил не получать высшее образование, а сразу идти работать. Причиной такого поступка была обычная юношеская упёртость. Теперь он шёл по улице в 10 часов вечера со своей работы – из супермаркета «Еда здесь». Степан Гум был очень грустен – шеф сегодня дал ему задание, которое наш герой не смог выполнить. Задание состояло в том, чтобы принести нужное количество банок с вареньем. Так как Степан Гум закончил только 9 классов и прогуливал уроки, то он не смог посчитать, сколько банок нужно принести, и так и не выполнил задание шефа.
Задание на первый взгляд было простым: нужно было принести столько банок варенья, чтобы их можно было разместить на N полках и не осталось свободного места. Причём Степан Гум помнит, что на одной полке может поместиться только М банок варенья.
Сегодня ночью Степан Гум наведался в дом автора задач и умолял о помощи, и автор решил предложить Вам посчитать, сколько банок нужно принести Степану Гуму, чтобы заполнить полки.
В единственной строке даны целые числа N и M (1 ≤ N,M ≤ 104).
Выведите единственное число – ответ на задачу.
1794 7856
14093664
Не только на Земле снимают и смотрят реалити-шоу. На планете Нямка тоже есть своё реалити-шоу. Его суть состоит в том, что участника шоу ставят на поле размером NxM в клетку с координатами (0, 0) (координаты отсчитываются от левого верхнего угла поля) и говорят ему идти вправо. Затем участник просто странствует по полю, тратя на каждое перемещение в соседнюю клетку одну секунду, и зрители телешоу ставят ставки на то, где окажется участник через Т секунд. Всё было бы очевидно, если бы поле было пустым, но это не так. На поле присутствуют:
- Указатели направления. Они представлены в виде букв английского алфавита: “u” – указывает, что участник должен двигаться вверх, “d” – указывает, что участник должен двигаться вниз, “l” – указывает, что участник должен двигаться влево, “r” – указывает, что участник должен двигаться вправо. Если участник приходит в точку с указателем направления, то далее он следует в том направлении, куда указывает указатель направления, даже если он не сделал ни одного шага.
- Катапульты. Катапульты работают одну секунду, если участник в этот момент оказывается в клетке с катапультой, то он перелетает в клетку, в которую стреляет катапульта. Перелёт участника из клетки с катапультой в новую занимает одну секунду. За один день реалити-шоу появляется Q катапульт. Если в клетке с катапультой есть указатель направления, то участник будет идти в заданном им направлении после переброски, если в новой клетке нет иного указателя направления. Гарантируется, что никакие две катапульты, находящиеся в одной клетке, не работают одновременно.
- Суши-бар. Если участник в какой-то момент времени окажется на линии или в столбце, которые содержат суши-бар, то он почувствует запах роллов и направится в сторону суши-бара, игнорируя указатели, но не катапульты. Он будет двигаться по линии или по столбцу в сторону суши-бара. Затраты на перемещение в соседнюю клетку так же составят одну секунду. Если участник дойдёт до суши-бара, то он проведёт там всё время до конца реалити-шоу, поедая разнообразные роллы, мисо-супы, суши и вкуснейшую лапшу. Гарантируется, что на всём поле суши-бар всегда один.
- Поле имеет границы. Если участник попробует пройти влево от клетки с координатами (а, 0), то он попадёт в точку с координатами (N-1-a, M-1). Если участник попробует пройти вверх от клетки с координатами (0, а), то он попадёт в точку с координатами (N-1, M-1-a), аналогично с другими границами.
Автор задач является большим поклонником данного реалити-шоу, поэтому он попросил Вас узнать: в какой точке будет находится через Т секунд участник сегодняшнего выпуска шоу?
В первой строке через пробел даны два натуральных числа N и M (2 ≤ N, M ≤ 103) – размеры поля.
Следующие N строк содержат по М символов каждая. Символы “u”, “d”, “l”, “r” – обозначают указатели направления. Символ “o” – обозначает пустую клетку. Символ “s” – обозначает суши-бар. Все символы являются строчными буквами английского алфавита.
Далее указаны два целых неотрицательных числа Т и Q через пробел (0 ≤ T, Q ≤ 106). За ними следуют Q строк – описания катапульт. i-я строка содержит пять чисел: x1, y1, x2, y2 и t, где (x1, y1) – координаты появления i-ой катапульты, (x2, y2) – координаты клетки, в которую она стреляет, t – секунда от начала шоу, во время которой катапульта работает (0 ≤ x1, x2 < N, 0 ≤ y1, y2 < M, 0 ≤ t ≤ 106). Гарантируется, что ни одна катапульта не стоит в клетке с суши-баром.
Выведите два целых числа через пробел – координаты клетки, в которой окажется участник через Т секунд.
3 3
oro
ooo
oso
4 1
1 1 2 2 2
2 1
3 3
dol
oso
rou
6 3
1 0 2 0 1
2 1 2 2 3
1 2 0 2 5
0 2
3 3
ooo
oso
ooo
2 0
1 1
У многих людей есть генеалогическое древо, но мало кто знает, что у пицц оно тоже есть. Всё потому что изначально был только один вид пиццы, а затем постепенно появлялись новые виды пицц. Новые пиццы появлялись не просто так – они основывались на своём предке - так постепенно появилось целое генеалогическое древо из пицц, где пиццы соединены линиями со своими предшественниками.
В пиццерии «Эль ням» работает величайший повар по имени Джордж Вкусняшков. Для него очень важно сочетание пицц, это буквально смысл его жизни. Поэтому он никогда не сделает заказ из двух пицц, если первая не является предком второй. Так как просмотр генеалогического древа перед выполнением каждого заказа занимает слишком много времени, администрация «Эль ням» решила автоматизировать данный процесс. Так как «Эль ням» просто пиццерия, здесь нет программистов, поэтому администрация просит вас помочь с решением данной проблемы.
Вам даны Q заказов на изготовление 2-ух пицц. Вам необходимо выяснить для каждого заказа, будет ли его делать Джордж Вкусняшков.
В первой строке указано целое число N – количество видов пицц (2 ≤ N ≤ 105). Далее следуют N-1 строк. Каждая строка содержит два натуральных числа a и b, которые означают, что a – пицца-предшественник b (1 ≤ a, b ≤ N), корнем древа пицц является пицца с номером 1.
Далее дано число натуральное Q (1 ≤ Q ≤ 105).
Далее следуют Q строк. Каждая строка содержит два натуральных числа А и В – заказ на две пиццы (1 ≤ А, В ≤ N).
Для каждого заказа в отдельной строке ответьте на вопрос: будет ли его готовить Джордж Вкусняшков, то есть является ли А предком В. В случае положительного ответа выведите “YES”, иначе “NO” (заглавными буквами).
8
1 6
1 7
6 5
6 8
6 2
8 4
8 3
7
1 7
1 3
6 4
4 3
6 5
5 6
3 7
YES
YES
YES
NO
YES
NO
NO
3
1 2
1 3
3
1 2
1 3
2 1
YES
YES
NO
В галактике Печеньковая Система находится планета Чаёчек. Жители планеты очень любят печеньки, поэтому каждый имеет своё хранилище печенек. У нашего героя, Ивана Ксеноморфа, тоже есть склад с печеньками. Так как он любит порядок во всём, его склад представляет собой прямоугольное здание размером N на M метров, причём всё пространство склада занимают ящики с печеньками с площадью основания 1 м2 каждый. В каждом ящике лежит определённое количество печенек.
Завтра к Ивану Ксеноморфу нагрянут родственники. Дабы не сильно крушить свой склад, он решил выбрать прямоугольник, состоящий из K ящиков с печеньками, и угостить родственников печеньками только из этих ящиков. Но так как Иван Ксеноморф не хочет делиться с другими своей прелестью, он хочет минимизировать количество печенек, которым он угостит гостей. Помогите Ивану Ксеноморфу сохранить как можно больше печенек себе.
В первой строке даны натуральные числа N и M (1 ≤ N, М ≤ 103) – размер склада Ивана Ксеноморфа.
Далее следуют N строк по М целых неотрицательных чисел в каждой. Где aij – количество печенек в j-ом ящике i-го ряда (0 ≤ aij ≤ 106).
В последней строке указанно единственное число K (1 ≤ K ≤ 103).
В единственной строке выведите число – минимальное количество печенек, которое придётся отдать гостям. Если ответа не существует, выведите «-1».
3 3
1 2 3
4 5 6
1 1 2
4
11
2 4
1 1 1 1
2 2 3 4
4
4
В первом примере минимальная сумма 11 = 4+5+1+1.
Во втором примере минимальная сумма 4 = 1+1+1+1.
На планете Обжорка, как и на любой другой существует общественный транспорт, в котором выдают билетики, причём номера билетиков состоят из 2N разрядов. На такой далёкой планете тоже существуют счастливые билетики в автобусах (сумма первых N разрядов равна сумме последних N разрядов), которые принято съедать. Так как власти на планете очень демократичны, все счастливые билетики съедобны, то есть, сделаны из пирожков. Существует ещё одно отличие от наших счастливых билетиков, а именно: существует K-ый счастливый билет, который, по легендам, сделан из самого вкусного пирожка во вселенной!
Боб Пирожкоман сегодня ехал из института на автобусе на планете Обжорка и ему попался билет с номером R (не счастливый). Он хочет узнать номер K-го счастливого билета и получить ответ на вопрос: есть ли у него шанс получить счастливый билет в будущем?
В единственной строке указаны три целых числа через пробел N, K и R (1 ≤ N ≤ 12, 1 ≤ K ≤ 1018, 0 ≤ R < 102N).
В единственной строке выведите число – K-ый счастливый билет. Через пробел укажите, есть ли шанс у Боба Пирожкомана получить его в будущем. Если шанс есть, то выведите “Try again”, иначе выведите “Sadness”.
2 9 0320
0321 Try again
3 1 000010
000000 Sadness
В кондитерской «Ля тортик» на улице Тарталеток продаются самые вкусные тортики и пироженки. Сегодня в этой прекрасной кондитерской произошло величайшее несчастье: Петя Криворук – главный кондитер – уронил В тортиков. Слёзы хозяина кондитерской затопили всю кухню. Его горю не было конца. Но необходимо было жить дальше и продолжать радовать детей и взрослых с улицы Тарталеток. Для начала нужно открыть кондитерскую. Для того чтобы начать продавать тортики, необходимо провести ревизию, то есть посчитать количество тортиков в наличии. Но убитый горем хозяин кондитерской не в состоянии этого сделать, а Петя Криворук находится в шоке от содеянного, ведь тортики – самое прекрасное, что есть в его жизни!
Автор задач сегодня посетил кондитерскую «Ля тортик» и от увиденного впал в унынье, поэтому он попросил Вас посчитать текущее количество тортиков в кондитерской, если считать, что до того как Петя Криворук уронил тортики – их было А штук.
В единственной строке даны целые числа А и В (1 ≤ А,В ≤ 109, А ≥ В).
Выведите единственное число – ответ на задачу.
1795735 4912
1790823
В волшебной стране находится бескрайнее поле. На этом поле растут шашлычки! Из земли в прямом смысле вырастают шампуры с нанизанными кусочками прожаренного на костре мяса. Также в поле находятся N столбов. Владелец поля с шашлыками, Милк Кукис, решил построить себе на своём поле дом (жить на поле с шашлыками… Что ещё для счастья надо?). Для того чтобы построить дом, нужно сначала определиться с его местоположением. Милк Кукис решил, что для удобства стоит натянуть верёвку между четырьмя уже существующими столбами и внутри образовавшегося четырёхугольника построить дом. Он хочет, чтобы территория, выделенная для постройки дома, была максимально приближена к числу K. Для решения этой проблемы Милк Кукис обратился к автору задач и пообещал ему шашлык. Милк Кукис попросил автора задач найти четыре столба, соединив которые, можно получить четырёхугольник (он может быть невыпуклым), площадь которого максимально приближена к числу K, причём Милк Кукису важна лишь площадь полученного четырёхугольника, поэтому он просит узнать именно её. Автор задач съел шашлык, а работу поручил Вам.
В первой строке через пробел даны числа N и K (4 ≤ N ≤ 200, 0 < K ≤ 106). N – натуральное число, K – вещественное число, с точностью до 10 - 4.
Далее следуют N строк. В i-ой строке указаны два числа xi и yi – координаты i-го столба. Обе координаты каждого столба по модулю не превосходят 500. Гарантируется, что никакие три точки не лежат на одной прямой.
В единственной строке выведите число – площадь четырёхугольника - наиболее близкое к числу K. Площадь выводить с точностью до 10 - 4. Если решений несколько, то выведите наибольшее.
6 6.000
0 4
1 2
4 4
3 2
4 0
0 0
6.0000
6 3.500
0 0
3 2
4 0
1 2
0 4
4 4
4