Задания первого тура

Задача 1. Многоугольники

Требуется проверить, образует ли заданный упорядоченный набор из N плоских выпуклых многоугольников последовательность вложенных друг в друга фигур (каждая последующая фигура лежит внутри предыдущих). Многоугольники задаются координатами вершин (x^k_i,y^k_i), i=1,2,…,Mk, где M_k (3<=M_k<=10) – число вершин k-ого многоугольника (k=1,2,…N).

Входные данные
Входной текстовый файл input.txt состоит из N (2<=N<=100) строк. В k-ой строке содержится описание k-ого многоугольника, представляющее собой последовательность пар целых чисел x^k_i и y^k_i, (–100000<=x^k_i,y^k_i<=100000), задающих координаты вершин.

Выходные данные
В выходной текстовый файл output.txt следует поместить слово “Yes”, если свойство вложенности выполнено. В противном случае, необходимо вывести порядковый номер первого многоугольника, нарушившего данное свойство.

Примеры входных и выходных данных

input.txt			output.txt
0  0  10  0  0  10		Yes
1  1  2  2  1  2  2  1
		
0  0  10  0  0  10		Yes
0  0  2  0  4  5
0  0  1  0   2  2

0  0  10  0  0  10		2
0  0  2  0  4  -5
0  0  1  0   2  2

0  0  10  0 0  10  10  10  -1  5  5  11  11  5  5  -1	Yes
1  1  9  9  1  9
2  6  2  7  9  9  3  6

Задача 2. Дерево

Дано дерево, вершины которого пронумерованы от 1 до N. Требуется определить, принадлежит ли вершина с номером C кратчайшему пути, соединяющему вершины A и B. Ограничение времени: 5.0 сек. Ограничение памяти: 32 Мб.

Входные данные
В первой строке файла input.txt находится число N – количество вершин дерева (1≤N≤100000). Далее идут N-1 строк, описывающих рёбра дерева, в каждой из которых записаны числа Xi, Yi (1≤Xi≠Yi≤N). В следующей строке находится число M – количество тестов (0≤M≤5000). В следующих M строках находятся тройки чисел Ai, Bi, Ci (1≤Ai, Bi, Ci≤N) – номера проверяемых вершин дерева.

Выходные данные
В выходном файле output.txt должны содержаться M строк с ответами “Yes” (без кавычек), если Ci принадлежит пути, соединяющему Ai и Bi, или “No” (без кавычек) в противном случае.

Пример входных и выходных данных

		input.txt	output.txt
		6		Yes
		1 3		Yes
		5 3		No
		1 2
		3 4
		3 6
		3
		1 5 5
		2 6 3
		2 6 4

Задача 3. Палиндром

Палиндромом считается число, которое пишется одинаково как слева направо, так и справа налево. Минимальное число-палиндром, которое делится без остатка на 12, равно 252. А какое число соответствует, например 67 или 711? Ваша программа должна за секунду выводить правильный ответ, если в нём не более 30 цифр. Ограничение времени: 1.0 сек. Ограничение памяти: 16 Мб

Входные данные
В единственной строке файла input.txt находится целое число A (1≤A≤10000).

Выходные данные
В единственной строке файла output.txt должно находиться натуральное число -палиндром без ведущих нулей - состоящее не более, чем из 30 цифр, и делящееся на A. Если такого числа не существует, то вывести «No solution» (без кавычек).

Пример входных и выходных данных

		input.txt	output.txt
		11		11
		12		252

Вход для участников