Главная
страница 1






International Olympiad in Informatics 2011

ELEPHANTS

22–29 July 2011, Pattaya City, Thailand

Competition Tasks – Day 2

Русский Russian 1.1203






Танцующие слоны


Танцующие слоны — это зрелищное шоу в Паттайе, в котором участвуюет N слонов, танцующих в на однойу линиию, называемую называемой сценой.

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

Постановщики шоу хотят сделать фотоальбом, который бы содержал фотографии всего шоу. После каждого акта они хотят сделать фотографии всех слонов, которых могут наблюдать зрители.

В любой момент времени на протяжении шоу, некоторое количество слонов может находиться в одной и той же позиции – — это значит, что слоны просто стоят один за другим рядом.

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

К примеру, предположим, что L = 10 и слоны располагаются на сцене в позициях 10, 15, 17, и 20 соответственно. В этот момент достаточно одной фотокамеры, чтобы сфотографировать всех слонов, как это показано ниже. (Слоны изображены как треугольники; фотокамеры изображены как трапеции).



В последующем акте слон, находящийся в позиции 15, в результате танцевального движения перемещается в позицию 32. После этого акта, необходимо уже не менее двух фотокамер для того, чтобы сфотографировать всех слонов одновременно.



В следующем акте слон, находящийся в позиции 10, перемещается в позицию 7. В данном случае понадобится 3 фотокамеры для того, чтобы сфотографировать всех слонов.



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


Задание


Реализовать Написать следующие процедуры:

  • Процедура Процедуру init(N,L,X), которой передаются следующие параметры:

    • N – — количество слонов. Слоны нумеруются от 0 до (N-1).

    • L —– Длина отрезка, охватываемого одной фотокамерой. Гарантируется, что целое число L удовлетворяет ограничению:
          L     1 000 000 000.

    • X —– одномерный массив целых чисел, представляющий собой начальные позиции слонов. Для каждого i (, 0     i < N), слон с номером i находится в позиции X[i].
      Начальные позиции упорядочены. Точнее, гарантируется, что 
          X[0]      ...      X[N-1]      1 000 000 000. Следует отметить, что в течениеи танца при изменении позиции слонов может из меняться и порядок их следования.

Эта процедура будет вызвана ровно один раз (, до всех вызовов процедуры update). Эта процедура не возвращает никакого значения.

  • Процедурау update(i,y), которой передаются следующие параметры:

    • i —– номер слона, который передвигается в данном акте.

    • y — – позиция, в которой слон с номером i будет стоять после данного акта. Гарантируется, что целое число y удовлетворяет ограничению:     y      1  000  000  000.

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

Пример


Рассмотрим случайпример, где N=4, L=10, и начальные позиции слонов следующие:

X=

10

15

17

20

Сначала, Ваша процедура init будет вызвана с этими вышеописанными параметрами. Далее, вашаПосле этого процедура update будет вызываться один раз на для каждогоый акта. Ниже приводится пример последовательности вызовов и правильных возвращаемых значений:

Акт

Параметры вызова

Возвращаемое значение

1

update(2,16)

1

2

update(1,25)

2

3

update(3,35)

2

4

update(0,38)

2

5

update(2,0)

3



Подзадачи

Подзадача 1 (10 баллов)


  • Имеется ровно два слона (N = 2 слона).

  • В начале и после каждого акта, все позиции слонов различны.

  • Ваша пПроцедура update будет вызвана не более 100 раз.

Подзадача 2 (16 баллов)


  • 1     N     100.

  • В начале и после каждого акта, все позиции слонов различны.

  • Ваша пПроцедура update будет вызвана не более 100 раз.

Подзадача 3 (24 балла)


  • 1     N     50 000.

  • В начале и после каждого акта, все позиции слонов различны.

  • Ваша Ппроцедура update будет вызвана не более 50 000 раз.

Подзадача 4 (47 баллов)


  • 1     N     70 000.

  • Слоны могут занимать одну и ту же позицию.

  • Ваша Ппроцедура update будет вызвана не более 70 000 раз.

Подзадача 5 (3 балла)


  • 1     N     150 000.

  • Слоны могут занимать одну и ту же позицию.

  • Ваша пПроцедура update будет вызвана не более 150 000 раз.



  • Необходимо обратить внимание на замечание об использовании коллекции шаблонов в разделе “Детали реализации”.

Обратите внимание на ограничение процессорного времени в секции Детали Реализации.

Детали реализации

Ограничения


  • Ограничение по времениОграничение процессорного времени: 9 секунд.
    ВниманиеЗамечание: Шаблоны коллекцийКоллекции шаблонов (collection templates) для в стандартной библиотеке шаблонов языка C++ (в STL) могут быть работать медленноыми, в частности, может оказаться невозможным решить подзадачу 5 в случае их использования.

  • Ограничение по памяти: 256 MB
    Замечание: Нет отдельного ограничения на размер стека; используемая стеком память входит в общий объём используемой памяти.


Интерфейс (API)


  • Папка для разработки: elephants/

  • Участник должен разработать: elephants.c или elephants.cpp или elephants.pas

  • Интерфейс участника: elephants.h или elephants.pas

  • Предлагаемый модуль оценивания:Интерфейс модуля оценивания: grader.c или grader.cpp или grader.pas

  • Ввод для предлагаемого модуля оцениванияПредлагаемый модуль оценивания: grader.in.1, grader.in.2, ...

Замечание: Предлагаемый модуль оценивания читает входной файл в следующем формате:

    • Строка 1: N, L, и M, где M – — количество актов в шоу.

    • Строки со от 2 дпо (N+1): начальные позиции; то есть.е. строка с номером (k+2) содержит значение X[k] для каждого 0     k < N.

    • Строки с от (N+2) дпо (N+M+1) содержат информацию об M актах; то естьт.е,. строка с номером (N+1+j) для 1    j    M содержит значения i[j], y[j], и s[j], разделенные одним пробелом, и обозначает, что в j-ом акте слон elephant с номером i[j] перемещается в позицию y[j],, при этоми после этого акта, s[j] – — это минимальное количество необходимых фотокамер после этого акта для 1 j M.

  • Ожидаемый вывод для предлагаемого модуля оценивания: grader.expect.1, grader.expect.2, … В этой задаче каждый из перечисленных файлов должен содержать только текст “Correct.

Страница из


Смотрите также:
Elephants 22–29 July 2011, Pattaya City, Thailand Competition Tasks – Day 2 Русский Russian 1203 Танцующие слоны — это зрелищное шоу в Паттайе, в котором участвуюет N
72.42kb.
1 стр.
Премьера мюзикла Love Story в стиле индийского кино на московской сцене
12.26kb.
1 стр.
Экскурсии в таиланде экскурсии из паттайи
87.6kb.
1 стр.
31 July 2010 russian original: english конференция сторон конвенции о биологическом разнообразии десятое совещание
484.23kb.
2 стр.
Шоу анатолия евдокимова
30.71kb.
1 стр.
27 July 2012 russian original: english onl конференция сторон конвенции о биологическом разнообразии одиннадцатое совещание
258.68kb.
1 стр.
Ii часть: «The best of …» лучшие номер за 2009 и 2010 гг
48.93kb.
1 стр.
Экскурсии в Паттайе
181.93kb.
1 стр.
Соглашение онлайн магазин «Thailand Silver»
38.72kb.
1 стр.
Царство: Животные Тип: Хордовые
9.46kb.
1 стр.
Каждый август в португальском городе Абиуле проходит праздник рождения корриды, основной изюминкой которого является проведение корриды с соблюдением всех традиций
17.5kb.
1 стр.
Урок проект (4 класс) " People and animals in the country and in the city". Цели: повторение и обобщение темы \"
28.86kb.
1 стр.