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

Информат - алгоритмическое и математическое мышление

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "физика YES" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

  Январь 2003   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
20.01.2003
12:11:41
15:51:33
21
22
23
24
25
26
27
28
29
30
31
Автор
ss77_ss77@mail.ru

Статистика

1.523 подписчиков
+1 за неделю
←   Все выпуски   →

Конкурсы и Олимпиады по Машинному программированию (КОМП)


Информационный Канал Subscribe.Ru 
       Участникам студенческого конкурса МАРК и
              всем заинтересованным лицам.


Туманный лабиринт

Задан  лабиринт  10x10  в  каждой  клетке  стена  может находиться или
отсутствовать.  Клетки  нумеруются слева направо и сверху вниз числами
от  0  до  99 (рис.1). Вокруг лабиринта - сплошная стена. Программа за
один  вопрос  может узнать, что находится в клетке с заданным номером.
Из  одной  клетки  можно  переходить  в  другую,  если они имеют общую
сторону и ни в одной из них нет стены.

Рисунок 1.

  0  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 31 32 33 34 35 36 37 38 39
 40 41 42 43 44 45 46 47 48 49
 50 51 52 53 54 55 56 57 58 59
 60 61 62 63 64 65 66 67 68 69
 70 71 72 73 74 75 76 77 78 79
 80 81 82 83 84 85 86 87 88 89
 90 91 92 93 94 95 96 97 98 99

Требуется,  задав не более 100 вопросов узнать, как пройти из клетки 0
в клетку 99, переходя от одной клетки к другой.

ТЕХНИЧЕСКОЕ ЗАДАНИЕ
Программа  во время своей работы должна сделать ход не более чем за 10
секунд.  При  каждом  запуске программа может читать файлы: maze.txt и
temp.tmp.  maze.txt  хранит текущий путь до какой-то клетки лабиринта.
Начало  этого  пути  всегда  в  клетке  с номером 0. В пути все клетки
должны быть соседними и все, кроме, может быть, последней, должны быть
пустыми.  Номера  клеток  разделены  пробельными  символами  (пробелы,
табуляции,  переводы  строк). Перед запуском программы будет проверена
последняя клетка пути в maze.txt и если там стена, она будет убрана из
maze.txt,   иначе   maze.txt  не  изменится.  После  окончания  работы
программы  в maze.txt должен находится путь, последняя клетка которого
будет  проверена  перед очередным запуском Вашей программы. Если номер
последней клетки в пути окажется равен 99, то будет проверен весь путь
и если он окажется верным, то задача считается решённой.

Программа  может иметь только один временный файл temp.tmp размером не
более 10 байт.

ЦЕЛЬ
Найти путь за минимальное количество запусков Вашей программы.

ПРИМЕР
  <запуск проверки пути>
  В maze.txt: 0
  <запуск программы участника>
  В maze.txt: 0 1 2 3 4 5 6 7 8 9
  <запуск проверки пути>
  В maze.txt: 0 1 2 3 4 5 6 7 8
  <запуск программы участника>
  В maze.txt: 0 1 2 3 4 5 6 7 8 18 19 29 39 49 59 69 79
  <запуск проверки пути>
  В maze.txt: 0 1 2 3 4 5 6 7 8 18 19 29 39 49 59 69 79
  <запуск программы участника>
  В maze.txt: 0 1 2 3 4 5 6 7 8 18 19 29 39 49 59 69 79 89 99
  <запуск проверки пути>
  Количество ходов на поиск пути: 3

ЗАДАНИЕ 1
Написать программу для выполнения цели, которая описана выше.

ЗАДАНИЕ 2
Предоставить  файл  maze.txt.  В  файле  maze.txt записаны номера всех
клеток,  где  находятся  стены,  т.е. хранится лабиринт. Эти лабиринты
будут  участвовать  в  тестировании  программ  участников.  Сами тесты
баллов не приносят, но могут снизить количество баллов у соперников.

Эту задачу решать нужно лично, не командой.

                                             Автор задачи: В.В.Пупышев


19 декабря 2002 последний день присылать решения.

16 декабря 2002 последний день задавать вопросы по формулировке задачи.



--
До свидания.                     Жюри студенческого конкурса проекта КОМП
                                 e-mail: grantadmin@mark-itt.ru
                                 http://colymp.da.ru
                                 05.12.2002
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное