Задача A. Дайте мне справку, что вам нужна справка... ≡

Автор:А. Кленин
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб
Максимальный балл:50  

Условие

Администрация одного города состоит из N чиновников, выдающих справки. Для выдачи справок некоторые из чиновников могут потребовать справок от других чиновников, а те, в свою очередь, от третьих и т.д.

Требуется написать программу, выдающую способ получения справки от M-го чиновника, требующий минимального общего количества справок.

Рекомендуется рассмотреть частичные решения для следующих случаев

Формат входного файла

Входной файл содержит числа N M, за которыми следует последовательность из N описаний чиновников. Описание i-го чиновника состоит из числа Ri — количества требуемых чиновником справок, за которым следуют Ri чисел si,1 si,2… si,Ri — номера чиновников, со справками от которых нужно являться к i-му чиновнику.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100, 0 ≤ Ri < N, si, j ≠ i

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1 1
0
 
1 1
2 
2 1
1 2
1 1
 
0
3 
2 1
1 2
0
 
2 2 1

Задача B. Контрпример ≡

Автор:А. Кленин
Входной файл: input.txt   Ограничение времени:1 сек
Выходной файл: output.txt   Ограничение памяти:4 Мб
Максимальный балл:60  

Условие

Учитель математики провёл урок на тему "неравенства". По окончании урока ученики написали контрольные работы, в которых требовалось преобразовать неравенства. Каждый школьник сдал работу, состоящую из двух неравенств, которые, по его мнению, эквивалентны между собой.

Проверяя эти работы, учитель обнаружил, что все они содержат ошибки. Чтобы пояснить ученикам суть ошибок, учитель желает привести к каждой паре неравенств контрпример — значение переменной, при котором одно из неравенств выполняется, а второе — нет. Для большей наглядности учитель решил, что значения должны быть целыми числами.

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

Неравенство представляет из себя строку, из двух выражений, разделённых одним из знаков '<', '>', '<=', '>='. Каждое выражение состоит из цифр, переменной 'x', а также знаков '+' и '-'. Знак умножения подразумевается между коэффициентом и переменной, записанными подряд. Примеры выражений: x+3, -5x, x+2-4x.

Рекомендуется рассмотреть частичные решения для следующих случаев

Формат входного файла

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

Формат выходного файла

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

Ограничения

Длина каждого неравенства не превосходит 100 символов. Коэффициенты — целые числа, не превосходящие 10^9. Символом после переменной не может быть цифра или переменная (т.е. выражения вида '5xx', '3x3' не могут встретиться во входных данных).

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
x>=-5
5>-x
 
-5
2 
17&lt;x
42&lt;2x
 
19

Задача C. Прямоугольник и отрезок ≡

Автор:А. Кленин
Входной файл: input.txt   Ограничение времени:2 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб
Максимальный балл:40  

Условие

Прямоугольник со сторонами, параллельными осям координат, задан координатами двух противоположных вершин (x1, y1) и (x2, y2). Отрезок задан координатами вершин (u1, v1) и (u2, v2). Требуется вычислить длину части отрезка, лежащей внутри прямоугольника или на его границе.

Рекомендуется рассмотреть частичные решения для следующих случаев

Формат входного файла

Входной файл содержит вещественные числа x1 y1 x2 y2 u1 v1 u2 v2.

Формат выходного файла

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

Ограничения

1 ≤ xi, yi, ui, vi ≤ 106

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
100 10 160 60 90 30 180 30
 
60.0
2 
10 10 20 20 10.5 11 13.5 15
 
5.0

Задача D. Океанариум ≡

Автор:А. Кленин, Е. Иванова
Входной файл: input.txt   Ограничение времени:2 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб
Максимальный балл:50  

Условие

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

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

Например, если в первый раз Петя увидел трёх гуппи и одного вуалехвоста, а во второй раз — четырёх вуалехвостов, то всего в аквариуме не менее 7 рыбок.

Рекомендуется рассмотреть частичные решения

Формат входного файла

Первая строка входного файла содержит число N. Далее следует последовательность из N описаний листков. В первой строке каждого описания содержится число рыбок Ki, в последующих Ki строках — названия рыбок.

Формат выходного файла

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

Ограничения

1 ≤ N, Ki ≤ 50, длина названий не превосходит 255 символов.

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1
2
Carassius auratus
Poecilia reticulata
 
2
2 
3
5
Lionhead
Pompom
Pearlscale
Pearlscale
Lionhead
2
Pompom
Pompom
5
Lionhead
Lionhead
Ryukin
Pearlscale
Lionhead

8
0.051s 0.005s 13