Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадные задачи с решениями на Turbo Pascal

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 3.826 RSS
←   Сентябрь 2002   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Открыта: 02-12-2001

Автор
Aslof

Статистика

3.826 подписчиков
0 за неделю
←   Все выпуски   →

Олимпиадные задачи с решениями на Turbo Pascal


Информационный Канал Subscribe.Ru

Олимпиадные задачи с решениями на Turbo Pascal #32

Подписчиков на 2002-09-10 - 4336 человек(а).
Главная Архив задач Конкурс Рассылки Форум Гостевая книга Контакты

Здравствуйте, уважаемые подписчики!

  Маленькое объявление в начале рассылки. На сервере http://homepages.compuserve.de/chasluebeck (Германия) проводится открытая олимпиада по информатике(на русском языке). Там же вы найдете довольно большой архив олимпиадных задач и других материалов по данной теме. 

ЗАДАЧИ

Сапер - 3 уровень

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

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

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

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

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

Confuse.dat

Confuse.sol
2
2 2		 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 (n>i) 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.

ТЕОРИЯ

  Данный раздел временно прерывает свою работу по ряду причин, основная из основных - это, конечно же, отстутствие времени. Однако, по мере накопления новых материалов я буду стараться выкладывать их здесь.
Реклама в рассылке:

RLE    

  

Подпишитесь на наши рассылки:

Новости проекта "Олимпиада.com.ru" [Алексей Шамис]
Новости проекта "Olimpiada.com.ru". Новые темы на форуме. Информация о пополнениях в архиве задач. Оперативно и своевременно!

Уроки программирования на Turbo Pascal [Галин Павел]
Хотите стать Великим Программистом? Начните свой путь к вершине славы с изучения языка Turbo Pascal. Он как нельзя лучше подходит для начинающих программистов и в то же время используется для разработки сложных "профессиональных" программ.

 Олимпиадные задачи с решениями на Turbo Pascal [Шамис Алексей]
В рассылке публикуются решения интересных олимпиадных задач различного уровня. Содержит много теоретической информации. Периодичность - 2-3 раза в неделю.

 Задача в неделю. Олимпиадные задачи по информатике [Алексеев Александр]
Каждый понедельник в рассылке публикуется задача, которую необходимо решить и в следующий понедельник прислать программу на тестирование. Решения проверяются, и в пятницу публикуется разбор и итоги тестирования.

Всегда рады видеть Вас на нашем сайте. Жду ваших предложений и замечаний, Алексей Шамис

Copyright © 2001-2002 by Shamis Alex.

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное