Меню сайта

Категории раздела
Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) [36]
Решение олимпиадных задач по программированию
Готовимся к олимпиаде по математике [3]
Решение олимпиадных задач по математике

Мини-чат

Наш опрос
Уважаемый посетитель сайта, к какой категории вы себя относите?
Всего ответов: 5501

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

Сайт в каталогах


Сайт    Банк Интернет-портфолио учителейКаталог сайтов Каталог сайтов 'Российское образование в сети' Справочник сайтов учителей и для учителя Учительский портал Сеть творческих учителей Личный сайт Фоновой Натальи Леонидовны учителя математики и информатики

Погода в Вязниках


Главная

Регистрация

Вход
Вы вошли как Гость | Группа "Гости" | RSS


Личный сайт учителя математики и информатики

Фоновой Натальи Леонидовны



Вторник, 18.06.2019, 12:38
Главная » Файлы » Внеурочная деятельность » Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru)

Сапер
14.02.2012, 08:28

Условие:
На прямоугольном поле размером 2 на N (N<=10000) в нижней строке случайным образом расставлено некоторое количество мин, не видимых саперу, а в верхней строке в каждой клетке написаны числа от 0 до 3, которые совпадают с количеством мин в полях нижней строки, соседних с этой клеткой (расположены слева, под ней и справа). Требуется написать программу, которая находит все возможные расположения мин.

Технические условия:
Ограничение по времени тестирования: по 1 секунде на один тест.

Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке число N, а во второй - числа из верхней строки, записанные через пробел.

Формат выходных данных:
В первую строку выходного файла OUTPUT.TXT вывести количество возможных расположений мин (0, если такое невозможно). В следующих строках записать по одному найденному расположению мин (1 – есть мина, 0 – нет, числа разделить одним пробелом).

Примеры входных и выходных файлов:
Input.txt
2
2 2

Output.txt
1
1 1

Решение:
---------- cut ----------
Задача является одномерным аналогом игры, входящей в стандартную поставку Windows.

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

- найденные значения удовлетворяют всем равенствам,
- получено недопустимое значение.

Тогда в первом случае найдена расстановка мин, а во втором получили, что такой расстановки мин не существует. Проделав тоже самое в предположении, что в левом поле нет мины, мы либо найдем еще одну расстановку мин, либо определим, что таковой не существует.

В итоге получаем, что в задаче может:

- не быть решения,

- имеется одно решение,

- имеется два решения.

Изложенный алгоритм и используется в программе:
---------- cut ----------

var
f, g : text;
a, b : array[1..10000] of integer;
n, i, a0, b0, c0, a1, b1, c1, c : integer;
t0, t1 : boolean;
begin
assign(f,'input.txt'); reset(f);
readln(f,n);
t0:=true; t1:=true;
a0:=0; b0:=0; a[1]:=b0;
a1:=0; b1:=1; b[1]:=b1;
i:=1;
while (i<n) and (t0 or t1) do
begin
i:=i+1;
read(f,c);
c0:=c-a0-b0; a[i]:=c0; a0:=b0; b0:=c0;
t0:=t0 and ((c0=0) or (c0=1));
c1:=c-a1-b1; b[i]:=c1; a1:=b1; b1:=c1;
t1:=t1 and ((c1=0) or (c1=1))
end;
read(f,c);
assign(g,'output.txt'); rewrite(g);
t0:=t0 and (a0+b0=c);
t1:=t1 and (a1+b1=c);
if t0 and t1 then write(g,2)
else
if t0 or t1 then write(g,1)
else write(g,0);
if t0 then
begin
writeln(g);
for i:=1 to n-1 do write(g,a[i],' '); write(g,a[n])
end;
if t1 then
begin
writeln(g);
for i:=1 to n-1 do write(g,b[i],' '); write(g,b[n])
end;
close(g)
end.
Категория: Готовимся к олимпиаде по программированию (задачи взяты с сайта http://olimpiada.com.ru) | Добавил: admin
Просмотров: 772 | Загрузок: 0 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Форма входа

Поиск

Кнопка сайта

Одна кнопка

время жизни сайта

Сайт участвует
конкурс сайтов 

Новости образовани

Фраза дня

Web-мастеру

OperaFirefoxGoogle ChromeDownload Master
QIPSkypeµTorrentTeamViewer
Dr.Web CureITAvira AntiVirTotal CommanderCDBurnerXP
PicasaIrfanViewCheMaxDAEMON Tools
AIMPKMPlayerBSplayerK-Lite Codec Pack

Установить себе такой Блок
Скрипты и HTML для uCOz

Раскрутка сайта
Graffiti Decorations(R) Studio (TM) Site Promoter

Copyright MyCorp © 2019
/td>