Вывести маршрут максимальной стоимости

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

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

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

В первой строке входных данных записаны два натуральных числа N и M, не превосходящих 100 — размеры таблицы. Далее идет N строк, каждая из которых содержит M чисел, разделенных пробелами — описание таблицы. Все числа в клетках таблицы целые и могут принимать значения от 0 до 100.

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

Первая строка выходных данных содержит максимальную возможную сумму, вторая – маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

Примеры

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

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

17. K-ичные числа

Требуется вычислить количество N-значных чисел в системе счисления с основанием K, таких что их запись не содержит двух подряд идущих нулей.
Ограничения: 2 <= K <= 10, N + K <= 18.
Формат входных данных
Числа N и K в десятичной записи, разделенные пробелом или переводом строки.
Формат выходных данных
Искомое число в десятичной записи.

Путь через горы

Поверхность Земли в горной местности можно представить в виде ломаной линии. Вершины ломаной расположены в точках (x₁, y₁), (x₂, y₂),…,(x_N, y_N), при этом x_i<x_i+1.

Обычный горный маг находится в точке (x₁, y₁) и хочет попасть в точку (x_N, y_N). При этом он может перемещаться только пешком. Он может ходить по поверхности Земли (т.е. вдоль ломаной). А может сотворить в воздухе мост и пройти по нему. Мост может соединять две вершины ломаной: мост не может начинаться и заканчиваться не в вершине ломаной, и мост не может проходить под землей (в том числе не может быть туннелем в горе), но мост может каким-то своим участком проходить по поверхности земли. Длина моста не может быть больше R. Суммарно маг может построить не более K мостов.

Какое наименьшее расстояние придется пройти магу, чтобы оказаться в точке (x_N, y_N).

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

Вводится сначала натуральное число N (2≤N≤100). Затем водится натуральное число K (1≤K≤100) — максимальное количество мостов. Далее вводится целое число R (0≤R≤10000) — максимальная возможная длина моста. Далее вводятся координаты (x₁, y₁), (x₂, y₂),…,(x_N, y_N). Все координаты – целые числа, не превышающие по модулю 10000, для всех i от 1 до N–1: x_i<x_i+1.

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

Выведите одно число — минимальную длину пути, которую придется пройти магу (как по земле, так и по мостам). Ответ выведите не менее чем с 5 цифрами после десятичной точки.

Примеры

Количество треугольников

Рассмотрим фигуру, аналогичную показанной на рисунке (большой равносторонний треугольник, составленный из маленьких равносторонних треугольников). На рисунке приведена фигура, состоящая из 4-х уровней треугольников.

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

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

Вводится одно число N — количество уровней в фигуре (1 N 100000).

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

Выведите количество треугольников в такой фигуре.

Примеры

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

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

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

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

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

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

20. Машинки

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

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

В некоторый момент образовалась пробка. На 1-й дороге скопилось N машин, а на 2-й — M. Для каждой машины известно время, которое ей потребуется для проезда развилки, если она первая в очереди и ее дорога "активна".

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

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

Сначала вводятся числа T, N и M, затем N чисел — времена проезда перекрестка машинами с первой дороги (в порядке удаления от перекрестка), а затем Mчисел — времена проезда перекрестка машинами со второй дороги.

<>Все числа целые неотрицательные, все времена не превосходят 100, T ≤ 100, N, M ≤ 1000, N+M > 0.

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

В первой строке выведите одно число — минимальное среднее время ожидания c точностью 10^–3. Далее выводите информацию о машинах в порядке их проезда перекрестка и о переключении потока следующим образом.

• Для каждой машины выведите информацию в формате:

Car k from road i

где k — номер машины на своей дороге (ближайшая к перекрестку в момент образования пробки машина имеет номер 1, следующая на той же дороге — 2 и т.д.), i — номер дороги: 1 или 2.

• Для каждого переключения потока выведите информацию:

Switch road from 1 to 2

для переключения потока с первой дороги на вторую или

Switch road from 2 to 1

для переключения потока со второй дороги на первую.

Информация обо всех событиях (переключениях и проездах через перекресток) должна выводиться именно в том порядке, в котором они происходят.

Если решений несколько, выведите любое из них.

Оценка задачи

1 балл будет набирать решение, верно работающее при N, M ≤ 10.

Примеры

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

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

Гвоздики

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

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

В первой строке входных данных записано число N — количество гвоздиков (2 N 100). В следующей строке заданы N чисел — координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

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

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

Пример

Примеры

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

3 4 6 12 13 14

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

Маскарад

По случаю введения больших новогодних каникул устраивается великий праздничный бал-маскарад. До праздника остались считанные дни, поэтому срочно нужны костюмы для участников. Для пошивки костюмов требуется L метров ткани. Ткань продается в N магазинах, в которых предоставляются скидки оптовым покупателям. В магазинах можно купить только целое число метров ткани. Реклама магазина номер i гласит: "Мы с радостью продадим Вам метр ткани за P_i бурлей, однако если Вы купите не менее R_i метров, то получите прекрасную скидку - каждый купленный метр обойдется Вам всего в Q_i бурлей". Чтобы воплотить в жизнь лозунг "экономика страны должна быть экономной", правительство решило потратить на закупку ткани для костюмов минимальное количество бурлей из государственной казны. При этом ткани можно купить больше, чем нужно, если так окажется дешевле. Ответственный за покупку ткани позвонил в каждый магазин и узнал, что:

1) реклама каждого магазина содержит правдивую информацию о ценах и скидках;

2) магазин номер i готов продать ему не более F_i метров ткани.

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

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

В первой строке входного файла c.inзаписаны два целых числа N и L (1 £ N £ 100, 0 £ L £ 100). В каждой из последующих N строк находится описание магазина номер i - 4 целых числа P_i, R_i, Q_i, F_i (1£ Q_i £ P_i £ 1000, 1 £ R_i £ 100, 0 £ F_i £ 100).

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

Первая строка выходного файла c.out должна содержать единственное число - минимальное необходимое количество бурлей.

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

Если ткани в магазинах недостаточно для пошивки костюмов, выходной файл должен содержать единственное число -1.

Примеры

Скобки

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

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

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

Пример входного файла
????(?

Пример выходного файла
2

Уравнение

Задано уравнение вида A + B = C, где A, B и C – неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса (?). Примером такого уравнения является ?2+34=4?. Требуется так подставить вместо знаков вопроса цифры, чтобы это равенство стало верным, либо определить, что это невозможно.

Входные данные
Заданное уравнение содержится в первой строке входного файла. Длина уравнения не превышает 80 символов. Входной файл не содержит пробелов.

Выходные данные
В выходной файл требуется вывести верное равенство, полученное из исходного уравнения заменой знаков вопроса цифрами, либо сообщение «решения не существует».

Пример входного файла
??2?4+9?=355

Пример выходного файла
00264+91=355

Красивый номер телефона

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

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

Входные данные
Во входном файле записано целое число N (1 ≤ N ≤ 100).

Выходные данные
Выведите в выходной файл искомое количество телефонных номеров.

Пример входного файла
2

Пример выходного файла
16

Плитки

У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1 * 1. Он выбирает ровно N плиток и выкладывает их в полоску. Например, при N = 10 она может выглядеть следующим образом:

(буквой К обозначена красная плитка, С — синяя, З — зеленая).
После этого Петя заполняет следующую таблицу:

В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает "Y", если в его полоске найдется место, где рядом лежат плитки цветов А и Б и "N" в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали — если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски.
Так, данная таблица представляет собой диаграмму смежности приведенной выше полоски.
Петя хочет узнать, сколько различных полосок имеет определенную диаграмму смежности. Помогите ему.
(Заметьте, что полоски, являющиеся отражением друг друга, но не совпадающие, считаются разными. Так, полоска

не совпадает с полоской, приведенной в начале условия.)

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

Первая строка входного файла содержит число N (1 <= N <= 100). Следующие три строки входного файла, содержащие по три символа из набора {"Y", "N"}, соответствуют трем строкам диаграммы смежности. Других символов, включая пробелы, во входном файле не содержится. Входные данные корректны, т.е. диаграмма смежности симметрична

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

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

Альтернативные пути

Задано прямоугольную таблицу размером M строк на N столбиков. В каждой клеточке записано натуральное число, не превышающее 200. Путник должен пройти по этой таблице из левого верхнего угла в правый нижний, на каждом шаге перемещаясь либо на 1 клеточку направо, либо на 1 клеточку вниз. Очевидно, таких путей много. Для каждого пути можно вычислить сумму чисел в пройденных клеточках. Среди этих сумм, очевидно, есть максимальная.

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

Количество <хороших> путей гарантированно не превышает 10⁹.

Задание

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

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

Первая строка входного файла GOODWAYS.DAT содержит три целых числа M (2≤M≤200), N (2≤N≤200) и K (0≤K≤200). Каждая из последующих M строк содержит N чисел, записанных в соответствующих клеточках.

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

Первая строка выходного файла GOODWAYS.SOL должна содержать максимальную возможную сумму; вторая строка - количество маршрутов, сумма чисел которых отличается от максимальной не более чем на K.