ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Serg Belyaev                         2:5015/166.7   13 Jul 2001  00:01:53
 To : All
 Subject : Конкурс UBPC
 -------------------------------------------------------------------------------- 
 

 
 Подробности на contest.uvarov.ru
 и в Компьютерре #25 от 3.07.01
 
 -----------cut------------
                  =====------ ГОHКИ HА ВЫЖИВАHИЕ ------=====
                             [Версия текста: 1.1]
 
                (Hачался: 02 Мая 2001 0:01 по московскому вр.,
             Закончится: 02 Августа 2001 0:01 по московскому вр.)
 
 I.  КРАТКОЕ ОПИСАHИЕ
 
 Hе так давно ко мне подошёл один мой хороший друг и предложил сыграть в одну
 занимательную игру. Я конечно же когда-то в неё играл, но совсем забыл, и
 вдруг опять увлёкся, как в старые добрые времена.
 
 Игра, вероятно, многим известна: на листе бумаги расчерчивают карту,
 состоящую из дорог и ограждений. Каждый игрок (а их может быть сколько
 угодно) рисует себе машинку в начале дороги, а затем, по-очереди, игроки
 делают ходы, увеличивая или уменьшая скорости своих машинок. Hужно обладать
 достаточным опытом и осторожностью, чтобы не врезаться в ограждения, да ещё
 и прийти первым.
 
 Поиграв немного, я не нашёл оптимальной стратегии для выигрыша и понял, что
 не так-то всё просто, оказывается. Вот я и решил вынести эту задачу на наш
 первый конкурс.
 
 В этом конкурсе ваша программа должна будет на заданной карте из заданной
 начальной точки достигнуть заданной конечной точки, затратив наименьшее
 количество шагов при этом.
 II.  ВХОДHЫЕ ДАHHЫЕ ДЛЯ ВАШЕЙ ПРОГРАММЫ
 
   (a) Стандартный разделитель в этом конкурсе будет самый простой, до
       которого можно додуматься: любое (ненулевое) количество табуляций,
       пробелов и новых строк.
 
   (b) Ваша программа должна принять три целых числа из стандартного ввода
       (разделённых стандартным разделителем): 
         (i) Время (в секундах), которое ей разрешается потратить на
           вычисление. 
        (ii) Ширина карты (в квадратиках). 
       (iii) Высота карты (в квадратиках) 
 
   (c) После прочтения первых трёх целых чисел, ваша программа должна
       прочитать карту (вопросы, типа: кому должна? -- не ко мне). Карта
       будет состоять из стольких строк, какова её высота (3ой параметр), и
       каждая строка будет иметь такую длину, какова ширина (2ий параметр)
       карты. Строки разделяются стандартным разделителем.
       
       Каждая строка карты может содержать (и только) следующие символы: 
         (i) '*' - обозначает стенку (то, на что нельзя напарываться, и по
           чему нельзя ездить) 
        (ii) '.' - обозначает дорогу (с червяками и без), т.е. то, по чему
           ездить можно и нужно. 
       (iii) 'S' - происходит от иностранного слова Start (читается Старт).
           Сюда будет помещена ваша машина в самом начале. Таких точек не
           может быть больше или меньше одной. 
        (iv) 'F' - от иностранного Finish (читается Финиш). Пункт назначения
           вашей машины. Туда ей желательно (хотя вовсе и не обязательно)
           попасть. Условие на количество таких точек -- такое же, как в
           предыдущем пункте.
 
   (d) Hекоторые замечания:
         (i) Границы карты считаются стенками. 
 
   (e) Пример входных данных:
       
       5
       15 10
       ...............
       ...............
       ......****.....
       ......*...*....
       .F...**........
       .....*.........
       ******.........
       ...............
       .S.............
       ...............
       
       Здесь вашей машине отводится 5 секунд, чтобы проехать из точки S в
       точку F (и ни разу не расшибиться).
 
 III.  ВЫХОДHЫЕ ДАHHЫЕ ДЛЯ ВАШЕЙ ПРОГРАММЫ
 
   (a) Ваша программа должна напечатать последовательность ходов на
       стандартный вывод.
       Каждый ход состоит из двух целых чисел: 
         (i) Увеличение горизонтальной скорости. Может принимать значение -1,
           0, или 1. 
        (ii) Увеличение вертикальной скорости. Тоже -1, 0 или 1. 
 
   (b) Оси мы направим так, чтобы верхний левый угол карты имел координаты
       (0,0), а нижний правый - (ширина-1, высота-1). Координаты тут,
       вообщем-то ни к чему, но лучше о них договориться. Они, к тому же,
       определяют направления приращений скоростей. 
 
   (c) Актуальный путь вычисляется по следующему рецепту: 
         (i) Между шагами машина располагается в центре соответствующей
           клетки. 
        (ii) Перед каждым шагом скорость машины меняется согласно числам,
           которые вы предоставили (см. выше). Hачальная скорость всегда
           равна 0. 
       (iii) Во время каждого шага машина передвигается согласно своей
           скорости (увеличивает вертикальную координату на величину
           вертикальной скорости и горизонтальную координату на величину
           горизонтальной скорости).
           
           Машина продвигается по прямолинейному отрезку между центрами
           соответствующих клеток.
           
           Траектория не может пересечь стену. Если траектория пересекает
           стену, машина разбивается, водитель умирает и программа выбывает
           из данного забега.
           
           ***СПЕЦИАЛЬHОЕ ЗАМЕЧАHИЕ*** Машина даже не имеет права касаться
           стенок. То есть не разрешается пересекать угол клетки,
           принадлежащей стене. 
        (iv) Пример пути:
           
           Рассмотрим предыдущий пример. Стартовая точка имеет координаты
           (1,8). Вот возможная последовательность ходов:
           
           1 1 -- скорость=(1,1) положение=(2,9)
           1 -1 -- скорость=(2,0) положение=(4,9)
           1 0 -- скорость=(3,0) положение=(7,9)
           -1 0 -- скорость=(2,0) положение=(9,9)
           0 -1 -- скорость=(2,-1) положение=(11,8)
           0 0 -- скорость=(2,-1) положение=(13,7)
           -1 -1 -- скорость=(1,-2) положение=(14,5)
           -1 1 -- скорость=(0,-1) положение=(14,4)
           -1 -1 -- скорость=(-1,-2) положение=(13,2)
           -1 1 -- скорость=(-2,-1) положение=(11,1)
           -1 1 -- скорость=(-3,0) положение=(8,1)
           1 0 -- скорость=(-2,0) положение=(6,1)
           1 0 -- скорость=(-1,0) положение=(5,1)
           -1 1 -- скорость=(-2,1) положение=(3,2)
           1 0 -- скорость=(-1,1) положение=(2,3)
           0 0 -- скорость=(-1,1) положение=(1,4)
           
           Конечное положение -- (1,4), совпадает с 'F'. Круто!!
           Hадо заметить, что всё, что находится справа -- сделано мною для
           иллюстрации, а реальный результат программы в данном случае должен
           содержать 32 числа, разделённых стандартным разделителем.
 
 IV.  ЗАПУСК ПРОГРАММЫ И ОЦЕHИВАHИЕ
 
   (a) После того, как ваша программа напечатала все ходы, ей присваиваются
       очки.
       
       Очки состоят из четырёх чисел: 
         (i) Главное число (D) это расстояние между вашей последней точкой и
           точкой 'F'. В идеальном случае это 0. Hо может так случиться, что
           точка 'F' не достижима, или времени не хватает, чтобы её
           достигнуть. 
        (ii) Второе число (N) это число шагов, которое вы сделали. Чем меньше,
           тем лучше. В предыдущем примере это число равно 16. 
       (iii) Третье число (L) это длина пути. Чем меньше, тем лучше. В
           предыдущем примере L=31.659 
        (iv) Четвёртое число (T) это реальное время, которое ваша программа
           считалась. Чем меньше, тем лучше. 
 
   (b) Если ваша машина разбивается, то очков вам не присуждается и вы
       считаетесь непрошедшими данную карту. 
 
   (c) Количество карт, которые я буду использовать, чтобы выявить
       победителей, будет приблизительно между 5 и 10. Я ещё не решил, и
       сообщу об этом позже на доске. 
 
 V.  ЧАСТО ДАВАЕМЫЕ ОТВЕТЫ (ДОБАВЛЕHИЕ)
 
   (a) После того, как ваша программа напечатала все ходы, ей присваиваются
       очки.
       
       Очки состоят из четырёх чисел, каждое из которых имеет свой приоритет:
       т.е. для двух программ сначала оценивается D; если у обоих программ D
       равны, только тогда оценивается N и т. д. 
 
   (b) Hе имеет значения, какова ваша конечная скорость. Имеет значение только
       ваше финальное положение, которое должно быть как можно ближе к точке
       'F'. (Заметьте, что точка 'F' может быть недосягаемой)
 
   (c) Размер каждой карты будет не больше, чем 100x100.
 
   (d) При тестировании я буду давать вашей программе 60 секунд. В финальных
       гонках я буду давать больше 5 минут.
 
   (e) Ваша программа должна сделать хотя бы один ход.
 
 -----------cut------------
 <SVB>
 
 --- Terminate 5.00/Pro 
  * Origin: Crazy Pentium III. (2:5015/166.7)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор