Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.
В первой строке входного файла вводится одно натуральное число \(N \leq 100 -\) количество ступенек.
В следующей строке вводятся \(N\) натуральных чисел, не превосходящих 100 \(-\) стоимость каждой ступеньки (снизу вверх).
Выведите одно число \(-\) наименьшую возможную стоимость прохода по лесенке.
| Ввод | Вывод |
|---|---|
3 1 3 1 |
2 |
Черепаха хочет переползти из левого верхнего угла поля размером \(N\) на \(M\) клеток \((1 \leq N\),\(M \leq 1000)\) в правый нижний. За один шаг она может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Определите, сколькими различными способами Черепаха может добраться до цели.
Поскольку количество способов, которое нужно найти, может быть очень велико, вычислите егопо модулю \(10^6 + 7\), то есть найдите остаток от деления этого числа на \(10^6 + 7\).
Входная строка содержит два натуральных числа: размеры поля \(N\) и \(M\), разделенные пробелом (\(1 \leq N, M \leq 1000\)).
Программа должна вывести одно число: количество различных маршрутов из левого верхнего угла поля в правый нижний по модулю \(10^6 + 7\).
| Ввод | Вывод |
|---|---|
20 20 |
16385 |
Черепаха хочет переползти из левого верхнего угла поля размером \(N\) на \(M\) клеток (\(2 \leq N,M \leq 1000\)) в правый нижний. За один шаг она может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Кроме того, проходя через каждую клетку, Черепаха получает (или теряет) несколько золотых монет (это число известнодля каждой клетки).
Определите, какое максимальное количество монет может собрать Черепаха по пути и как ей нужно идти для этого.
В первой строке вводятся два натуральных числа: \(N\) и \(M ( 2 \leq N,M \leq 1000 )\), разделённые пробелом. В каждой из следующих \(N\) строк записаны через пробел по \(M\) чисел, которые обозначают количество монет, получаемых Черепашкой при проходе через каждую клетку. Если это число отрицательное, Черепашка теряет монеты.
В первой строке программа должна вывести наибольшее количество монет, которое может собрать Черепаха. Во второй строке без пробелов выводятся команды, которые нужно выполнить Черепахе: буква 'R' (от слова right) обозначает шаг вправо, а буква 'D' (от слова down) – шаг вниз. Если ответов несколько, выведите самый нижний маршрут.
| Ввод | Вывод |
|---|---|
3 3 0 2 -3 2 -5 7 1 2 0 |
6 RRDD |
По данному натуральному \(n\) определите количество последовательностей длины \(n\) из 0, 1 и 2, не содержащих двух единиц подряд. Гарантируется, что ответ не превосходит \(2^{31} - 1\).
Вводится натуральное число.
Выведите ответ на задачу.
| Ввод | Вывод |
|---|---|
2 |
8 |
Лесенкой называется набор кубиков, в котором каждый горизонтальный слой содержит меньше кубиков, чем слой под ним.
|
|
|
|
|||||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
Подсчитать количество различных лесенок, которые могут быть построены из \(N\) кубиков.
Вводится одно число \(N (1 \leq N \leq 150)\).
Выведите искомое количество лесенок.
| Ввод | Вывод |
|---|---|
3 |
2 |
Родители подарили мальчику Пете очень много одинаковых кубиков. Наиболее интересным сооружением из кубиков Петя счел двусторонние лесенки.
В основании (нижнем ряду) такой лесенки расположено \(N\) кубиков, а каждый следующий ряд кубиков укладывается на предыдущий так, что один кубик укладывается ровно на один нижестоящий кубик, а по крайней мере на самый правый и самый левый кубики предыдущего ряда новые кубики не кладутся (чтобы получилась ступенька).
Петя поручил старшему брату подсчитать, сколько можно построить различных лесенок, состоящих из ровно \(K\) рядов кубиков, в основании которых лежит ровно \(N\) кубиков. При этом, если одну лесенку можно получить из другой путем зеркального отображения, то они все равно считаются различными.
Вводятся два числа \(N\) и \(K (1 \leq N \leq 100, 1 \leq K \leq 100)\).
Выведите одно число – количество различных лесенок. Гарантируется, что правильный ответ не будет превышать \(10^{18}\)
| Ввод | Вывод |
|---|---|
10 4 |
84 |
Около Петиного университета недавно открылось новое кафе, в котором действует следующая система скидок: при каждой покупке более чем на 100 рублей покупатель получает купон, дающий право на один бесплатный обед (при покупке на сумму 100 рублей и меньше такой купон покупатель не получает).
Однажды Пете на глаза попался прейскурант на ближайшие \(N\) дней. Внимательно его изучив, он решил, что будет обедать в этом кафе все \(N\) дней, причем каждый день он будет покупать в кафе ровно один обед. Однако стипендия у Пети небольшая,и поэтому он хочет по максимуму использовать предоставляемую систему скидок так, чтобы его суммарные затраты были минимальны. Требуется найти минимально возможную суммарную стоимость обедов и номера дней, в которые Пете следует воспользоваться купонами.
В первой строке входного файла записано целое число \(N (0 \leq N \leq 100)\). В каждой из последующих \(N\) строк записано одно целое число, обозначающее стоимость обеда в рублях на соответствующий день. Стоимость — неотрицательное целое число, не превосходящее 300.
В первой строке выдайте минимальную возможную суммарную стоимость обедов. Во второй строке выдайте два числа \(K_1\) и \(K_2\) — количество купонов, которые останутся неиспользованными у Пети после этих \(N\) дней и количество использованных им купонов соответственно.
В последующих \(K_2\) строках выдайте в возрастающем порядке номера дней, когда Пете следует воспользоваться купонами. Если существует несколько решений с минимальной суммарной стоимостью, то выдайте то из них, в котором значение \(K_1\) максимально (на случай, если Петя когда-нибудь ещё решит заглянуть в это кафе). Если таких решений несколько, выведите любое из них.
| Ввод | Вывод |
|---|---|
5 35 40 101 59 63 |
235 0 1 5 |
Новый учитель математики ввел в школе оригинальную систему оценки учеников – рейтинговую. На каждом уроке школьнику предлагалось выполнить задание, состоящее из нескольких задач. После этого учитель увеличивал рейтинг школьника на число, равное отношению количества решенных им сегодня задач к количеству задач, решенных им на прошлом занятии. Например, если сегодня ученик решил 5 задач, а вчера – две, то к его рейтингу сегодня прибавится 2.5. Изначально рейтинг равен нулю; он начинает увеличиваться со второго дня. Если в один из дней какой-то ученик не решал ни одной задачи, то учитель объявлял его полной бездарностью и переводил в другой класс (с облегченным изучением математики), поэтому каждый день все ученики старались решить хотя бы одну задачу.
Школьники быстро обнаружили, что для получения наибольшего рейтинга им далеко не всегда нужно решать все задачи. Им известно, сколько задач учитель будет давать в каждый из дней. Помогите им определить, в какой день сколько задач следует решить, чтобы в итоге получить наибольший рейтинг.
В первой строке вводится одно натуральное число \(N (1 \leq N \leq 1 000)\) – количество уроков, которые провел в школе учитель до того, как его уволили.
В следующей строке содержатся числа \(a_1,a_2, \dots, a_N -\) количество задач, которые учитель предложил школьникам на первом, втором, \(\dots\), \(N\)-м уроках соответственно \((1 \leq a_i \leq 100)\).
В первой строке выведите максимальный рейтинг, который может получить школьник за \(N\) дней, с точностью не менее 0.001.
Во второй строке выведите \(N\) чисел – количество задач, которые должен решить школьник в каждый из дней. Если вариантов несколько, выведите один любой из них.
| Ввод | Вывод |
|---|---|
3 1 2 3 |
4.00000 1 1 3 |
3 1 10 8 |
10.800000 1 10 8 |