На данный момент все N ЂЂЂ 1 рыцарей, кроме опаздывающего, уже заняли свои места в ряду. Леонардо имеет возможность поставить прибывшего фаворита на любое место в ряду, в том числе в начало или в конец. Порядок сражений и позиции рыцарей, в них участвующих, уже определены. Леонардо знает для каждого рыцаря значение его абстрактной ЂЂЂсилыЂЂЂ, выражаемое целым числом от 0 до N ЂЂЂ 1. В рамках этой задачи считается, что в сражении, в котором участвует определённые рыцари, в любом случае побеждает тот из них, который имеет наибольшее значение силы. Так сложилось, что на турнире все рыцари различны по силе, то есть в любом сражении победитель определяется однозначно исходя их знания их значений. Леонардо хочет добиться того, чтобы по итогам турнира количество сражений, в которых победил любимец толпы, было как можно большим, а из всех позиций, приводящих к такому исходу, он хочет выбрать самую левую. Обратите внимание: необязательно, чтобы наш рыцарь становился победителем всего турнира! Достаточно максимизировать количество сражений, из которых он вышел победителем.
Рыцарский турнир происходит следующим образом. В ряд стоит некоторое количество рыцарей. Перед каждым очередным сражением выходит судья и вызывает рыцарей, стоящих на позициях, образующих непрерывной отрезок, на поединок, в результате которого определяется победитель. Победитель возвращается на своё место, а проигравшие рыцари выбывают. После этого ряд рыцарей сдвигается, занимая пустые места. Более формально: в ряд стоят N рыцарей, судья называет два числа l и r, после этого рыцари, занимающие в порядке нумерации слева направо места с l-ого по r-ое, сражаются и из них в ряду остаётся только победитель. После этого происходят последующие сражения по такому же принципу до тех пор, пока не останется один рыцарь, который объявляется победителем турнира.
Такая вот захватывающая история.
И вот, к началу празднеств оказалось, что вовремя прибыли все рыцари, кроме одного, который опаздывает, но не настолько сильно, чтобы помешать проведению турнира. По случайному совпадению, этот рыцарь был фаворитом толпы, и все сражения с его участием пользовались большой популярностью. Леонардо знает расписание боёв турнира и то, как будут выбираться рыцари для участия в них, и он хочет слегка повлиять на ход турнира таким образом, чтобы рыцарь-фаворит поучаствовал в как можно большем количестве сражений. Так хитрый пиарщик Леонардо собирается увеличить значимость события.
В задаче идёт речь о церемонии обручения герцога Лодовико Сфорца, наместника Милана, и герцогини Беатриче дЂЂЂЭсте, произошедшей в 1491. Организовывать празднества и управлять культурной программой герцог пригласил своего хорошего друга Леонардо да Винчи, который ему предложил, в частности, устроить шикарный рыцарский турнир.
Я ЂЂЂ Макс Ахмедов. Мне предложили поделиться с общественностью, что представляют собой подобные соревнования и какие задачи нам приходится решать. Я расскажу о последней задаче второго тура «Jousting Tournament». Английский вариант условия можно найти . К слову, это наиболее простая из трёх задач в тот день :-)
Всем привет! В сентябре прошла международная олимпиада по программированию, IOI 2012. И мы, сборная России, на неё весьма успешно , как вы могли видеть.
Разбор задачи с IOI2012 / Блог компании ABBYY / Хабрахабр
Комментариев нет:
Отправить комментарий