Задача 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   Ограничение времени: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

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

Автор:А. Кленин
Входной файл: 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

Задача D. Кратные тройки ≡

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

Условие

Дана последовательность различных целых чисел A1, A2, …, AN. Требуется подсчитать количество таких троек (Ai, Aj, Ak), что i ≠ j, i ≠ k, j < k и Ai нацело делится как на Aj, так и на Ak. Например, в последовательности 1 3 2 4 6 таких троек четыре: 6 3 2, 6 1 3, 6 1 2, 4 1 2.

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

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

Входной файл содержит число N, за которым следуют N чисел A1 A2… AN.

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

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

Ограничения

3 ≤ N ≤ 1000, 1 ≤ Ai ≤ 109

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3
1 2 3
 
0
2 
4 2 4 8 16
 
4
0.046s 0.005s 13