Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Играем в Камушки#37891

Когда-то в далеком детстве мы все с удовольствием играли в игру "Камушки" или "Пять камешков", кто как называл. Для игры нужны были обычные камешки, которые можно было запросто найти на улице. Играть можно было в любом месте, Для игры нужна была небольшая ровная площадка утоптанной земли или ровный пол крыльца или беседки.
Первый шаг игры заключался в следующем. На землю перед собой бросаются все пять камешков. Выбирался один из них. Это биток. Этот камешек подбрасывается в воздух и, пока он летит, необходимо поднять один из оставшихся на земле камешков и успеть подхватить этой же рукой летящий. Подобранный камешек откладывается в сторону и действие повторяется для всех оставшихся камешков.
На следующих шагах количество камешков, которые надо подхватить увеличивается. Последним шагом был экзамен, когда необходимо было подбросить все собранные камешки в воздух и поймать их тыльной стороной ладони, а затем опять подбросить, и поймать открытой ладонью. Сколько камешков в итоге оставалось, столько баллов и получаешь. Ход переходит к следующему игроку, который также повторяет все шаги. Далее запускался новый тур игры. Выигрывал тот, кто набирал больше всего баллов за все туры.
Многие ребята усложняли игру самыми разными способами.
Допустим у ребят есть бесконечное число камешков лежащих на земле. В конце тура им необходимо поймать в ладони не все камешки, а ровно столько, чтобы общее число баллов у них увеличилось на 1 или удвоилось или утроилось. Перед началом игры у всех уже имеется 1 балл. Победителем будет считаться тот, кто быстрее наберет N баллов.
Будем считать, что у всех играющих достаточно опыта игры, и они всегда доходят до экзамена с нужным им числом камней (чтобы была возможность нужное число баллов увеличить на 1, удвоить или утроить).

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

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

Программа получает на вход одно число, не превосходящее 10⁶.

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

Требуется вывести одно число: наименьшее количество искомых операций.

Примеры

№	Входные данные	Выходные данные
1	1	0
2	5	3
3	32718	17

Динамическое программирование: один параметр

✓ 472✗ 908600лёгкаяВойти и решать

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

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

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	1	2

Динамическое программирование: один параметр

✓ 844✗ 1 061400лёгкаяВойти и решать

Слинки "Радуга"#37889

Слинки — игрушка-пружина, созданная в 1943 году в США Ричардом Джеймсом. В нашей стране она называлась просто Радуга. Все дети любили ее запускать со ступенек, считая у кого она спустится ниже.
Обычно "Радуга" в руках детей спускалась на следующую ступеньку, на ступеньку через одну или через 2. (Например, если Радугу запускали с 10-ой ступеньки, то она могла остановиться на 9-ой, 8-ой или 7-ой.)
Допустим на лестнице N ступенек. Определите число всевозможных "маршрутов" Радуги с вершины лестницы на землю.

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	4	7

Динамическое программирование: один параметр

✓ 890✗ 1 263400лёгкаяВойти и решать

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	5 -1 2 3 -2 2	2 3
2	7 2 -2 3 -1 5 -2 7	3 7

Алгоритмы обработки Динамическое программирование: один параметр

✓ 806✗ 4 225800средняяВойти и решать

Гомер Симпсон#33650

Обеденный перерыв Гомера Симпсона составляет T миллисекунд. Один гамбургер Гомер съедает за N миллисекунд, один чизбургер - за M. Какое количество гамбургеров и чизбургеров нужно съесть, чтобы потраченное время было как можно больше, не превышая T. При равенстве потраченного времени необходимо максимизировать суммарное количество съеденных гамбургеров и чизбургеров.

Ограничения: 1 <=M, N, T, <= 1000000 , все числа целые.

Входные данные
В первой строке находятся три числа - M, N и T, разделённые пробелами.

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

Ввод	Вывод
1 2 1000	1000
2 1 1000	1000
3 6 1000	333 1

Задача о рюкзаке

✓ 41✗ 240600лёгкаяВойти и решать

Splash Bomb#33297

Имеется клетчатое поле размером NxM. В каждой клетке может лежать либо реактив A, либо B, либо ничего не лежать - 0. За ход можно положить в некоторую клетку реактив A, причем преобразование вещества идет по следующему правилу: 0+A->A, A+A->B, B+A->0. При этом в результате последней реакции происходит взрыв, а в соседние непустые клетки по сторонам света (если они есть), попадает по порции реактива A. Очки за ход = количество взрывов минус 1. Очки за отдельные ходы суммируются. Требуется очистить поле и при этом набрать максимальное количество очков.

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

В первой строке вводятся N и M (1 <= N, M <= 3). Далее идут N строк по M символов из алфавита (0, A, B) - описание поля.

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

Выведите единственное число - максимальное количество очков, которое можно набрать.

Комментарий ко второму примеру: за первый ход не произошло ни одного взрыва, очки=0-1=-1; за второй ход произошел один взрыв и поле очистилось, очки=1-1=0; итого очков: 0+(-1)=-1

Ввод	Вывод
1 1 0	0
1 1 A	-1

Динамическое программирование Задачи на моделирование Перебор

✓ 5✗ 781 200средняяВойти и решать

Ход конем - 2#33143

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:

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

Входные данные
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 15\)).

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

Примеры

№	Входные данные	Выходные данные
1	4 4	2
2	7 15	13309

Динамическое программирование: два параметра

✓ 238✗ 399700средняяВойти и решать

Ход конем_1#33142

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить ТОЛЬКО на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз (смотри рисунок).

Входные данные
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 50\)).

Примеры

№	Входные данные	Выходные данные
1	4 4	2

Динамическое программирование: два параметра

✓ 490✗ 656500лёгкаяВойти и решать

Лесопилка#33135

Недавно на лесопилку, где работает Вася, поступил новый заказ. Для постройки нового дома мэру соседнего города требуется a досок длины x футов и b досок длины y футов.

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

Например, если на лесопилке имеются доски длины 80, а клиенту требуется две доски длины 30 и семь досок длины 20, то достаточно сделать семь распилов: одну доску распилить двумя распилами на доски длины 20, 30 и 30, одну тремя распилами на четыре доски длины 20 и одну двумя распилами на доски длины 20, 20 и 40. Доска длины 40 клиенту не нужна, она останется на лесопилке, остальные доски будут отправлены клиенту.

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

На вход программы поступают числа a, x, b, y и z. Все числа положительны и не превышают 300, x<=z, y<=z, x!=y.

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

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

Ввод	Вывод
2 30 7 20 80	7

Динамическое программирование Остатки

✓ 7✗ 43900средняяВойти и решать

Камни#33133

На столе лежат N камней. За ход игрок может взять:

- 1 или 2 камня, если N делится на 3;

- 1 или 3, если N при делении на 3 дает остаток один;

- 1, 2 или 3, если N при делении на 3 дает остаток два.

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

Входные данные: вводится целое число \(0 < N <= 100\).

Выходные данные: выведите 1 или 2 – номер игрока, который выиграет при правильной игре.

Примеры

№	Входные данные	Выходные данные
1	1	1
2	3	2

Динамическое программирование: один параметр Простые игры

✓ 827✗ 1 043500лёгкаяВойти и решать

Обработка больших данных#33128

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

позволяющая эффективно обрабатывать большие объемы данных.

Суперкомпьютер имеет 2^k ячеек памяти, пронумерованных от 0 до 2^{k– 1}. Отрезком

[L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R,

включительно.

Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является

корректным, если его длина (R – L + 1) равна 2i для некоторого i, а число L делится на 2i.

Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются

отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,

6] и [7, 7].

Ключевой операцией в новой архитектуре является операция STORE, которая за одно

действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного

отрезка.

Исходно все ячейки памяти содержат значение 0. В лаборатории планируют запустить

на суперкомпьютере программу обработки данных, но перед её запуском необходимо

инициализировать память определенным образом. А именно: первые с1 ячеек памяти

необходимо заполнить значениями v1, следующие c2 ячеек — значениями v2, и так далее,

последние cn ячеек памяти необходимо заполнить значениями vn, где 1 ≤ vi ≤ m.

Ученым надо выяснить, какое минимальное количество операций STORE необходимо

выполнить, чтобы проинициализировать память требуемым образом.

Например, если k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, то итоговое

содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для

инициализации памяти достаточно трех операций STORE:

- STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;

- STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];

- STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],

как и требуется.

Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не

является корректным отрезком памяти.

Требуется написать программу, которая по заданному содержимому памяти

определяет минимальное количество операций STORE, которое необходимо выполнить для

инициализации памяти заданным образом.

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

Первая строка входных данных содержит три целых числа: k, n и m (0 ≤ k ≤ 30,1 ≤ n ≤ 10

5, 1 ≤ m ≤ 10⁹).

Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа ci

и vi (1 ≤ ci ≤ 2^k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2^k).

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

Требуется вывести одно целое число – минимальное количество операций STORE,

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

Ввод	Вывод
3 3 2 1 1 2 2 5 1	3

Динамическое программирование Множества Структуры данных

✓ 0✗ 101 300средняяВойти и решать

Мониторинг труб#33124

Газораспределительная система одного региона устроена следующим образом. Она

содержит n узлов, пронумерованных от 1 до n, некоторые узлы соединены односторонними

трубами. Узел с номером 1 соответствует центральному газохранилищу.

Система узлов описывается числами от p2, p3, …, pn. Для всех i от 2 до n узел с

номером pi соединен односторонней трубой с узлом i, газ по этой трубе передается от узла pi

к узлу i. Известно, что возможно доставить газ по трубам от центрального газохранилища до

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

используются трубы различных типов, тип трубы обозначается буквой английского алфавита

от «a» до «z». Труба, соединяющая узел pi с узлом i, имеет тип ci.

Для проверки качества труб используется специальный робот. Он помещается в

систему труб в одном из узлов и перемещается по трубам, каждый раз проверяя трубу, по

которой он перемещается. Робот может перемещаться по трубам только в том же

направлении, в котором по трубе передается газ. Совершив одно или несколько

перемещений по трубам между узлами, робот извлекается из системы труб.

Каждый запуск робота должен соответствовать одной из m заданных спецификаций,

пронумерованных от 1 до m. Спецификация с номером t представляет собой строку st,

состоящую из строчных букв английского алфавита. Запуск соответствует спецификации st,

если количество перемещений робота по трубам во время запуска совпадает с длиной st, и

для всех j от 1 до длины st на j-м шаге робот перемещается по трубе, тип которой совпадает с

st[j] —символом на позиции j в спецификации.

Если запуск робота соответствует спецификации с номером t, то стоимость этого

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

можно запускать робот несколько раз. Каждый раз выбирается спецификация и маршрут

робота по трубам, соответствующие выбранной спецификации. Необходимо проверить все

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

минимальна. Одну и ту же трубу можно проверять несколько раз.

Требуется написать программу, которая по описанию системы труб и списку

спецификаций определяет минимальную суммарную стоимость запусков робота, в

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

запусков (по требованию).

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

В первой строке входных данных находятся три целых числа n, m и t — количество

узлов системы труб, количество спецификаций запусков робота и параметр, указывающий,

требуется ли вывести список запусков робота или только их минимальную суммарную

стоимость (1 ≤ n ≤ 500, 1 ≤ m ≤ 10⁵, t равно 0 или 1).

В последующих (n – 1) строках содержится информация о трубах, (i – 1)-я из этих

строк содержит разделенные пробелом значения pi и ci, где pi — целое число, задающее

номер узла, из которого ведет труба в i-й узел, а ci — строчная буква английского алфавита,

задающая тип этой трубы (1 ≤ pi ≤ i – 1).

В последующих m строках содержится информация о спецификациях, i-я из этих

строк содержит разделенные пробелом целое число wi — стоимость запуска робота в

соответствии с этой спецификацией, и состоящую из строчных букв английского алфавита

строку si — саму спецификацию (1 ≤ wi ≤ 10⁹). Суммарная длина строк si не превышает 10⁶.

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

Первая строка выходных данных должна содержать одно число — минимальную

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

Если проверить все трубы невозможно, требуется вывести «–1».

Если t = 0, то больше ничего выводить не требуется.

Если t = 1 и проверить трубы возможно, то далее следует вывести список описаний

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

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

следующих k строках необходимо вывести по три целых числа ai, bi и ci — номер узла, в

котором начинается запуск, номер узла, в котором заканчивается запуск, и номер

спецификации, которой соответствует запуск.

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

Ввод	Вывод
3 3 0 1 a 2 b 3 a 4 b 2 a	6
7 3 1 1 a 2 a 3 b 3 b 1 b 6 b 3 aab 5 b 2 ab	15 4 1 4 1 2 5 3 1 6 2 6 7 2

Пояснение к примеру

Система труб, заданная во втором примере входных данных, и оптимальный способ

проверки всех труб для этого случая приведены на рисунке ниже.

Необходимо обратить внимание на следующие моменты:

- трубу можно проверять несколько раз, так в приведенном примере дважды

проверена труба из узла 2 в узел 3;

- одну и ту же спецификацию разрешается использовать несколько раз, в

приведенном примере вторая спецификация используется дважды, для

проверки труб из узла 1 в узел 6 и из узла 6 в узел 7;

- робот может перемещаться по трубам только в том же направлении, по

которому по трубе передается газ, спецификацию «ab» нельзя использовать

для проверки труб по маршруту 2→1→6, так как робот не может

переместиться из узла 2 в узел 1.

Алгоритмы на графах Деревья Динамическое программирование

1 300средняяВойти и решать

Копилка#33105

Задан вес E пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов, для каждого вида известна ценность P_i и вес W_i одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.

Входные данные
В первой строке находятся числа E и F (1 <= E <= F <= 10000). Во второй - число N (1<= N <= 500). В следующих N строках - по два числа, P_i и W_i(1 <= P_i <= 50000, 1 <= W_i <= 10000). Все числа целые.

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

Задача о рюкзаке

✓ 219✗ 391800средняяВойти и решать

Сдача - 1#33104

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P₁, P₂, ..., P_N рублей. У продавца есть M банкнот номиналом Q₁, Q₂, ..., Q_M. рублей. Определите, смогут ли они рассчитаться.

Входные данные:
- в первой строке задается сумма S;
- во второй строке - число N;
- в третьей строке - N чисел P₁, P₂, ..., P_N;
- в четвертой строке - число M;
- в пятой строке - M чисел Q₁, Q₂, ..., Q_M.
Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

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

Если они не могут рассчитаться, выведите строку Impossible.

Примеры

№	Входные данные	Выходные данные
1	10 3 3 9 14 2 6 2	-2 +9 +3
2	100 3 74 35 8 2 19 6	Impossible

Задача о рюкзаке

✓ 73✗ 1851 000средняяВойти и решать

Гирьки#33088

Дан набор гирь массой m₁, …, m_N. Можно ли их разложить на две чаши весов, чтобы они оказались в равновесии?

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

- в первой строке вводится натуральное число N, не превышающее 100;

- во второе строке вводятся N натуральных чисел m_i, не превышающих 100.

Выходные данные: выведите YES или NO.

Примеры

№	Входные данные	Выходные данные
1	1 17	NO
2	2 19 19	YES

Задача о рюкзаке

✓ 239✗ 425600лёгкаяВойти и решать

0-1 рюкзак: минимум предметов#33087

Дано N предметов массой m₁, …, m_N. Ими наполняют рюкзак, который выдерживает вес не более M. Как набрать вес в точности M, используя как можно меньше предметов?

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

- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

- во второе строке вводятся N натуральных чисел m_i, не превышающих 100.

Выходные данные: выведите наименьшее необходимое число предметов или 0, если набрать данный вес невозможно.

Примеры

№	Входные данные	Выходные данные
1	1 5968 18	0

Задача о рюкзаке

✓ 372✗ 1 268600лёгкаяВойти и решать

0-1 рюкзак: наибольший вес#33086

Дано N золотых слитков массой m₁, …, m_N. Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую массу золота можно унести в таком рюкзаке?

Входные данные:
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

- во второй строке вводятся N натуральных чисел m_i, не превышающих 100.

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

Примеры

№	Входные данные	Выходные данные
1	2 3195 38 41	79

Задача о рюкзаке

✓ 655✗ 1 001400лёгкаяВойти и решать

Задача о рюкзаке с восстановлением ответа#33081

Дано N предметов массой m₁, …, m_N и стоимостью c₁, …, c_N соответственно.

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

Входные данные:
- в первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000;

- во второй строке вводятся N натуральных чисел m_i, не превышающих 100;

- в третьей строке вводятся N натуральных чисел с_i, не превышающих 100.

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

Примеры

№	Входные данные	Выходные данные
1	4 6 2 4 1 2 7 2 5 1	1 3 4

Задача о рюкзаке

✓ 401✗ 847600лёгкаяВойти и решать

Сборка компьютера#31928

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

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

Первая строка ввода содержит одно целое число – количество типов компонентов T (1 ≤ T ≤ 5). Вторая строка ввода содержит одно целое число – количество компонентов в магазине N (1 ≤ N ≤ 1000). Далее следует N строк, содержащих по три целых числа, разделенных пробелами – стоимость i-го компонента C_i (1 ≤ C_i ≤ 3000), его рейтинг R_i (1 ≤ R_i ≤ 3000) и его тип t_i (1 ≤ t_i ≤ T). Далее следует строка, содержащая одно целое число – бюджет на покупку компьютера B (1 ≤ B ≤ 3000).

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

Ввод	Вывод
2 5 10 6 1 5 7 1 6 10 2 1 5 1 11 11 2 16	18 2 5

Динамическое программирование

✓ 9✗ 711 100средняяВойти и решать

Игра с пешкой#31781

В левой нижней клетке шахматной доски размера N×N стоит пешка. Двое игроков по очереди двигают её, причём каждый может подвинуть её на одну клетку вверх или на одну клетку вправо. На диагонали доски написаны числа a₁, a₂, …, a_N. Когда пешка попадает на диагональ, игра кончается и выигрыш первого игрока равен значению числа, написанного в клетке с остановившейся пешкой. Напишите программу определения гарантированного выигрыша первого игрока.

3
	1
		4
			1
				5
					9
						2
							6

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

В первой строке записано число N (1 ≤ N ≤ 100). Во второй строке записаны натуральные числа a₁, a₂, …, a_N (1 ≤ a_i ≤ 100).

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

Выведите одно число – выигрыш первого игрока.

Ввод	Вывод
8 3 1 4 1 5 9 2 6	5

Динамическое программирование на таблицах Простые игры

✓ 91✗ 311800средняяВойти и решать