Страница: << 48 49 50 51 52 53 54 >> Отображать по:
#1345
Пути
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Прямоугольное поле состоит из N строк и M столбцов. Игровая фишка за один ход может переместиться с клетки одного столбца на одну из клеток следующего столбца. Для каждой клетки поля известны номера строк клеток следующего столбца на которые фишка может сделать ход. Фишка не может пойти на клетку, которую она уже посещала раньше.

В начале игры фишку устанавливают на произвольную клетку первого столбца. После этого фишка начинает двигаться в сторону последнего столбца. Когда фишка достигает последнего столбца, ее снова устанавливают на любую клетку первого столбца, которая не была посещена раньше, и возобновляют ее движение.

Игра завершается когда фишка не может сделать ход.

Напишите программу, которая по числам N, M (1≤N≤50, 2≤M≤10), и таблице переходов между клетками определяет какое наибольшее количество раз можно провести фишку от первого до последнего столбца игрового поля.

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

В первой строке входного файла находятся числа N иM. Далее следует M-1 блок по N строк в каждом — описание возможных переходов для каждой клетки поля. Каждая i–ая строка j–го блока описывает возможные переходы из клетки в i–ой строке и j–ом столбце игрового поля. Первое число в строке задает количество возможных переходов из клетки, после чего следуют номера строк следующего столбца по возрастанию и без повторений.

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

В единственной строке выходного файла должно находиться целое число, которое соответствует искомому количеству путей. (Ответ может быть 0, если ни из одной клетки первого столбца нельзя достичь ни одной клетки последнего). Для приведенного примера входных данных фишку можно провести 3 раза, например, по таким маршрутам: (133), (244) и (422).

Примеры
Входные данные
4 3
2 1 3
3 1 2 4
0
2 2 3
1 2 
1 2
1 3
2 2 4
Выходные данные
3
#1346
ВТО
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Территория Великой Треугольной Области (ВТО) представляет собой прямоугольный треугольник. Длины его катетов равны M и N государственных единиц длины (ГЕД). Правительство ВТО решило покрыть как можно большую часть территории области квадратными плитами размером 11 ГЕД. Плиты должны плотно прилегать друг к другу и к катетам ВТО. Разрезать плиты нельзя.

Согласно межгосударственным соглашениям, правительство ВТО не имеет права покрыть частью своей плиты чужую территорию. Производитель поставляет плиты только контейнерными партиями — по P плит. Правительство заказывает столько контейнеров, сколько необходимо для реализации проекта.

Заведующий центральным складом, узнав про проект, решил, что его интересует коли­чество плит, которые останутся на складе из последнего контейнера после покрытия территории ВТО.

Напишите программу, которая по длинам катетов ВТО и вместимости контейнера находит количество плит, которые останутся на складе после осуществления проекта.

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

Единственная строка входного файла содержит три целых числа: M, N (2≤M, N≤2 000 000 000) и P (100≤P≤10 000).

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

Единственная строка выходного файла должна содержать целое число — количество неиспользованных плит из последнего контейнера.

Примеры
Входные данные
4 3 100
Выходные данные
97
#1347
Вишня
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Маленький, но гордый мышонок решил съесть все ягоды с дерева вишни. Вишня — это обычное дерево, ветки которого разветвляются и не срастаются снова. Из точки, где заканчивается ветка, могут начинаться другие ветки или может расти некоторое количество ягод.

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

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

Движение всегда начинается и заканчивается в начале ветки с номером 1, которая соответствует стволу.

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

В первой строке входного файла содержится целое числоN (1≤N≤100) — количество веток в дереве. Дальше идут N строк, которые описывают дерево. Каждая (i+1)-ая строка файла задает информацию про i-ую вершину. Первым в строке идет целое число L (1≤L≤30 000), которое задает длину ветки. Вторым — количество веток K, которые начинаются с конца i-ой ветки. Далее следует K чисел — номера этих веток. Если число K для ветки равно нулю, то третье число задает количество ягод V (0≤V≤30 000), которые растут на конце ветки.

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

В единственной строке файла должно находится целое число — минимальное количество единиц ПВ, которое должен иметь мышонок, для восхождения на дерево, съедания всех ягод и возвращения на землю.

Примеры
Входные данные
8
5 3 6 5 7
5 0 10
9 0 1
4 0 19
11 0 50
5 2 2 4
3 2 8 3
4 0 0
Выходные данные
15
#1348
Алхимия
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Первая строка входного файла содержит четыре целых числа: K (3≤K≤250) — количество веществ, N (3≤N≤500) — количество реакций, M (1≤M<K) — количество имеющихся сначала веществ, а также номер целевого вещества.

Далее следуют N блоков, которые описывают реакции. Каждый блок состоит из трех строк: первая содержит натуральное число — время, необходимое для проведения реакции, вторая строка — количество веществ, которые вступают в реакцию, и перечень этих веществ, третья строка — количество веществ, которые образовываются в результате реакции, и их перечень.

Вещества, имеющиеся сначала, имеют номера от 1 до M, а все остальные — от M+1 до K. Сумма времен проведения всех реакций не превышает 2∙109.

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

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

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

Для приведенного примера входных данных, целевое вещество 4 можно получить, если на протяжении первых трех единиц времени провести реакцию 2, а после этого на протяжении двух единиц времени провести реакцию 3. Таким образом, за 5 единиц времени будет получено требуемое вещество.

Примеры
Входные данные
4 3 1 4
8
1 1
1 4
3
1 1
2 2 3
2
2 1 3
1 4
Выходные данные
5
#1355
Векторы
  

На плоскости задано множество точек (x, y), где x, y – целые числа, 1≤x≤M, 1≤y≤N. Из каждой точки выходит ровно один из следующих векторов: (-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1). Каждый вектор соединяет одну целочисленную точку плоскости с другой. Например, если из точке (2, 5) выходит вектор (1, 1), то он соединяет эту точку с (3, 6), но не наоборот.

Последовательность из двух и более точек плоскости a1, a2,…, ak назовем циклом, если каждая точка ai соединена вектором с ai+1 (1≤i≤k-1), и ak соединена вектором с a1. Циклы считаются разными если они отличаются хотя бы одной вершиной.

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

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

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

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

Единственная строка выходного файла должна содержать целое число – количество циклов, образованных векторами.

Примеры
Входные данные
2 4 
-1 1 -1 1 -1 0 0 1
1 0 1 0 0 -1 0 -1
Выходные данные
2
Страница: << 48 49 50 51 52 53 54 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест