основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Олимпиады >> Задачи

Страницы: 1
Gleb_Grenkin
здесь был не раз


Рег.: 07/27/04
Сообщений: 32
Из: Vladivostok, Russia
SNSS 5: D ("Пауки и муха")
      #11912 - 08/23/06 11:00 PM

Не понятно условие задачи D.
"сколько клеток проползла муха" - это значит сколько узлов?
"каждый из них записывает, сколько клеток проползла муха, прежде чем повернуться спиной к пауку" - с какого времени начинается отсчёт? Число означает, сколько клеток проползла муха, если считать от предыдущей записи или с начала пути мухи?

И почему в примере из условия задачи 0 у второго паука?
Ведь, если муха сначала стояла спиной к первому, то нуля нигде нет или ноль у первого паука (условие не понятно). А если муха сначала стояла спиной ко второму, то ноль должен появиться и у первого.

Привожу условие задачи.

Задача D. ПАУКИ И МУХА

Входной файл: input.txt

Выходной файл: output.txt

Ограничение по времени: 2 сек.


Муха ползёт по квадратной проволочной сетке размером N*N (1&#61603;N<100). Её путь начинается из левого нижнего угла (узел 0, 0). Муха может ползти вверх, вниз, влево или вправо, меняя направление в узлах сетки, но не покидая её.

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

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

Будем считать, что паук номер 1 сидит слева, паук номер 2 сидит снизу, паук номер 3 сидит справа, паук номер 4 сидит сверху. Муха всегда начинает путь из левого нижнего узла (координаты 0, 0). В координатах узлов первое число обозначает номер горизонтали, а второе – номер вертикали, которым принадлежит узел. Первая запись пауков один или два может быть равна нулю, в зависимости от выбранного мухой первоначального направления движения. Пока муха ползет спиной к пауку, он клетки не подсчитывает, поэтому других нулей в записях пауков нет. Все записи пауков корректны.

Формат входных данных:

В первой строке входного файла задаётся N длина стороны сетки. Во второй строке – количество чисел в записи первого паука. В третьей – числа, записанные первым пауком, разделенные одним пробелом. В четвёртой строке – количество чисел в записи второго паука. В пятой – числа, записанные вторым пауком, разделенные одним пробелом. В шестой строке – количество чисел в записи третьего паука. В седьмой – числа, записанные третьим пауком, разделенные одним пробелом. В восьмой строке – количество чисел в записи четвертого паука. В девятой – числа, записанные четвёртым пауком, разделенные одним пробелом.

Формат выходных данных:

В каждой строке выходного файла находится пара чисел – координаты узла сетки, разделённые одним пробелом. В первой строке – координаты 0 0. В следующих строках – координаты промежуточных узлов в порядке посещения их мухой. В последней строке – координаты узла, в котором остановилась муха.

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

1
1
1
2
0 1
1
2
1
2

Пример
выходных данных:
0 0
1 0


Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 387 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, Sergeyev, M_Gustokashin 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 7727

Rate this topic

Переход в