Ваша программа должна читать данные с клавиатуры и выводить результат на экран в точности в таком формате, как указано в задаче. Каждая задача проверяется на нескольких тестах. Задача считается решенной, если она проходит все тесты. Баллы за частичные решения не начисляются.

Для сдачи решений на проверку терубется зарегестрироваться в тестирующей системе на сайте http://olympiads.ru/moldova

Задача 1. “Фишки”.

Рассмотрим доску размером NxN. Какое наименьшее число фишек нужно поставить на клетки доски для того, чтобы на каждой прямой, проходящей через центр произвольной клетки и параллельной каким-либо сторонам или диагоналям доски, стояла хотя бы одна фишка? (Фишки ставятся в центры клеток).

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

4

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

8

Задача 2. “Слова”.

Студенты и школьники очень любят играть на занятиях в следующую игру, которая называется «Слова». Выбирается слово и из его букв составляются другие осмысленные слова, при этом каждая из букв исходного слова может быть использована не более того количества раз, сколько она в нем встречается. Напишите программу, помогающую играть в эту игру.

В первой строке входных данных записано выбранное для игры слово. Далее следует число K – количество слов в словаре. В последующих K строках задан "словарь" - множество слов, которые мы считаем осмысленными. Их количество не превышает 100. Слово - это последовательность не более чем 255 маленьких латинских букв. Каждое слово записано в отдельной строке. Слова в словаре, как это ни странно, не обязательно располагаются в алфавитном порядке, но не повторяются.

Результатом работы программы должен быть список слов, которые можно получить из исходного слова. Слова должны быть выданы в том же порядке, в котором они встречаются в словаре. Каждое слово должно быть записано в отдельной строке. В файле не должно быть пробелов.

Пример входных данных: soundblaster 10 sound blaster soundblaster master last task sos test bonus done

Пример выходных данных: sound blaster soundblaster last sos bonus done

Задача 3. “Змейка”.

На доске размером NxN расставлено k пронумерованных фишек. Ежик, который собирает эти фишки, выходит из клетки с координатами (1,1) и должен собрать все фишки в порядке возрастания их номеров. Из клетки с координатами (x,y) ежик может переместиться только в одну из четырех соседних, т.е. в одну из клеток с координатами (x+1,y), (x-1,y), (x,y+1) или (x,y-1), конечно с соблюдением условия, что он не должен выходить за границы доски. Требуется определить, какое минимальное количество ходов нужно сделать, чтобы собрать все фишки. Если ежик проходит через клетку, где содержится фишка с большим номером, чем он сейчас должен взять, то ничего не происходит (он просто проходит, а фишка остается стоять).

Вводятся два числа N и k. Затем вводятся k пар координат (x,y) соответствующих фишек, т.е. сначала для первой фишки, затем для второй фишки и т. д.

Ответом должно быть единственное число – минимальное количество шагов, которое потребуется для сбора всех фишек в порядке возрастания их номеров.

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

4 3

3 3

1 4

2 1

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

11

Задача 4. “Густой лес”

На плоскости во всех точках с целочисленными координатами от 1 до N стоят деревья - всего N² деревьев. Путник находится в точке с координатами (x1,y1), где x1,y1>0 и хоть одна из этих координат больше N (чтобы не оказаться в самом лесу). Требуется определить, видно ли путника из точки с координатами (0,0). Путника не видно, если на прямой, проходящей через точку (0,0) и точку (x1,y1), есть хоть одно дерево.

На вход подается три целых числа – N, x1, y1.

Требуется вывести YES, если путника видно и NO иначе.

Пример входных данных1 5 6 2 Пример выходных данных1 NO

Пример входных данных2 5 7 6 Пример выходных данных2 YES