Кузнечик-KMax

Примеры

Покупка билетов

Примеры

Камни

Примеры

Хлебные крошки

Заботливые хозяева квартиры заботятся о таракане Василии. Вечером они выкладывают для него в ряд N хлебных крошек, которые он очень любит. Переходя от одной хлебной крошки к другой, таракан Василий может съесть ее, а может и не съесть. Но он никогда не ест две хлебные крошки подряд.
Посчитайте сколько различных вариантов полакомиться хлебными крошками есть у таракана Василия.

Входные данные

На вход программы поступает целое число N  (\(1<=N<=100\) ).

Выведите ответ на задачу.

Примеры

Словарь

У Васи на клавиатуре не работает клавиша пробел. Поэтому все тексты он теперь набирает слитно. Напишите программу, которая будет разделять набранный Васей текст на слова из данного словаря.

Входные данные
Сначала на вход программы поступает текст, введенный Васей – одна строка из не более чем 100 латинских строчных букв. В следующей строке входных данных задается значение N – количество слов в словаре (N – натуральное число, не превосходящее 2000). В следующих N строках записаны слова из словаря – по одному слову в  строке, каждое слово содержит не более 20 латинских строчных букв. Слова записаны в алфавитном порядке.


Выходные данные
Выведите Васин текст с пробелами между словами (пробел после последнего слова допустим). Если возможно несколько вариантов разбиения строки на слова, выведите  любой их них. Гарантируется, что хотя бы один способ разбиения строки на словарные слова существует.

Примеры

Валютные махинации

Петя, изучая, как меняется курс рубля по отношению к доллару и евро, вывел закон, по которому происходят эти изменения (или думает, что вывел). По этому закону Петя рассчитал, каков будет курс рубля по отношению к доллару и евро в ближайшие N дней.

У Пети есть 100 рублей. В каждый из дней он может обменивать валюты друг на друга по текущему курсу без ограничения количества (при этом курс доллара по отношению к евро соответствует величине, которую можно получить, обменяв доллар на рубли, а потом эти рубли — на евро). Поскольку Петя будет оперировать не с наличной валютой, а со счетом в банке, то он может совершать операции обмена с любым (в том числе и нецелым) количеством единиц любой валюты.

Напишите программу, которая вычисляет, какое наибольшее количество рублей сможет получить Петя к исходу N-го дня.

Законы изменения курсов устроены так, что в течение указанного периода рублевый эквивалент той суммы, которая может оказаться у Пети, не превысит 10⁸ рублей.

Входные данные
Первая строка входного файла содержит одно число N (1≤N≤5000). В каждой из следующих N строк записано по 2 числа, вычисленных по Петиным законам для соответствующего дня — сколько рублей будет стоить 1 доллар, и сколько рублей будет стоить 1 евро. Все эти значения не меньше 0.01 и не больше 10000. Значения заданы точно и выражаются вещественными числами не более, чем с двумя знаками после десятичной точки.

Выходные данные
В выходной файл выведите искомую величину с точностью не менее двух знаков после десятичной точки.
 

Примеры

Поход

Группа школьников решила сходить в поход вдоль Москвы-реки. У Москвы-реки существует множество притоков, которые могут впадать в нее как с правого, так и с левого берега.

Школьники хотят начать поход в некоторой точке на левом берегу и закончить поход в некоторой точке на правом берегу, возможно, переправляясь через реки несколько раз. Как известно, переправа как через реку, так и через приток представляет собой определенную сложность, поэтому они хотят минимизировать число совершенных переправ.

Школьники заранее изучили карту и записали, в какой последовательности в Москву-реку впадают притоки на всем их маршруте.

Помогите школьникам по данному описанию притоков определить минимальное количество переправ, которое им придется совершить во время похода.

Входные данные
Единственная строка содержит описание Москвы-реки между начальной и конечной точкой похода. Длина строки не превосходит 10⁵ символов.

Каждый символ строки может быть одной из трех латинских букв L, R или B. Буква L означает, что очередной приток впадает в реку с левого берега, R - приток впадает в реку с правого берега и B - притоки впадают с обоих берегов реки в одном месте. Поход начинается на левом берегу перед описанной частью реки и заканчивается на правом берегу после описанной части.

Выходные данные
Выведите одно целое число - минимальное количество переправ.

Примечания
Рисунок к приведенному ниже примеру.

Примеры

Практический тест

У нас есть сетка с H строками и W столбцами. Квадрат в i-й строке и j-м столбце будет называться Square(i, j). Целые числа от 1 до H·W записаны по всей сетке, а целое число, записанное в Square(i, j), равно Ai,j.
Вы - волшебник (волшебница), и можете телепортировать фигуру, помещенную на Square(i, j) в Square(x, y), потратив \(|x-i|+|y-j|\) маджиков (магических монет).
Теперь вам нужно пройти Q практических тестов на свои способности как волшебника (волшебницы). I-е испытание будет проводиться следующим образом:
- первоначально фигура располагается в квадрате, где записано целое число Li;
- пусть x будет целым числом, записанным в квадрате, занятом фигурой. Неоднократно переместите фигуру в квадрат, где написано целое число x+D, пока x не станет равен Ri. Тест заканчивается, когда x = Ri .
Гарантируется, что Ri- Li делится на D.
Для каждого теста найдите сумму маджиков, израсходованных во время этого теста.

Входные данные
В первой строке заданы три целых числа: H, W и D (\(1\leq H,W \leq 300\), \(1 \leq D \leq H \cdot W\)).
В следующих H строках записано по W чисел Ai,j (\(1 \leq A_{i,j} \leq H \cdot W\), \(A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))\).
В следующей строке записано целое число Q (\(1 \leq Q \leq 10^5\)).
В последних Q строках записано по 2 целых числа: Li и Ri (\(1 \leq L_i \leq R_i \leq H \cdot W\)), \((R_i-L_i)\) кратно D.

Выходные данные
Для каждого теста выведите сумму маджиков, израсходованных во время этого теста. Вывод должен быть в порядке проведения тестов.
 

Примеры

Мячик на лесенке

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну или через 2. (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 5-ую, 6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.

Вводится одно число 0 < N < 31.

Выведите одно число — количество маршрутов.
 

Примеры

Ладья Громозеки

Любимая шахматная фигура Громозеки - это ладья. Но он любит ходить ей только по вертикали, причем либо на одну клетку, либо на две. Громозека заканчивает игру, когда ладья доходит до конца вертикали. Подумав над очередной позицией, он заметил, что некоторые клетки на пути ладьи находятся под ударом фигур соперника и ходить на эти клетки нельзя.
Помогите Громозеке посчитать сколькими способами он может перевести ладью c 1 горизонтали на другой конец шахматного поля, не попадая на клетки под ударом. 

Входные данные
В первой строке вводится одно натуральное число N (N <= 40): размер шахматного поля. Во второй строке вводится одно натуральное число K (K <= N): количество клеток, находящихся под ударом. В третьей строке вводятся K различных натуральных чисел в диапазоне от 1 до N: номера клеток, находящихся под ударом фигур соперника.

Выходные данные
Выведите одно число  - количество способов попасть на конец вертикали (на N-ю клетку).
 

Примеры

Ограждение

Примеры

Кузнечик и лягушки

Числа Фибоначчи: Мемоизация рекурсии (Python)

Числа Фибоначчи, обозначаемые обычно F(n) образуют последовательность, называемую последовательностью Фибоначчи, такую, что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.

По заданному n, вычислите F(n) (0 <= n <= 80).

(в коде программы длина одного отступа равна 4 пробелам!)

Примеры

Подняться на вершину горы (снизу-вверху)

Робот Сильвер занимается терроформированием на планете Шелезяка. Сейчас робот находится перед лестницей, ведущей на вершину горы. Лестница состоит из n ступенек. Робот, поднимаясь вверх, может пойти на одну или сразу две ступеньки.
Пока робот поднимается на вершину, вы хотите определить, сколько существует различных способов, которыми он может добраться до последней ступеньки этой лестницы и тем самым оказаться на вершине горы.

Входные данные
Программа получает на вход одно целое число  n - количество ступенек в лестнице (1 <= n <= 45).

Выходные данные
Выведите одно число - количество способов добраться до вершины горы.
 
Попробуйте решить эту задачу без использования массивов и других структур данных! Другими словами, ваша программа должна использовать фиксированный объем памяти, не зависящий от входных данных (О(1)).
 

Примеры

Подняться на вершину горы (рекурсивно)

Робот Сильвер занимается терроформированием на планете Шелезяка. Сейчас робот находится перед лестницу, ведущей на вершину горы. Лестница состоит из n ступенек. Робот, поднимаясь вверх, может пойти на одну или сразу две ступеньки.
Пока робот поднимается на вершину, вы хотите определить, сколько существует различных способов, которыми он может добраться до последней ступеньки этой лестницы и тем самым оказаться на вершине горы.

Входные данные
Программа получает на вход одно целое число  n - количество ступенек в лестнице (1 <= n <= 45).

Выходные данные
Выведите одно число - количество способов добраться до вершины горы.
 
 

Примеры

Стоимость проезда

Робот Сильвер едет по шоссе. Вдоль дороги стоят n пунктов оплаты — по одному на каждый километр. На пункте i написана плата cost[i]: столько робот отдаёт, если останавливается у этого пункта. Пункт, мимо которого он проехал не останавливаясь, не оплачивается.
Перед шоссе есть бесплатный въезд, а после — бесплатный съезд. Робот стартует со въезда, едет только вперёд, и от каждой остановки до следующей проезжает 1 или 2 пункта. Доехать ему надо до съезда.
Найдите наименьшую сумму, которую заплатит робот.

Формат входных дынных
В первой строке записано количество пунктов оплаты n (2 <= n <= 1000). Во второй строке записыны n целых чисел (costi) - стоимость проезда через i-й пункт оплаты (1 <= i <= n, 0 <= costi <= 999).

Формат выходных дынных
Выведите одно число - ответ на задачу.

Маршрут наименьшей стоимости

Робот Сильвер движется по платному шоссе на планете Шелезяка. На каждом километре шоссе расположен пункт оплаты. Всего на шоссе n пунктов оплаты. Первый пункт оплаты находится в самом начале шоссе, n-й пункт оплаты находится в начале последнего километра шоссе. Заплатив нужную сумму в i-м пункте оплаты, робот может двигаться дальше либо до следующего пункта оплаты, либо же до того, который находится через 2 километра (то есть, если робот находится в пункте i, то он может двигаться либо до пункта i+1, либо до пункта i+2). Первую оплату можно сделать либо в первом пункте, либо во втором (на выбор). Если оплаты была произведена в предпоследнем (n-1) пункте, то можно просто доехать до конца  шоссе, не оплачивая проезд в последнем пункте.
Зная стоимость проезда через определенный пункт оплаты, помогите роботу Сильверу найти наименьшую стоимость проезда через все шоссе, которую должен будет заплатить Сильвер, а также пункты оплаты, на которых ему необходимо будет остановиться. 

Входные данные
В первой строке записано количество пунктов оплаты n (2 <= n <= 1000). Во второй строке записыны n целых чисел (costi) - стоимость проезда через i-й пункт оплаты (1 <= i <= n, 0 <= costi <= 999).

Выходные данные
Выведите в первой строке наименьшую стоимость проезда через шоссе. 
Во второй строке выведите через пробел номера пунктов оплаты (по возрастанию), на которых роботу придется остановиться, чтобы оплатить проезд. Если вариантов маршрута с остановками в пунктах оплаты несколько, то выведите любой из них.
 
 

Примеры

Магическая энергия

Вы - маг, который хочет собирать магическую энергию из домов вдоль улицы. В каждом доме сосредоточена определенная магическая энергия, и единственным ограничением является то, что если вы извлекаете магическую энергию из двух соседних домов в одну и ту же ночь, то это вызывает негативные последствия для вас и окружающей среды.

Зная уровень магической энергии в каждом доме, найдите максимальное количество магической энергии, которое вы можете собрать сегодня, избегая извлечения энергии из соседних домов в одну и ту же ночь. Кроме этого, определите заранее какие дома вы должны посетить?

Входные данные
В первой строке записано число n - количество домой вдоль улицы. Во второй строке - n целых чисел ai - количество магической энергии в i-м доме.

Ограничения на входные данные 

• 1 <= n <= 100
• 0 <= a[i] <= 400
• 1 <= i <= n

Выходные данные
Выведите в первой строке максимальное количество магической энергии, которую вы сможете собрать. Во второй строке выведите номера домов (в порядке возрастания, через пробел), которые вы посетите.
 

Примеры

Магическая сила

Вы - маг, странствующий по волшебному лесу, в поисках своей утраченной магической силы. Эта магическая сила находится в волшебных кристаллах, которые растут на деревьях в этом волшебном лесу. На каждом дереве растет только один волшебный кристалл. Так как вы маг, то вы знаете какой силой обладает тот или иной кристалл, растущий на определенном дереве в этом лесу. Вы хотите получить в этом лесу как можно больше магической силы. Для этого вам следует выполнить следующее действие любое количество раз:

• Выберите любое дерево и соберите волшебный кристалл, который растет на нем, чтобы получить его магическую силу. Помните, что после того как был сорван кристалл с определенной силой, все кристаллы, чья сила на один меньше или на один больше, чем сила кристалла, который вы только что собрали, сами исчезают, оставляя вас с магической силой, равной силе собранного кристалла.

Определите максимальную магическую силу, которую вы можете получить, применяя вышеуказанное действие любое количество раз.

Входные данные
Первая строка входных данных содержит число n - количество деревьев в волшебном лесу. Вторая строка содержит n чисел ai - волшебная сила кристалла на i-м дереве.

Ограничения на входные данные

• 1 <= n <= 2 * 104
• 1 <= a[i] <= 104
• 1 <= i <= n

Выходные данные
Выведите максимальную магическую силу, которую вы можете получить.
 

Примеры

В фантастическом лесу

В фантастическом лесу живут различные существа, каждое из которых имеет свой уникальный номер, начинающийся с 1. Также у каждого существа есть свой уровень энергии, представленный целым числом. У первого существа уровень энергии равен 1. Каждое последующее существо имеет уровень энергии, который зависит от уникального номера существа. В общем виде уровень энергии существа можно выразиить следующим образом:

• creature[1] = 1
• creature[2 * i] = creature[i], если  2 <= 2 * i <= n
• creature[2 * i + 1] = creature[i] + creature[i + 1], при  2 <= 2 * i + 1 <= n

Примеры

Выборы

Скоро в Соединенных Штатах Берляндии пройдут выборы президента. На эту ответственную должность претендуют два кандидата: Дядя Сэм и Дядя Фродо. Вы работаете аналитиком в пред- выборном штабе Дяди Сэма, и вам поручено помочь ему победить конкурента. Раздуть газетный скандал из одержимости оппонента бросанием колец в жерла вулканов не получилось, так что при- дётся воспользоваться математикой.

Казалось бы, чтобы выиграть, необходимо убедить проголосовать за нашего кандидата более половины пришедших на выборы. Оказывается, что иногда нужно гораздо меньше! Для того чтобы понять, как это возможно, рассмотрим подробнее процедуру голосования.

Как вы знаете, Соединенные Штаты Берляндии разделены на несколько административных ре- гионов первого уровня — штатов. Сначала в каждом из штатов проходят местные выборы, по итогам которых каждый штат отдаёт свой голос за одного из кандидатов. Если не менее половины штатов выбрало Дядю Сэма, то выигрывает он (в случае равенства голосов Дядя Сэм имеет преимущество как действующий президент), иначе побеждает Дядя Фродо. Все штаты, в свою очередь, состоят из административных регионов второго уровня, каждый из которых представлен выборщиком из административных регионов третьего уровня и так далее. Последний уровень состоит из отдельных жителей Берляндии. Всего в Берляндии N жителей и K уровней административных единиц. Одним из ключевых принципов этой страны является равенство, так что любой регион i-го уровня делится на одинаковое число регионов следущего уровня (в том числе содержит одинаковое число граждан).

Так получилось, что делением на регионы поручили заняться именно вам, то есть в ваших руках назначить, на сколько именно административных единиц i-го уровня делится (i−1)-ая администра- тивная единица.

Также у вас есть сильный инструмент влияния на выбор людей — нефтяные бурли. Чтобы заста- вить одного избирателя отдать свой голос за Дядю Сэма, достаточно дать ему скромный подарок в размере одного нефтяного бурля.

К несчастью, изначально все N жителей Соединённых Штатов Берляндии собираются отдать свой голос за Дядю Фродо. Требуется определить минимальное количество нефтяных бурлей, ко- торое достаточно потратить для победы на выборах.

Формат входных данных

В единственной строке ввода находятся два целых числа N и K (1 <= N <= 10¹⁵ , 1 <= K <= 10).

Формат выходных данных
Требуется вывести единственное число — минимальное количество нефтяных бурлей, которое придётся потратить на предвыборные подарки при наилучшем разбиении на регионы.

Примеры

Trapped in the Haybales

Ноутбук за печеньки

Летовец обладает неудивительными математическими способностями. Его способности на столько велики, что он легко может просчитать стоимость его любимых печенек, которые продаются на другом конце города. К сожалению, Летовец не может по максимуму воспользоваться всеми своими способностями, потому что вчера у него сломался ноутбук и теперь он не может писать программы. 
Чтобы купить себе новый ноутбук, Летовец решил потратить все свои карманные деньги (а это всего лишь 10 рублей) на покупку своих любимых печенек, а чуть позже, продать все купленные им печеньки. 
Так как  Летовец еще несовершеннолетний и один ездить на другой конец города не может, ему нужно понять, в какие из двух дней попросить маму отвезти его на другой конец города. Мама всегда готова ему помочь.
Отсутствие ноутбука очень угнетает юного Летовца, поэтому он просит вас определить эти два дня в ближайшие N дней. 

Формат входных данных
В первой строке записано число N (2 <= N <= 100000) количество дней, на которые Летовец делает прогноз. Вторая строка содержит N целых положительных чисел ai (1 <= i <= N , 1 <= a_i <=  5000 ), где ai - предсказанная стоимость печенек в i-й день.

Формат выходных данных

Выведите два числа: первое число - номер дня, в который Летовей поедет покупать печеньки, второе - номер дня, в который он поедет продавать печеньки. В случае, если таких вариантов дней несколько, выведите любой из них. Если Летовец в итоге не сможет получить прибыль ни при каких вариантах, то выведите два нуля.

Призы

Миша участвует в процедуре награждения на интеллектуальном шоу. В процессе награждения ему последовательно предлагают призы. У каждого приза есть стоимость. Про каждый приз Миша должен заявить, хочет ли он его взять. После того, как Миша возьмет или пропустит приз, ему показывается следующий, и так далее, вернуться к предыдущим призам и изменить свое решение нельзя.

В качестве первого приза Миша может взять любой приз, а затем Миша может взять приз, если его стоимость строго больше стоимости предыдущего взятого им приза.

Миша подсмотрел сценарий шоу и знает стоимости призов, а также порядок, в котором они будут ему предлагаться. Помогите ему выбрать призы таким образом, чтобы их суммарная стоимость была как можно больше.

Формат входных данных
Первая строка ввода содержит целая число \(n\) — количество призов (\(1 \le n \le 1000\)). Вторая строка содержит \(n\) чисел \(a_1, a_2, \ldots, a_n\) — стоимости призов в том порядке, в котором их покажут Мише (\(1 \le a_i \le 10^9\)).

Формат выходных данных
Выведите одно число — максимальную суммарную стоимость призов, которые может получить Миша.

Выражение

Петя - большой любитель математических головоломок. Недавно он прочитал в одном популярном журнале о новой головоломке. Он пытался ее решить несколько дней, но это ему так и не удалось. Помогите Пете справиться с неподдающейся задачей.

В ряд выписаны n чисел. Требуется поставить между каждой парой соседних чисел один из знаков "+" или "×" таким образом, чтобы значение получившегося выражения было как можно больше. Использовать скобки не разрешается.

Например, для последовательности чисел 1, 2, 3, 1, 2, 3 оптимально расставить знаки следующим образом: 1 + 2 × 3 × 1 × 2 × 3. Значение выражения в этом случае равно 37.

Входные данные
В первой строке вводится число n (2 <= n <= 200000). Вторая строка содержит n целых чисел - числа, между которыми следует расставить знаки. Все числа находятся в диапазоне от 0 до 10⁹.

Выходные данные
Выведите оптимальное выражение. В качестве знака "×" выводите символ "*" (звездочку). Если оптимальных решений несколько, выведите любое из них.

Перекраска N-угольника

В правильном N-угольнике провели некоторые диагонали так, что он оказался разбит на треугольники. Изначально стороны N-угольника и все его диагонали черные.

Разрешается выбрать четырехугольник, в котором ровно одна диагональ, и при этом эта диагональ черного цвета (сам четырехугольник не обязан быть полностью черным) и проделать с ним следующее: заменить диагональ на противоположную (т.е. если сам четырехугольник был ABCD и в нем была диагональ AC, то она меняется на диагональ BD), после чего перекрасить стороны этого четырехугольника и новую диагональ в красный цвет.

Требуется определить, можно ли с помощью таких операций сделать так, чтобы все отрезки (т.е. стороны N-угольника и изображенные диагонали) стали красными, и не осталось бы ни одного черного отрезка. А если это возможно, то какое минимальное количество операций для этого требуется.

Входные данные
Вводится сначала число N (3≤N≤30000). Далее идет описание N–3 проведенных диагоналей. Каждая диагональ описывается двумя натуральными числами — номерами вершин, которые она соединяет. Гарантируется, что проведенные диагонали внутри N-угольника не пересекаются.

Выходные данные
Выведите минимальное число действий, необходимое для того, чтобы перекрасить весь N-угольник и все его диагонали. Если перекрасить многоугольник указанным способом невозможно, выведите одно число –1 (минус один).

Заполните массив

Требуется заполнить N элементов массива, пронумерованных числами от 1 до N (A[1]…A[N]), натуральными числами от 2 до N+1, использовав каждое число ровно один раз, так, чтобы значение каждого элемента массива делилось бы нацело на его номер (т.е. для каждого i A[i] делилось бы на i).

Напишите программу, которая для заданного N вычислит количество способов такого заполнения массива.

Входные данные
Вводится одно натуральное число N (1≤N≤1000).

Выходные данные
Выведите одно число — искомое количество способов заполнения массива.

Примечание
Массив можно заполнить единственным способом: 3 2
 

Взрывоопасность

При переработке радиоактивных материалов образуются отходы двух видов — особо опасные (тип A) и неопасные (тип B). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N
 определить количество возможных типов безопасных стопок.

Входные данные
Одно число 1 ≤ N ≤ 20.

Выходные данные
Одно число — количество безопасных вариантов формирования стопки.

Примечание
В примере из условия среди стопок длины 2 бывают безопасные стопки типов AB, BA и BB. Стопки типа AA являются взрывоопасными.

Самый дешевый путь

Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.


Входные данные

В первой строке входного файла вводится одно натуральное число 𝑁≤100 — количество ступенек.
В следующей строке вводятся 𝑁 натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх).

Выведите одно число — наименьшую возможную стоимость прохода по лесенке.

Cow Hopscotch (Bronze)

Фермер Джон придумал игру для своих коров.

Она играется на решётке R*C (2 <= R <= 15, 2 <= C <= 15), где каждый квадрат раскрашем красным либо синим цветом. Коровы начинают в левом верхнем углу и двигаются в правый нижний последовательными прыжками. Прыжок является корректным если и только если:

1) Вы прыгаете на квадрат другого цвета

2) Квадрат, куда Вы прыгаете, как минимум на одну строку ниже квадрата, в котором Вы сейчас стоите

3) Квадрат, в который Вы прыгаете как минимум на одну колонку правее квадрата, в котором Вы сейчас стоите

Пожалуйста, помогите коровам вычислить количество возможных различных последовательностей корректных прыжков из левого верхнего квадрата в правый нижний.

Формат входных данных

Первая строка содержит два целых числа R и C. Каждая из следующих R строк содержит ровно C символов. Каждый символ или R или B (обозначающих соответтсвенно красный или синий квадрат)

Формат выходных данных

Выведите количество различных способов пропрыгать из левого верхнего угла в правый нижний.

Secret Cow Code

Коровы экспериментируют с секретными кодами, и они изобрели метод для создания строки с бесконечной длиной которая может быть использована для кодирования.

Пусть дана строка \(s\), назовём \(F(s)\) строку \(s\) за которой идёт строка \(s\) "циклически сдвинутая" на один символ вправо (последний символ становится новым первым символом). По заданной строке \(s\), коровы строят свою строку бесконечной длины повторя применение \(F\); каждый шаг удваивает длину текущей строки.

Вам дана начальная строка и индекс \(N\), помогите коровам вычислить символ на позиции \(N\), в этой бесконечной строке.

Fruit Feast

Беси забралась на кухню Фермера Джона и обнаружила там кучу лимонов и апельсинов там (неограниченное количество и того и другого) и хочет съесть как можно больше .

Максимум сытости Беси равен \(T\) (\(1 \le T \le 5,000,000\)). Поедание апельсина увеличивает её сытость на \(A\), а поедание лимона увеличивает её сытость на \(B\) (\(1 \le A, B \le T\)). Дополнительно, если она хочет, Беси может попить воды не более одного раза, что мгновенно уменьшит её сытость вдвое (с округлением вниз).

Помогите определить Беси максимальную сытость, которую она сможет достичь.

Balancing a Tree

Фермер Джон изучает эволюцию пород коров. Результат - корневое дерево с \(N\) (\(2\le N\le 10^5\)) вершинами, помеченными \(1\ldots N\), каждая вершина соответствует одной породе коров. Для каждого \(i\in [2,N]\), родитель вершины \(i\) есть вершина \(p_i\) (\(1\le p_i<i\)), это означает, что порода \(i\) эволюционировала из породы \(p_i\). Вершина \(j\) называется предком вершины \(i\), если \(j=p_i\) или \(j\) предок вершины \(p_i\).

Каждая вершина \(i\) в этом дереве ассоциируется с породой, имеющей целое число пятен \(s_i\). Дисбалансом такого дерева называется максимум \(|s_i-s_j|\) по всем парам \((i,j)\) таким, что \(j\) есть предок \(i\).

Фермер Джон не знает точное значение \(s_i\) для каждой породы, но он знает нижнюю и верхнюю границу этих величин. Ваша задача - назначить значения \(s_i \in [l_i,r_i]\) (\(0\le l_i\le r_i\le 10^9\)) каждой вершине так, чтобы минимизировать дисбаланс этого дерева.

Snakes

У Беси есть сеть ловить змеек, распределённых в \(N\) групп на линии \((1 \leq N \leq 400)\). Беси должна поймать каждую змейку в каждой группе. Каждый раз, когда Беси ловит группу она может переложить змеек в клетку и начать пустой сеткой ловить следующую группу.

Сеть размером \(s\) означает, что Беси может поймать любую группу, которая содержит \(g\) змеек, где \(g \leq s\). Однако каждый раз, когда Беси ловит группу змеек размером \(g\) сетью размером \(s\), она тратит впустую \(s - g\) пространства. Беси может начинать с сети любого размера и Беси может изменять размер своей сети \(K\) раз \((1 \leq K < N)\).

Выведите минимальное количество потерянного пространства, которого может добиться Беси после вылавливания всех групп змеек.

Problem_648

ЃҐбЁ ЁЈа Ґв ў ЁЈаг.

€Ја  ­ зЁ­ Ґвбп б Ї®б«Ґ¤®ў вҐ«м­®бвЁ Ё§ \(N\) Ї®«®¦ЁвҐ«м­ле 楫ле зЁбҐ« (\(2 \leq N \leq 262,144\)), Є ¦¤®Ґ ў ¤Ё Ї §®­Ґ \(0 \ldots 40\). ‡  ®¤Ё­ 室 ЃҐбЁ ¬®¦Ґв ‚§пвм ¤ў  б®бҐ¤­Ёе а ў­ле зЁб«  Ё § ¬Ґ­Ёвм Ёе ­  зЁб«® ­  1 Ў®«миҐ (­ ЇаЁ¬Ґа, ®­  ¬®¦Ґв § ¬Ґ­Ёвм ¤ўҐ б®бҐ¤­ЁҐ 7 ­  ®¤­г 8). –Ґ«м ЁЈал - ¬ ЄбЁ¬Ё§Ёа®ў вм §­ зҐ­ЁҐ б ¬®Ј® Ў®«ми®Ј® зЁб« , Є®в®а®Ґ ®­  ¬®¦Ґв Ї®«гзЁвм. Џ®¬®ЈЁвҐ Ґ©.

Џђ€Њ…ђ ‚‚Ћ„Ђ:

4
1
1
1
2

Џђ€Њ…ђ ‚›‚Ћ„Ђ:

3

‚ ЇаЁ¬ҐаҐ ЃҐбЁ б­ з «  б«Ёў Ґв ўв®аго Ё ваҐвмо 1 Ё Ї®«гз Ґв Ї®б«Ґ¤®ў вҐ«м­®бвм 1 2 2 ,   § вҐ¬ б«Ёў Ґв ¤ўҐ ¤ў®©ЄЁ ў 3. ‡ ¬ҐвЁ¬, зв® ­Ґ ®ЇвЁ¬ «м­® б«Ёў вм ЇҐаўлҐ ¤ўҐ Ґ¤Ё­Ёжл.

Ђўв®а: Mark Chen Bessie likes downloading games to play on her cell phone, even though she does find the small touch screen rather cumbersome to use with her large hooves.

She is particularly intrigued by the current game she is playing. The game starts with a sequence of \(N\) positive integers (\(2 \leq N \leq 262,144\)), each in the range \(0 \ldots 40\). In one move, Bessie can take two adjacent numbers with equal values and replace them a single number of value one greater (e.g., she might replace two adjacent 7s with an 8). The goal is to maximize the value of the largest number she can create. Please help Bessie score as highly as possible!

The Cow Run

Фермер Джон забыл заделать дыру в изгороди на своей ферме и его N (1 <= N <= 1,000) коров сбежали и бедокурят. Каждая минута, когда корова находится вне изгороди, она "бедокурит" на 1 доллар. ФД должен посетить каждую корову, чтобы "усмирить" ее и прекратить долларовые потери от нее.
К счастью, коровы находятся вдоль одной прямой на различных растояниях от фермы. ФД знает расстояние P_i (-500,000 <= P_i <= 500,000, P_i != 0) каждой коровы i относительно ворот (позиция 0), из которых он стартует.
ФД двигается на 1 единицу расстояния за минуту и "усмиряет" корову мгновенно. Определите порядок, в котором ФД дожен посещать коров, так чтобы минимизировать свои долларовые потери.
PROBLEM NAME: cowrun
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..N+1: Строка i+1 содержит целое число P_i.
Формат выходных данных
* Строка 1: Минимальная общая стоимость долларовых потерь
Примечание
Оптимальный порядок посещения --2, 3, 7, -12. ФД прибудет в позицию -2 на 2-ой минуте и получит ущерб в два доллара от этой коровы.
Потом он проследует в позицию 3 (расстояние 5), итого ущерб = 2+5=7 долларов от второй коровы.
Затем он потратит 4 минут чтобы добраться до коровы в позиции 7, с общей стоимостью потерь от этой коровы 7+4 = 11 долларов.
Наконец, он потратит 19 минут чтобы перейти в точку -12, и стоимость потерь от этой коровы будет 11 + 19 = 30 долларов.
Общие потери от всех коров будут 2 + 7 + 11 + 30 = 50 долларов.

Bookshelf

Когда Фермер Джон не доит коров, собирает сено, выстраивает коров или строит изгороди, он сидит и читает хорошую книгу. С годами он собрал коллекцию из N книг (1 <= N <= 100,000), и хочет построить для них новое множество книжных полок.
Каждая книга I имеет ширину W(i) и высоту H(i). Книги необходимо ставить на полки в определенном порядке; например, первая полка должна содержать книги с номерами от 1 до k для некоторого k. Вторая полка должна содержать книгу k+1 и т.д. Каждая полка имеет общую ширину не более L (1 <= L <=1,000,000,000). Высота полки равна высоте самой высокой книги на этой полке, а высота множества книжных полок равна сумме высот на всех полках, поскольку полки ставятся одна поверх другой.
Помогите ФД вычислить минимально возможную высоту всего множества книжных полок.
PROBLEM NAME: bookshelf
Формат входных данных
* Строка 1: два разделенных пробелом целых числа: N и L.
* Строки 2..1+N: Строка i+1 содержит два разделенных пробелом целых числа : H(i) W(i). (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L).
Формат выходных данных
* Строка 1: Минимально возможная высота множества полок.
Примечание
Всего 3 полки. Первая содержит книгу 1 (высота 5, ширина 7), вторая содержит книги 2..4 (высота 13, ширина 9), третья содержит книгу 5 (высота 3, ширина 8).

Кролик и морковки

Кролик Роджер находится в начале числовой прямой (позиция 0) и хочет добраться  до позиции N, где лежит гигантская морковка.

Кролик умеет делать только два вида прыжков:
- Короткий прыжок: +1 позиция (тратит 1 единицу энергии)
- Длинный прыжок: +2 позиции (тратит 1 единицу энергии)

Сколько РАЗЛИЧНЫХ способов есть у Роджера добраться до морковки?

Два способа считаются различными, если последовательность прыжков отличается.

ВХОДНЫЕ ДАННЫЕ:
Одно число N (0 ≤ N ≤ 45) - позиция морковки.

ВЫХОДНЫЕ ДАННЫЕ:
Одно число - количество различных способов добраться до морковки.

Подарки под ёлкой

Под ёлкой лежит N подарков в ряд. Известна радость, которую принесёт каждый подарок. По традиции Простоквашино, нельзя брать два соседних подарка — это невежливо. Дядя Фёдор хочет выбрать подарки так, чтобы суммарная радость была максимальной.

Входные данные: В первой строке число N (1 ≤ N ≤ 10). Во второй строке N целых чисел от 1 до 1000 — радость от каждого подарка.

Выходные данные: Максимальная суммарная радость.

Разделить конфеты

Старец Летовец, известный своей любовью к математике, решил проверить смекалку своих учеников. Он дал им n конфет и сказал: "Разложите эти конфеты на три кучки так, чтобы в каждой кучке было не больше, чем limit. И определите сколькими различными способами это можно сделать?"

Напишите программу, которая поможет ученикам получить ответ на вопрос Летовца.

Формат входных данных
В первой строке входных данных записано натуральное число n, во второй - натуральное число limit.

Ограничения

• 1 <= n <= 1000
• 1 <= limit <= 1000

Совсем как огуречик

На числовой прямой в точке с координатой \(0\) сидит кузнечик. За одно действие он может выбрать любое целое неотрицательное число \(k\) и прыгнуть влево или вправо на расстояние \(2^k\).

Помогите кузнечику определить, какое минимальное количество действий ему понадобится выполнить, чтобы из точки с координатой \(0\) попасть в точку с координатой \(x\).

Формат входных данных
В первой строке дано одно целое число \(t\) — количество наборов входных данных (\(1 \le t \le 100\,000\)).

Каждый набор входных данных состоит из единственной строки, в которой дано целое число \(x\) — координата точки, в которую хочет попасть кузнечик (\(-10^{18} \le x \le 10^{18}\)).

Формат выходных данных
Для каждого набора входных данных выведите одно целое число — минимальное количество действий, которое кузнечику понадобится совершить.

Скобки(3)

Определим правильные скобочные выражения так:

Пустое выражение - правильное.
Если выражение S правильное, то (S) и [S] также правильные.
Если выражения A и B правильные, то и выражение AB - правильное.
Дана последовательность скобок "(", ")", "[" и "]". Требуется найти самое короткое правильное выражение, в котором данная последовательность является подпоследовательностью, то есть такое, из которого можно вычеркнуть некоторые символы (возможно, ноль) и получить исходную последовательность, не меняя порядок оставшихся.

Ограничения: исходная последовательность содержит не более 100 скобок.

Входные данные
В первой строке находятся символы (, ), [ и ] без пробелов.

Выходные данные
Выводится искомая последовательность скобок без пробелов.

Примеры

Реформы в королевстве

В одном королевстве есть \(n\) городов, расположенных вдоль длинной прямой дороги, \(i\)-й город расположен на расстоянии \(x_i\) километров от начала дороги (\(0 \le x_1 < x_2 < \ldots < x_n \le 10^9\)).

В ближайшее время король планирует провести реформу управления королевством и разделить его на \(k\) провинций. Каждый город должен войти ровно в одну провинцию.

В каждую провинцию войдет от \(a\) до \(b\) городов, причем эти города должны иметь следующие подряд номера. Таким образом, каждая провинция характеризуется числами \(i\) и \(l\), для которых \(1 \le i\), \(i + l - 1 \le n\), \(a \le l \le b\) и в провинцию входят города с номерами \(i, i + 1, \ldots, i + l - 1\).

Чтобы минимизировать затраты на обслуживание провинций, король хочет, чтобы максимальное расстояние между городами, входящими в одну провинцию, было как можно меньше. Помогите королю выполнить разделение королевства.

Формат входных данных
Первая строка ввода содержит четыре целых числа: \(n\), \(k\), \(a\) и \(b\) (\(1 \le n \le 200\), \(1 \le k \le n\), \(1 \le a \le b \le n\), \(ak \le n \le bk\)). Вторая строка ввода содержит \(n\) целых чисел: \(x_1, x_2, \ldots, x_n\) (\(0 \le x_1 < x_2 < \ldots < x_n \le 10^9\)).

Формат выходных данных
Выведите одно целое число: минимальное возможное \(z\), такое чтобы можно было разбить города на провинции описанным образом, и расстояние между городами внутри одной провинции не превышало \(z\).

Примечание
В примере оптимально первые 4 города объединить в первую провинцию, а пятый и шестой — во вторую. Максимальное расстояние между двумя городами в одной провинции: \(13 - 6 = 7\).

Разбиение на тройки

На день рождения Маше как обычно подарили массив \(a\) из \(n\) натуральных чисел, в котором каждое число находится в пределах от \(1\) до \(m\) включительно. Маша очень любит число три, поэтому длина массива делится на три.

Маша решила объединять числа в тройки: каждая тройка чисел должна состоять или из трех одинаковых чисел, или из трех последовательных чисел. Другими словами, каждая тройка имеет или вид \((x, x, x)\), или \((x, x+1, x+2)\), где \(x\) — какое-то натуральное число.

Маша хочет поиграть с подаренным массивом, и ее интересует количество способов разбить числа этого массива на такие тройки. Два способа разбиения считаются различными, если нельзя установить взаимно-однозначное соответствие между тройками первого разбиения и тройками второго разбиения, что числа внутри соответствующих троек равны. Так как количество разбиений может быть большим, Маше достаточно знать его остаток по модулю \(10^9+7\).

Помогите Маше посчитать количество способов разбить числа подаренного ей массива на тройки по модулю \(10^9+7\).

Формат входных данных
Первая строка входных данных содержит два целых числа \(n\) и \(m\) (\(1 \le n \le 5000\), \(1 \le m \le 5000\), \(n=3\cdot k\) для какого-то натурального \(k\)).

Вторая строка содержит \(n\) целых чисел \(a_i\) — числа массива (\(1 \le a_i \le m\)).

Формат выходных данных
В единственной строке одно число — количество способов разбить числа массива на тройки по модулю \(10^9+7\).

В первом примере числа можно разбить на тройки двумя способами: {\((2, 2, 2)\), \((3, 3, 3)\), \((4, 4, 4)\)} и {\((2, 3, 4)\), \((2, 3, 4)\), \((2, 3, 4)\)}.

Эксперименты Шелдона

Юному Шелдону очень интересно проводить эксперименты, результатом которых являются различные последовательности чисел. После проведения очередных экспериментов, Шелдон получил определенную последовательность чисел и заинтересовался вопросом, сможет ли он из исходной последовательности вычеркнуть некоторые числа таким образом, чтобы оставшиеся числа образовывали возрастающую подпоследовательность, где каждый элемент строго больше предыдущего. Шелдон хочет вычеркнуть как можно меньше чисел (в том числе, если можно, то ничего не вычеркивать). 
Теперь он хочет узнать, сколько существует различных вариантов выбрать одну такую подпоследовательность из данной последовательности чисел. Помогите юному Шелдону найти ответ для заданной последовательности чисел.

Входные данные
Первая строка содержит натуральное число n - длина последовательности Шелдона. Вторая строка содержит n чисел - элементы последовательности (numsi).
 

Ограничения

• 1 <= n <= 2000
• -106 <= numsi <= 106

Примеры

5
1 3 5 4 7

2

2

5
2 2 2 2 2

5

Поиск подотрезка массива с максимальной суммой

Дана последовательность из N целых чисел. Рассматриваются все её непрерывные подпоследовательности. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. В ответе укажите количество элементов в этой подпоследовательности.

Сумма чисел в массиве

Дан массив произвольных целых чисел. Напишите программу, которая за один проход по массиву находит непрерывный кусок, сумма чисел в котором максимальна.
Примечание. Фактически требуется найти такие i и j (i<=j), что сумма всех элементов массива от ai до aj включительно будет максимальна. Индексация элементов начинается с 1.

Входные данные
В первой строке задается натуральное число n <= 100000 — количество элементов в массиве. В следующих n строках задаются сами элементы массива — целые числа, по модулю не превосходящие 30 000.

Выходные данные
Выведите пару искомых значений индексов. Если таких пар несколько, то j должно быть минимально возможным, а при равных j значение i должно быть максимально возможным. В первой строке выведите i, во второй - j.
 

Примеры

Зоомагазин

Кузнечик

Пароль

Пути в музее

Пустоты в кубе

Число способов

Задача Иосифа Флавия