| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Интересные и занимательные задачи по программированию > Областная олимпиада тур 2 задача 3 |
| Автор: Strannik 18.2.2007, 15:35 |
| 3. В подземелье замка короля Мондрагона, план которого имеет форму прямоугольника 2*N, хранятся несметные сокровища. Нередкими были попытки злоумышленников пробраться в подземелье и украсть богатства короля, поэтому он решил поставить в подземелье стражу из числа солдат регулярной армии. Надо сказать, что личный состав вооруженных сил королевства имеет отличную военную подготовку, дисциплинирован и стреляет из луков и арбалетов без промаха. Охране дан был строгий приказ - стрелять во все живое, что они смогут увидеть. Конечно же, при этом недопустима такая расстановка стражников, при которой хотя бы один может увидеть другого. Смотреть солдат может в 8 направлениях: влево, вправо, вперед, назад и по диагоналям как угодно далеко, но, конечно же, только до стены - сквозь стены солдаты королевства пока еще не научились видеть. Задание. Напишите программу GUARDS, определяющую количество допустимых расстановок стражи в подземелье. (Заметим, что полное отсутствие стражи в подземелье также является допустимой расстановкой, поскольку при этом нет стражников, которые могли бы увидеть других). Входные данные. В первой строке текстового файла GUABDS.DAT записано количество тестов. Первая строка каждого теста содержит одно целое число - длину подземелья N (1<N<30), а вторая и третья - по N чисел из множества {0,1}, определяющих план подземелья. Значение 0 обозначает свободную клетку, в которую может быть поставлен один стражник, а значение 1 - клетку, занятую стеной (разумеется, замуровывать солдата в стену нельзя) Примечание. В 30% тестов N<=7. Выходные данные. В текстовый файл GUARDS.SOL выведите для каждого теста в отдельной строке количество допустимых расстановок стражи. Пример входных и выходных данных GUARDS.DAT GUARDS.SOL 2 4 3 9 1 1 0 0 1 1 3 0 1 0 0 0 0 |
| Автор: FireSnake 23.2.2007, 18:31 |
| Грузная задача. И кстати не перебор! А динамика. Хороший перебор набирает где-то 50/100 балов |