Задача A. Кратная подпоследовательность ≡

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

Условие

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

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

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

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

Выходной файл должен содержать не более N чисел, разделенных пробелами. Числа должны появляться в выходном файле в том же порядке, что и во входном. Если искомого подмножества не существует, в выходном файле должно содержаться число 0 (нуль).

Ограничения

1 ≤ N ≤ 1000.

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
5
1 3 9 33 11
 
1 9

Задача B. 0 - a, 1 - ab ≡

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

Условие

Дана строка s, состоящая из N символов 0 или 1, а также строка t, состоящая из M символов a или b,

Над строкой s разрешено производить следующие действия:

Требуется определить, можно ли преобразовать строку s в строку t при помощи указанных действий.

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

Первая строка входного файла содержит числа N M.

Вторая строка входного файла содержит строку s.

Третья строка входного файла содержит строку t.

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

Выходной файл должен содержать единственный символ Y или N.

Ограничения

1 ≤ N, M ≤ 10000

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3 3
101
bab
 
Y
2 
4 3
1001
bab
 
N

Задача C. Триангуляция пирога ≡

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

Условие

Праздничный пирог имеет форму неправильного выпуклого многоугольника с N вершинами. Хозяйка хочет порезать его на N − 2 кусков. Причем ее высокие эстетические идеалы требуют, чтобы куски имели форму треугольников. Разрезы же должны проходить через вершины изначального многоугольника и не пересекаться.

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

Напишите программу, которая решает эту задачу.

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

Первая строка входного файла содержит число N — количество вершин многоугольника.

Вторая строка содержит N пар разделенных пробелами целых чисел xi yi — координаты вершин многоугольника в порядке обхода по часовой стрелке.

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

В выходной файл выведите минимальную суммарную длину разрезов с точностью до четырех знаков после запятой.

Ограничения

3 ≤ N ≤ 100

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
6
0 0 1 1 2 1 3 0 2 -1 1 -1
 
6.2361
0.026s 0.005s 11