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

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

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

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

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

←   Февраль 2003   →
 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
Автор
ss77_ss77@mail.ru

Статистика

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

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


Информационный Канал Subscribe.Ru 
Продолжение материалов прошлой олимпиады школьников.

-----------------------------------------
 Полная формулировка задачи третьего тура.

     Яблоневый сад

У  одного фермера есть квадратный участок земли 10000 метров в длину и
10000 метров в ширину. Это поле мысленно разлиновано на клетки с шагом
в 1 метр. Линии пронумерованы от 0 до 10000. Таким образом, получилась
координатная сетка.

Фермер  посадил яблони точно в узлах (точках пересечения линий) сетки.
Ни  одна яблоня не посажена на краю участка. Теперь он решил поставить
вокруг  забор.  Забор нужно поставить так, чтобы выполнялись следующие
условия:
 1) должен состоять из четырёх прямых пролётов одинаковой длины;
 2) должен быть непрерывным;
 3) углы должны находится точно в узлах сетки;
 4) все яблони должны быть внутри области огороженной забором.
Желательно, чтобы забор был покороче.

Техническое задание
Расположение  узла  с  деревом задаётся двумя числами, номерами линий,
при пересечении которых получается этот узел. Расположение всех яблонь
задается  в  файле  orchard.txt  следующим  образом.  В  первой строке
записано  одно  число  -  количество яблонь. Начиная со второй, строки
записаны  пары  чисел  - расположение узлов. Пар столько же, сколько и
яблонь.  Числа  разделены пробелами. Нужно написать программу, которая
читает  файл  orchard.txt  и не позже чем через 10 секунд записывает в
файл fence.txt пары чисел - узлы, где должны быть углы забора.

ПРИМЕР
В orchard.txt
 3
  1  1
  5  6
 30 30

В fence.txt
 0  0
 40 40
 30 10
 10 30

Оценка задачи
Оцениваться  будет  длина забора, чем короче, тем больше баллов. Среди
программ будет проведено соревнование.
  Правила  таковы.  Тесты  проходятся в порядке увеличения числа яблонь.
Если  программа  три  раза  не проходит тесты или проходит не с лучшим
результатом,   то   она   не   участвует  в  дальнейшем  тестировании.
Тестирование  продолжается,  пока  не  останется  одна программа. Всем
программам   начисляются   баллы  за  пройденные  тесты.  Максимальное
количество 100 баллов.

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



Последний день решения задачи - 30 мая 2002 года.

Последний день задавать вопросы по условию задачи - 23 мая 2002 года.





                                 До свидания.

                                 Жюри школьного конкурса Марк
                                 olymp_mark@uni.udm.ru
                                 http://olymp.udm.ru
                                 16.05.02
----------------------------------------------------
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное