Страница: << 34 35 36 37 38 39 40 >> Отображать по:
#2964
Попытка к бегству
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Узник пытается бежать из замка, который состоит из N×M квадратных комнат, расположенных в виде прямоугольника NxM. Между любыми двумя соседними комнатами есть дверь, однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в левой верхней комнате и для спасения ему надо попасть в противоположную правую нижнюю комнату. Времени у него немного, всего он может побывать не более, чем в N+M-1 комнате на своем пути, то есть перемещаться он должен только вправо или вниз. Определите количество маршрутов, которые ведут к выходу.

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

Первая строчка входных данных содержит натуральные числа N и M, не превосходящих 1000. Далее идет план замка в виде N строчек из M чисел в каждой. Одно число соответствует одной комнате: 1 означает, что в комнату можно попасть, 0 – что комната закрыта.

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

Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово Impossible, если таких маршрутов не существует.

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

Примеры
Входные данные
3 5
1 1 1 1 1
1 0 1 0 1
1 1 1 1 1
Выходные данные
3
#2965
Максимальная стоимость маршрута
  

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

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

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

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

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

Программа должна вывести единственное число: максимальную возможную стоимость маршрута черепашки.
Ввод Вывод 
3 4
1 1 2 1
2 2 1 1
2 1 2 1
 
9

#2966
Вывести маршрут максимальной стоимости
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

Примеры
Входные данные
5 5
9 9 9 9 9
3 0 0 0 0
9 9 9 9 9
6 6 6 6 8
9 9 9 9 9
Выходные данные
74
D D R R R R D D
#2968
Калькулятор с восстановлением ответа
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Имеется калькулятор, который выполняет три операции:

  1. Прибавить к числу X единицу.
  2. Умножить число X на 2.
  3. Умножить число X на 3.

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

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

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

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

Выведите строку, состоящую из цифр "1", "2" или "3", обозначающих одну из трех указанных операций, которая получает из числа 1 число N за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них. 😁

Пример

Ввод Вывод 
1
 

5
 
121
 
562340
 
3333312222122213312
#2970
Равенство
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Андрей Сергеевич — учитель математики в начальной школе. Вчера на уроке он записал на доске выражение вида

a1 ? a2 ? ... ? aN - 1 ? aN = S

и попросил детей заменить вопросительные знаки на знаки сложения и умножения так, чтобы получилось верное равенство. Разумеется, дети быстро справились с заданием. Особенно понравилось Андрею Сергеевичу то, что мальчик Петя нашел сразу два варианта расстановки знаков. Тогда он попросил класс посчитать, сколько всего существует вариантов правильной расстановки знаков. Напишите программу, которая решает данную задачу.

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

В первой строке содержится число N (1 ≤ N ≤ 30) — количество чисел в левой части равенства, записанного на доске и число S, записанное в правой части равенства (1 ≤ S ≤ 106). В следующей строке даны N целых чисел в том порядке, в каком они были выписаны на доске. Все числа неотрицательные и не превышают 106.

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

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

Примеры
Входные данные
2 4
2 2
Выходные данные
2
Входные данные
2 46
4 6
Выходные данные
0
Входные данные
4 8
2 2 2 2
Выходные данные
5
Страница: << 34 35 36 37 38 39 40 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест