|
Міністерство освіти і науки України
Управлління освіти Вінницької облдержадміністрації
Вінницький обласний інститут післядипломної освіти педагогічних працівників
Управління освіти Вінницької міської ради
Вінницький регіональний бізнес-центр
Вінницьке обласне відділення фонду НАН України "Інтелект України"
Фізико-математична гімназія №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.
Программа не должна ничего выводить на экран и не должна ждать ввода с клавиатуры!
Решения проверяются автоматически на наборе тестов. В текст программ изменения не вносятся и сам он не оценивается.
|
