|
|
Компьютерная игра (платформы)Калькулятор Имеется калькулятор, который выполняет три операции:
Определите кратчайшую последовательность операций, необходимую для получения из числа 1 заданное число N. Входные данные Программа получает на вход одно число N, не превосходящее 106. Выходные данные Выведите строку, состоящую из цифр "1", "2" или "3", обозначающих одну из трех указанных операций, которая получает из числа 1 число N за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них. Пример
Разложение в сумму кубов Дано натуральное число N. Необходимо представить его в виде суммы точных кубов, содержащей наименьшее число слагаемых. Программа должна вывести это число слагаемых и разложение в виде суммы. Если возможных решений несколько, выведите любое из них.
Входные данные Программа получает на вход натуральное число N, не превосходящее 106. Выходные данные Программа должна вывести число слагаемых и разложение в виде суммы кубов. Примеры Входные данные 9Выходные данные 2 2^3+1^3Входные данные 27Выходные данные 1 3^3Взрывоопасность-2 При переработке радиоактивных материалов образуются отходы трех видов — особо опасные (тип A), неопасные (тип B) и совсем не опасные (тип C). Для их хранения используются одинаковые контейнеры. После помещения отходов в контейнеры последние укладываются вертикальной стопкой. Стопка считается взрывоопасной, если в ней подряд идет более одного контейнера типа A. Стопка считается безопасной, если она не является взрывоопасной. Для заданного количества контейнеров N определить число безопасных стопок. Входные данные Одно число 1 Выходные данные Одно число — количество безопасных вариантов формирования стопки. Примечание Примеры Входные данные Выходные данные
Опасные ступеньки: количество способов Вася каждый день поднимается по одной и той же лестнице. Одним шагом он может встать на следующую ступеньку или перешагнуть через одну ступеньку. Он уже знает, сколькими способами он может подняться на верхнюю ступеньку. Но недавно он обнаружил, что некоторые ступеньки обветшали, и ступать на них небезопасно. Он составил список таких ступенек, и теперь интересуется, сколькими способами можно подняться по лестнице, не наступая на эти ступеньки. Входные данные В первой строке вводится одно натуральное число N (N < 40): количество ступенек. Во второй строке вводится одно натуральное число K (K <= N): количество опасных ступенек. В третьей строке вводятся K различных натуральных чисел в диапазоне от 1 до N: номера опасных ступенек. Выходные данные Выведите одно число: количество способов попасть на N-ю ступеньку. Примеры Входные данные 1035 1 2Выходные данные 0Входные данные 312Выходные данные 1Входные данные 723 5Выходные данные 2
Платная лестница Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.
Входные данные В первой строке входного файла вводится одно натуральное число N Выходные данные Выведите одно число — наименьшую возможную стоимость прохода по лесенке. Примеры Входные данные 31 3 1Выходные данные 2
Зайчик
Входные данные В единственной строке входного файла INPUT.TXT записаны два натуральных числа K и N (1 ≤ K ≤ N ≤ 300). К - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы. Выходные данные В единственную строку выходного файла OUTPUT.TXT нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей.
Примеры Сдача Проезд в маршрутке стоит N рублей. Каким наименьшим количеством монет (бумажные купюры использовать нельзя!) можно заплатить эту сумму? Входные данные Вводится одно натуральное число N, не превосходящее 10 000. Выходные данные Выведите одно число - минимальное количество монет. Примеры Входные данные 25Выходные данные 3Входные данные 9Выходные данные 3
8. Башня Петя в очередной купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из N столбиков, высота каждого столбика составляет Ai кубиков. Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятия башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен. Петя решил как можно скорее посчитать, какова же неприступность его крепости. Однако вскоре он понял, что недостаточно знать высоту каждого из столбиков. В зависимости от того, как сгруппировать столбики в башни, получится разный результат. Разумеется, Петя выберет то разбиение на башни, при котором неприступность будет максимальна. Петя успешно справился со своей задачей, но теперь Правительство Флатландии решило защитить свой горный курорт. Правительство уже построило крепость из кубиков (просто кубики были побольше). Теперь вы должны помочь Правительству посчитать неприступность этой крепости. Единственная трудность состоит в том, что у Правительства было очень много денег, и поэтому крепость была построена очень длинная. Входные данные В первой строке входного файла содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1 ≤ K ≤ N ≤ 1000). Далее на следующей строке содержатся N целых чисел, обозначающих Ai (1 ≤ Ai ≤ 103). Выходные данные На первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни. Гарантируется, что в оптимальном разбиении неприступность крепости не превосходит 2 × 109. Примеры Входные данные 1 11Выходные данные 11Входные данные 2 11 1000Выходные данные 21 2Входные данные 8 31 2 3 4 1 6 7 8Выходные данные 22 6
Красим забор Васин дедушка построил забор на даче из того, что попалось под руку. Забор представляет собой ряд из N досок ширины 10 см, но, возможно, различной высоты. Теперь Вася хочет покрасить забор таким способом. Он выбирает 5 произвольных подряд идущих досок и красит их в один цвет. Затем он выбирает 5 любых еще не покрашенных идущих подряд досок и красит их в другой цвет. И так продолжает до тех пор, пока может выбрать 5 подряд идущих не покрашенных досок. Требуется определить, какую наибольшую площадь забора он сможет покрасить таким способом. Входные данные В первой строке входного файла вводится одно число N - количество досок. Во второй строке входного файла вводятся N чисел - высоты 1-й, 2-й, ..., N-й досок забора в сантиметрах. Все числа натуральные и не превосходят 100. Выходные данные Выведите одно число: наибольшую покрашенную площадь в квадратных сантиметрах. Примеры Входные данные 61 2 3 4 5 6Выходные данные 200Входные данные 122 4 3 7 8 100 92 1 4 2 34 1Выходные данные 2550Компьютерная игра (платформы) Вы можете вспомнить хоть одного своего знакомого до двадцатилетнего возраста, который в детстве не играл в компьютерные игры? Если да, то может быть вы и сами не знакомы с этим развлечением? Впрочем, трудностей при решении этой задачи это создать не должно. Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться от одного края экрана до другого. При этом при прыжке с одной платформы на соседнюю, у героя уходит|y2–y1| единиц энергии, где y1 и y2 — высоты, на которых расположены эти платформы. Кроме того, у героя есть суперприём, который позволяет перескочить через платформу, но на это затрачивается 3·|y3–y1| единиц энергии. Конечно же, энергию следует расходовать максимально экономно. Предположим, что вам известны координаты всех платформ в порядке от левого края до правого. Сможете ли вы найти, какое минимальное количество энергии потребуется герою, чтобы добраться с первой платформы до последней? Входные данные В первой строке записано количество платформ n (1 ≤ n ≤ 30000). Вторая строка содержит n натуральных чисел, не превосходящих 30000 — высоты, на которых располагаются платформы. Выходные данные Выведите единственное число — минимальное количество энергии, которую должен потратить игрок на преодоление платформ (конечно же в предположении, что cheat-коды использовать нельзя). Примеры Входные данные 2100 1Выходные данные 99Входные данные 31 100 80Выходные данные 11911. Быстро растет бамбук... Скоро начнётся сезон роста бамбука. Скупщики бамбука принимают любое количество бамбука каждый день ровно в полдень. Однако цена бамбука каждый день меняется. Нам удалось узнать, по какой цене скупщики будут принимать бамбук. Кроме того, мы точно знаем, на сколько метров вырастает бамбук за каждые сутки (эта величина тоже меняется). В любой день можно либо срезать весь бамбук целиком и продать его, либо оставить бамбук расти дальше. После срезания бамбук продолжает расти. Требуется определить, какую максимальную прибыль от продажи бамбука можно получить. В полдень нулевого дня (начало сезона роста бамбука) длина бамбука равна 0. Сезон роста бамбука длится ровно N суток. Входные данные В первой строке входного файла находится натуральное число N , 1 ≤ N ≤ 100000 . В каждой из следующих N строк содержатся два целых положительных числа, разделенных пробелом: цена одного метра бамбука в определенный день и на сколько метров вырос бамбук за последние сутки. В ( i + 1) - й строке файла содержатся данные, относящиеся к полудню i – го дня. Выходные данные В единственной строке выходного файла следует выводить одно целое неотрицательное число – наибольшая возможная выручка от продажи бамбука. Гарантируется, что результат не превосходит 2 63 - 1 . Примеры Входные данные 82 74 13 35 52 45 24 71 1Выходные данные 139Лотерея На одном из телеканалов каждую неделю проводится следующая лотерея. В течение недели участники делают свои ставки. Каждая ставка заключается в назывании какого-либо M-значного числа в системе счисления с основанием K (то есть, по сути, каждый участник называет M цифр, каждая из которых лежит в диапазоне от 0 до K−1). Ведущие нули в числах допускаются. В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также M-значное число в K-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере A1 рублей. Те, у кого совпали первые две цифры числа — получают A2 рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают A3 рублей. И так далее. Угадавшие все число полностью получают Am рублей. При этом если игрок угадал t первых цифр, то он получает At рублей, но не получает призы за угадывание t−1, t−2и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего. Напишите программу, которая по известным ставкам, сделанным телезрителями, находит число, которое должна назвать телеведущая, чтобы фирма-организатор розыгрыша выплатила в качестве выигрышей минимальную сумму. Для вашего удобства ставки, сделанные игроками, уже упорядочены по неубыванию. Входные данные В первой строке задаются числа N (количество телезрителей, сделавших свои ставки, 1 Выходные данные В первой строке выведите искомое число (если решений несколько — выведите любое из них), а во второй строке — сумму, которую при назывании телеведущей первого числа придется выплатить в качестве выигрыша. Примеры Входные данные 10 3 21 3 100000000001010100100100100110111Выходные данные 0116Входные данные 1 1 101000Выходные данные 10Игра со спичками-2 На столе лежит кучка из N спичек. Двое играют в такую игру. За один ход разрешается взять из кучки одну, две или три спички, так чтобы оставшееся количество спичек не было простым числом (Например, можно оставить в кучке 1 или 4 спички, но нельзя оставить 2 или 3). Выигрывает тот, кто забирает последнюю спичку. Требуется определить, кто из игроков имеет выигрышную стратегию. Входные данные Вводится одно число N (1<=N<=10000). Выходные данные Выведите число 1, если выигрышную стратегию имеет начинающий игрок, или число 2, если выигрышную стратегию имеет второй игрок. Примеры Входные данные 2Выходные данные 1Входные данные 4Выходные данные 2Треугольник Паскаля Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая содержит на одно число больше, чем предыдущая. Первое и последнее из этих чисел равны 1, а все остальные вычисляются как сумма числа, стоящего в предыдущей строке над ним и числа, стоящего в предыдущей же строке слева от него. Входные данные Вводится одно число N (0<=N<=30). Выходные данные Вывести N строк треугольника Паскаля (числа выводятся через пробел). Примеры Входные данные 5Выходные данные 11 1 1 2 1 1 3 3 1 1 4 6 4 1Давайте хранить массив dp[30][30], в dp[1][1] = 1; Шашку - в дамки На шахматной доске (8x8) стоит одна белая шашка. Сколькими способами она может пройти в дамки? (Белая шашка ходит по диагонали. на одну клетку вверх-вправо или вверх-влево. Шашка проходит в дамки, если попадает на верхнюю горизонталь.) Входные данные Вводятся два числа от 1 до 8: номер номер столбца (считая слева) и строки (считая снизу), где изначально стоит шашка. Выходные данные Вывести одно число - количество путей в дамки. Примеры Входные данные 3 7Выходные данные 2Входные данные 1 8Выходные данные 1Входные данные 3 6Выходные данные |
|
N 
