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

Восстановление скобок#23412

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

Входные данные
Вводится строка, которая содержит заданный шаблон длиной не более 80 символов.

Выходные данные
Выведите искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2·10⁹.

Примеры

№	Входные данные	Выходные данные
1	`????(?`	`2`

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

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

Главное правило личных олимпиад#60175

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

Промоделируем тур олимпиады. Пусть на туре предложено \(n\) задач, \(i\)-я задача состоит из \(k_i\) подзадач, \(j\)-я подзадача \(i\)-й задачи приносит \(c_{i, j}\) баллов. Зависимостей между подзадачами нет, поэтому можно в каждой задаче выбрать любое множество подзадач и его решить. При этом нельзя выбрать пустое множество, ведь тогда по задаче будет \(0\) баллов, а это противоречит главному правилу написания личных олимпиад.

Проверьте, можно ли, придерживаясь главного правила личных олимпиад, набрать на туре ровно \(s\) баллов.

Первая строка содержит два целых числа \(n\), \(s\) (\(1 \le n \le 100\,000\), \(1 \le s \le 100\,000\)) — количество задач в контесте и необходимую сумму баллов, соответственно. Далее следуют описания задач. Описание каждой задачи состоит из двух строк.

Формат входных данных
Первая строка описания \(i\)-й задачи содержит одно целое число \(k_i\) (\(1 \le k_i \le 100\,000\)) — количество подзадач в \(i\)-й задаче.

Вторая строка описания \(i\)-й задачи содержит \(k_i\) целых чисел \(c_{i, 1}, c_{i, 2}, \ldots, c_{i, k_i}\) (\(1 \le c_{i, j} \le 100\,000\)) — баллы за подзадачи.

Гарантируется, что сумма \(k_1+k_2+\ldots+k_n\) по всем задачам не превосходит \(100\,000\).

Гарантируется, что произведение \((k_1+k_2+\ldots+k_n)\cdot s\) не превосходит \(10^7\).

Формат выходных данных
Если решения не существует, выведите <<No>>.

В противном случае в первой строке выведите <<Yes>>. Далее необходимо вывести описание решенных подзадач для каждой задачи.

Описание \(i\)-й задачи начинается с целого числа \(m_i\) (\(1 \le m_i \le k_i\)) — количества решенных подзадач \(i\)-й задачи. Далее следуют \(m_i\) различных целых чисел \(p_{i, 1}, p_{i, 2}, \ldots, p_{i, m_i}\) (\(1 \le p_{i, j} \le k_i\)) — номера решенных подзадач в \(i\)-й задаче.

Если существует несколько подходящих способов набрать \(s\) баллов, выведите любое из них.

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

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

Шашку - в дамки#55458

На шахматной доске (8x8) стоит одна белая шашка. Сколькими способами она может пройти в дамки?

(Белая шашка ходит по диагонали. на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.)

Входные данные
Вводятся два числа от 1 до 8: номер столбца (считая слева) и номер строки (считая снизу), где изначально стоит шашка.

Выходные данные
Вывести одно число - количество путей в дамки.

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

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

Игра с монетами#55134

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

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

Ограничения: 1 <= N <= 180, 1 <= K <= 80, количество монет в стопке - не менее 1 и не более 20 000.

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

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

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

Космический мусорщик#54666

В околоземном космическом пространстве накопилось много мусора, поэтому ученые сконструировали специальный аппарат - ловушку для космического мусора. Для того, чтобы хорошо собирать мусор, этот аппарат должен двигаться по достаточно сложной траектории, сжигая собранный по пути мусор. Ловушка может передвигаться в пространстве по 6 направлениям: на север (N), на юг (S), на запад (W), на восток (E), вверх (U) и вниз (D). Движением ловушки управляет процессор. Программа движения задается шестью правилами движения, которые соответствуют каждому из указанных направлений. Каждое такое правило представляет собой строку символов из множества {N, S, W, E, U, D}.

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

Пусть, например, заданы следующие правила:

Направление	Правило
N	N
S	NUSDDUSE
W	UEWWD
E
U	U
D	WED

Тогда при выполнении команды S(3) мусорщик выполнит следующие действия:
1) переместится на 1 метр в направлении S
2) выполнит последовательно команды N(2), U(2), S(2), D(2), D(2), U(2), S(2), E(2).
Если далее проанализировать действия мусорщика при выполнении команд из пункта 2, получим, что в целом он совершит следующие перемещения:

SNNUUSNUSDDUSEDWEDDWEDUUSNUSDDUSEEПо заданной команде определите, какое общее количество перемещений на один метр совершит ловушка при выполнении заданной команды. В приведенном примере это количество равно 34.

Входные данные
Первые шесть строк входных данных задают правила для команд с направлением N, S, W, E, U и D соответственно. Каждая строка содержит не более 100 символов (и может быть пустой). Следующая строка содержит команду ловушки: сначала символ из множества {N, S, W, E, U, D}, затем пробел и параметр команды - целое положительное число, не превышающее 100.

Выходные данные
Выведите единственное число - количество перемещений, которое совершит ловушка. Гарантируется, что ответ не превышает 10⁹.

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

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

Кубики#54259

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

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

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

Входные данные
Вводятся два числа N и K (1≤N≤100, 1≤K≤100).

Выходные данные
Выведите одно число – количество различных лесенок. Гарантируется, что правильный ответ не будет превышать 10¹⁸.

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

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

Рейтинг#54215

Новый учитель математики ввел в школе оригинальную систему оценки учеников – рейтинговую. На каждом уроке школьнику предлагалось выполнить задание, состоящее из нескольких задач. После этого учитель увеличивал рейтинг школьника на число, равное отношению количества решенных им сегодня задач к количеству задач, решенных им на прошлом занятии. Например, если сегодня ученик решил 5 задач, а вчера – две, то к его рейтингу сегодня прибавится = 2.5. Изначально рейтинг равен нулю; он начинает увеличиваться со второго дня. Если в один из дней какой-то ученик не решал ни одной задачи, то учитель объявлял его полной бездарностью и переводил в другой класс (с облегченным изучением математики), поэтому каждый день все ученики старались решить хотя бы одну задачу.

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

Входные данные
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 1 000) – количество уроков, которые провел в школе учитель до того, как его уволили.

В следующей строке содержатся числа a₁, a₂, …, a_N– количество задач, которые учитель предложил школьникам на первом, втором, …, N-м уроках соответственно (1 ≤ a_i ≤ 100).

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

Во второй строке выведите N чисел – количество задач, которые должен решить школьник в каждый из дней. Если вариантов несколько, выведите один любой из них.

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

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

Хардсофт#50835

В ходе работы над оптимизацией компилятора для процессора из предыдущей задачи в фирме Хардсофт задумались об автоматическом выборе подпрограмм, которые станут инлайнподпрограммами. Инлайн-подпрограммы - это такой способ сборки машинного кода, при котором тело подпрограммы во время компиляции подставляется непосредственно в место её вызова, и оно становится частью вызывающего кода. Таким образом, исключаются накладные расходы на вызов и завершение подпрограмм во время работы.
Инженеры фирмы Хардсофт считают, что инлайн-подпрограммами надо делать те, которые вызываются чаще всего. Однако вставка кода больших подпрограмм в места их вызова приведёт к резкому увеличению памяти, потребляемой программами, а для фирмы важна возможность лёгкой адаптации своего решения к промышленным устройствам, в которых значительную роль играет экономическая составляющая: в частности, необходимый для работы объём памяти должен быть минимальным.
Разработчики создали специальный анализатор, который определяет среднее количество запуска подпрограмм и размер каждой из них.
Требуется определить, какие из подпрограмм можно встроить в инлайн-режиме, для увеличения быстродействия и в пределах доступной памяти.

Формат входных данных
в первой строке через пробел указаны натуральные числа N, M и X. N и M не превышают 100 и являются количеством подпрограмм и количеством цепочек вызова, а X не превышает 10⁶ и является количеством памяти (в килобайтах), доступным для размещения инлайнподпрограмм. Далее идёт N строк, где через пробел перечислены имена подпрограмм (из латинских слов длиной до 20 символов) и их размер в килобайтах (натуральное число от 1 до 1000). Далее - M строк с описанием выявленных цепочек вызова: в них записаны имена подпрограмм через пробел, после которых также через пробел указано ожидаемое количество срабатываний этой цепочки за время работы программы (целое число от 1 до 1000).
Формат выходных данных
в первой строке - количество подпрограмм, которые можно пометить инлайновыми, в последующих строках - имена этих подпрограмм в том порядке, в котором они были указаны во входных данных. Требуется выбрать подпрограммы так, чтобы количество вызовов инлайн-подпрограмм за время работы программы было максимальным.

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

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

Гирьки: четыре кучки#47780

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

Входные данные
Первая строка входных данных содержит натуральное число N, не превышающее 14. Далее идет N натуральных чисел mi, не превышающих 100.

Выходные данные
Программа должна вывести номера гирек для каждого из наборов в четыре строки или строчку No solution, если решения не существует.

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

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

Сумма фишек#47743

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

Входные данные
Программа получает в первой строке два числа: n - количество различных чисел, которые записаны на фишках, num - число, которое загадал Громозека. Во второй строке записаны n различных чисел c_i - числа, каждое из которых может быть записано на фишке. На каждой фишке записано только одно число из набора чисел c_i. При этом, количество фишек с числом c_i не ограниченно. Все фишки с одинаковым числом, считаются одинаковыми. Другими словами, комбинация фишек 2+1 и 1+2 считается одной комбинацией.

Ограничения

1 <= n <= 300
1 <= c_i <= 5000
Все значения c_i уникальны.
0 <= num <= 5000

Выходные данные
Выведите одно число - количество комбинаций, которым Алиса может выиграть Громозеку. Если Алиса не может выиграть, то выведите на экран 0.

Примечание
В первом примере есть 4 способа набрать сумму, равную 5:

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

Динамическое программирование Задача о рюкзаке

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

Наименьшая сумма ASCII кодов#47638

Вам даны две строки s1 и s2. Вы можете удалить из обоих строк любое количество символов. Ваша цель сделать строки одинаковыми.
Найдите наименьшую сумму ASCII кодов всех удаленных символов.

Входные данные
Программа получает на вход две строки s1 и s2.

Ограничения

1 <= длина s1 и s2 <= 1000;
s1 и s2 состоят из маленьких английских букв.

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	sea eat	231	Удаление "`s`" из слова "`sea`" добавляет к сумме ASCII код буквы "`s`" (115). Удаление буквы "`t`" из слова "`eat`" добавляет к сумме 116. В итоге обе строки равны, а `115 + 116 = 231` - минимально возможная сумма для достижения этой цели.

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

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

Симпатичные узоры#38607

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узоров из черных и белых плиток, каждая из которых имеет размер 1 х 1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника N х M метров. Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во-первых, каждый новый клиент, очевидно, захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во-вторых, этот узор должен быть симпатичным.

Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2 х 2 метра, полностью покрытого плитками одного цвета. Для составления финансового плана директору Васе необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!

Входные данные
Вводятся два положительных целых числа N и M (1 ≤ N · M ≤ 30).

Выходные данные
Выведите единственное число – количество различных симпатичных узоров, которые можно выложить во дворе размера N х M. Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.

Примеры

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

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

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

Ежедневные награды#38296

Миша установил на свой телефон новую игру «Мемтест 2к17». В ней предусмотрены ежедневные награды за посещение. Награды бывают n уровней. Тип награды зависит от награды за предыдущий день, а именно:

если игрок в предыдущий день не посещал игру, то за сегодняшнее посещение он получит награду уровня 1;
если игрок в предыдущий день зашёл в игру и получил награду уровня k ( k ≠ n ), то за сегодняшнее посещение он получит награду уровня k + 1 ;
если игрок в предыдущий день зашёл в игру и получил награду уровня n , то за сегодняшнее посещение он получит награду уровня 1.
На Форуме для Крутых Программистов Миша выяснил, что награды каждого из уровней составляют соответственно a 1 , a 2 , ..., a n золотых монет.
Через m дней состоится турнир по «Мемтест 2к17», к которому Миша хочет собрать как можно больше золотых монет. Помогите ему спланировать посещения игры на протяжении m дней, оставшихся до турнира. Найдите наибольшее количество золотых монет, которое он сможет получить за счёт ежедневных наград в этот период. Можно считать, что игра установлена в первый из этих m дней, то есть до этого Миша в неё ни разу не заходил.

Входные данные
Первая строка входных данных содержит натуральные числа n и m ( 1 ≤ n , m ≤ 1000 ) — количества уровней наград и дней до турнира.

Вторая строка входных данных содержит n целых чисел a 1 , a 2 , ..., a n ( 1 ≤ a i ≤ 1000 ), где a i — величина награды i -го уровня в золотых монетах.

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

Примечание
В первом тесте из примера Мише выгодно заходить в игру каждый день. Тогда он получит 1 + 2 + 4 = 7 золотых монет.

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

Примеры

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

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

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

Нужно больше золота#38286

Петя очень любит компьютерные игры. Недавно он обнаружил в интернете интересную ролевую игру. Управляя героем, надо искать магические артефакты и получать золото.

К сожалению, первый же квест в игре поставил Петю в тупик. Выполнив задание, он получил n магических артефактов, которые можно использовать для получения золота. Для каждого артефакта известна его ценность , для i -го артефакта она равна w_i . Для получения золота артефакты можно активировать . Каждый артефакт можно активировать только один раз. Петя может активировать артефакты в произвольном порядке.

У героя, которым управляет Петя, есть магическая сила , исходно она равна нулю. Есть два способа активировать артефакт: с помощью магии и с помощью силы. Если активировать артефакт с ценностью w с помощью магии, то магическая сила героя увеличивается на w . Если же активировать артефакт с ценностью w с помощью силы, то герой получает xw золотых монет, где x — магическая сила героя в момент активации артефакта.

Например, если герой Пети получил 4 артефакта с ценностями 1, 1, 2 и 2, то можно получить 9 золотых монет, действуя следующим образом. Сначала надо активировать с помощью магии по одному артефакту с ценностью 1 и 2. После этого магическая сила героя равна 3, теперь можно активировать с помощью силы оставшиеся артефакты и получить 3 и 6 золотых монет, соответственно.

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

Входные данные
Первая строка входных данных содержит единственное число n — количество магических артефактов ( 1 ≤ n ≤ 100 ).

Вторая строка входных данных содержит n чисел w₁ , w₂ , ..., w_n — ценности артефактов ( 1 ≤ w_i ≤ 100 ).

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

Примеры

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

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

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

Кинотеатр#38189

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

Входные данные
Вводятся два числа — X и Y (оба числа натуральные, не превосходящие 100).

Выходные данные
Выведите какую-нибудь строку, в которой будет ровно X символов B (обозначающих мальчиков) и Y символов G (обозначающих девочек), удовлетворяющую условию задачи. Пробелы между символами выводить не нужно. Если рассадить мальчиков и девочек согласно условию задачи невозможно, выведите строку NO SOLUTION.

Примеры

№	Входные данные	Выходные данные
1	5 5	BGBGBGBGBG
2	5 3	BGBGBBGB
3	100 1	NO SOLUTION

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

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

Наибольшая возрастающая подпоследовательность за O(n*log(n))#33231

Числовая последовательность задана рекуррентной формулой: a_i+1=(k * a_i+ b) mod m. Найдите длину её наибольшей возрастающей подпоследовательности.
mod - операция вычисления остатка от деления

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

Программа получает на вход пять целых чисел: длину последовательности n (1≤n≤10⁵), начальный элемент последовательности a₁, параметры k, b, m для вычисления последующих членов последовательности (1≤m≤10⁴, 0≤k<m, 0≤b<m, 0≤a1<m).

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

Требуется вывести длину наибольшей возрастающей подпоследовательности данной последовательности.

Примеры

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

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

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

Копилка#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.".

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

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

Сдача - 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средняяВойти и решать

Игра с пешкой#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

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

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

**Столовские котлеты#23380

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

Конечно, введенное правило оставляет существенный произвол в числе котлет, получаемых очередным явившимся лицеистом, и это число не в последнюю очередь будет зависеть от предыдущего поведения лицеиста в столовой, а также от волшебных слов, произносимых им. Например, 6 котлет могут быть в результате распределены по одной из следующих четырех схем: 3+2+1 (три котлеты первому из пришедших школьников, две - второму и одну - третьему), 4+2, 5+1 и 6 (все котлеты съедает счастливчик, пришедший первым).

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

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

Входной файл содержит одно целое число N - количество приготовленных поваром котлет (0<=N<=200).

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

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

Примеры

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

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

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