Темы
Информатика(2656 задач)
--->
61 задач
<---
ограничение по времени на тест
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
ограничение по времени на тест
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
#1356
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Система рейсов авиакомпании OlympAirways была спроектирована таким образом, чтобы из любого аэропорта, который обслуживается авиакомпанией, можно было перелететь в любой другой аэропорт, воспользовавшись, возможно, больше чем одним рейсом. Каждый рейс соединяет два аэропорта, и выполняется в обе стороны.
Существует проблема, что некоторые рейсы определенное время могут не выполняться из-за плохих погодных условий. Таким образом, вероятно, что клиент не сможет перелететь из аэропорта A аэропорт B, пользуясь только самолетами авиакомпании OlympAirways. Для исследования подобных ситуаций научный отдел компании ввел понятие числа уязвимости связи между парой аэропортов A и B. Это число равно количеству рейсов авиакомпании, отмена любого из которых (при условии, что все остальные рейсы выполняются в обычном порядке) приведет к невозможности перелета в аэропорт B из аэропорта A.
Напишите программу, которая по информации обо всех рейсах, выполняемых авиакомпанией, определяет сумму чисел уязвимости связи между всеми парами аэропортов.
Входные данные
Первая строка входного файла содержит целое число N (1≤N≤100) – количество аэропортов, которые обслуживаются авиакомпанией. Вторая строка содержит целое число M (1≤M≤4950) — количество рейсов, выполняемых авиакомпанией. Каждая из последующих M строк задает рейс, который представлен парой целых чисел от 1 до N – номерами аэропортов, которые он соединяет.
Выходные данные
Единственная строка выходного файла должна содержать целое число — суммарное число уязвимости связи между всеми разными парами аэропортов A и B, таких, что номер A меньше номера B.
Примеры
Входные данные
5 5 1 2 4 2 4 5 3 2 3 1
Выходные данные
10
#1357
Наверное, всем известно, что шоколад полезен для мозга человека. Поэтому участники национальной олимпиады страны Олимпия принесли на тур много плиток шоколада, чтобы гениальные идеи приходили к ним быстрее. Однако принесенного шоколада оказалось слишком много, и после тура в кабинете осталось N прямоугольных плиток, которые состояли из долей размерами 1×1. Двое участников решили съесть часть оставшегося шоколада, но, учитывая что во время тура они уже съели достаточно много шоколада, было решено сделать это достаточно необычным игровым способом, по следующим правилам.
Участники выполняют определенные операции с шоколадными плитками по очереди: сначала первый, потом второй, снова первый и т.д. В свою очередь участник выбирает плитку шоколада, с которой он будет выполнять одну из следующих операций:
- Разломить плитку на две; линия разлома должна проходить параллельно сторонам плитки и между долями.
- Отломить и съесть произвольную «строку» или «столбик» плитки, который не есть крайним.
- Отломить и съесть все доли плитки, которые находятся с краю, но чтобы после этого от плитки осталась хотя бы одна доля (минимальный размер плитки, c которой может быть произведена такая операция – 3×3)
Никакая из этих операций не может быть произведена с плиткой 1×1, поэтому все такие плитки остаются до конца игры. Проигрывает тот участник, который в свою очередь не может произвести ни одной из приведенных операций.
Напишите программу, которая по информации о плитках шоколада, оставшихся после тура, определяет количество вариантов первого хода первого участника, гарантирующих ему выигрыш, при следовании выигрышной стратегии в дальнейшем.
Входные данные
В первой строке входного файла содержится целое число N (1≤N≤100) – количество шоколадных плиток. Во второй строке содержатся N пар целых чисел, каждая i-ая из которых задает длину и ширину i-ой плитки. Длина и ширина не меньше чем 1 и не превышают 100.
Выходные данные
В единственной строке выходного файла должно находиться целое число – количество вариантов первого хода первого участника, которые гарантируют ему выигрыш, при следовании оптимальной стратегии в дальнейшем.
Комментарий к примеру тестов
Выигрышные ходы первого участника следующие: операция (3), операция (2) со второй строкой, и операция (2) со вторым столбиком.
Примеры
Входные данные
1 3 3
Выходные данные
3
Выбрано
:
|