Міністерство освіти і науки України
Управлління освіти Вінницької облдержадміністрації
Вінницький обласний інститут післядипломної освіти педагогічних працівників
Управління освіти Вінницької міської ради
Вінницький регіональний бізнес-центр
Вінницьке обласне відділення фонду НАН України "Інтелект України"
Фізико-математична гімназія №17 м.Вінниці

IX  міжрегіональна олімпіада з математики, фізики та інформатики

Завдання з інформатики

Шпионские игры

Задача ТАЙНИК (HIDING).

В страшной тайне и полной темноте Шпион устанавливает ужасную бомбу с часовым механизмом в прямоугольную выемку размером Nx3 . Чтобы скрыть следы, надо замуровать отверстие кирпичами размером 1x2 . Планируя операцию, Шпион перебрал все варианты укладки. Сколько вариантов укладки он нашел?

Напишите программу HIDING, которая читает число N  из файла HIDING.DAT и записывает число вариантов укладки в файл HIDING.SOL.

Ограничения:
1<N<1000

Пример:

HIDING.DAT:
4

HIDING.SOL:
11

Задача МИННОЕ ПОЛЕ (MINES).

Холодным, дождливым, осенним вечером уходя от погони, Шпион переходит минное поле. К счастью, у него есть карта, где отмечены мины. Эта карта нарисована на листке бумаги в клетку, вырванном из школьной тетради любимого сыночка Шпиона. Каждая клетка изображает квадратный метр поля, клетки с минами помечены красным крестиком.     Чтобы запутать следы, Шпион передвигается прыжками: на два метра вперед и метр в сторону, или на метр вперед и два в сторону (как шахматный конь, только назад двигаться нельзя, см. рисунок).     Сколько существует путей через минное поле, которые начинаются с самого верхнего ряда клеток и заканчиваются на самом нижнем.     Напишите программу MINES, которая читает карту из файла MINES.DAT и записывает число путей в файл MINES.SOL.

 Формат файла MINES.DAT:

 M  и N  – число строк и столбцов в карте. Pij=1 , если в клетке нет мины, и Pij=0  , если она заминирована.

 Ограничения:

1<M<=15 , 1<N<=15 .

П ример:

MINES.DAT:

5 4
1 1 1 1
0 1 0 1
1 0 1 0
1 0 1 0
1 1 0 1

MINES.SOL:

8

 Задача ЕДИНИЦЫ (UNITS).

После неудачно проведенной операции Шпион коротает время в тюрьме, решая задачу из популярного журнала. Ему нужно представить число N  используя только число 1 , операции сложения и умножения и скобки. При этом единиц должно быть как можно меньше. Например, 10=1+(1+1+1)x(1+1+1) . Помогите Шпиону-неудачнику определить, сколько единиц нужно для представления числа N .
    Напишите программу UNITS, которая читает число N  из файла UNITS.DAT и записывает количество единиц в файл UNITS.SOL.

 Ограничения:

1<=N<=5000 .

 Пример:

UNITS.DAT:
10
 UNITS.SOL:
7

 Памятка участникам.
    Решения задач – файлы с текстами программ, должны быть записаны на диск под именами hiding.pas, mines.pas, units.pas (или *.c, или *.cpp). Программы должны читать из текстовых файлов с расширением dat и записывать разультаты в файлы с расширением sol.
    Программа не должна ничего выводить на экран и не должна ждать ввода с клавиатуры!
    Решения проверяются автоматически на наборе тестов. В текст программ изменения не вносятся и сам он не оценивается.