Страница: << 321 322 323 324 325 326 327 >> Отображать по:

#113937

Гномы, шляпы и экстрасенсорные способности

Темы: [Интерактивные задачи] [Бинарный поиск]

Это интерактивная задача.

В былые времена гномы пытались развить у себя экстрасенсорные способности:

В абсолютно тёмную пещеру заводили n гномов.
На каждого гнома надевали шляпу — белую или чёрную. Гномы в пещере не видели цветов своих шляп и шляп других гномов.
Гномы по очереди выходили из пещеры на поляну и садились на произвольное места. При этом, выходя из пещеры, каждый гном видел цвета шляп всех гномов, вышедших ранее. Тем не менее, он не видит цвет собственной шляпы и никто из других гномов ему этот цвет не сообщает.
Задача состояла в том, чтобы все гномы разошлись в две стороны — в одну те, кто носят белые шляпы и в другую — чёрные.

За многие века гномы научились безошибочно выбирать для себя место на поляне. Получится ли подобное у вас?

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

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

Протокол взаимодействия

В первой строке стандартного потока ввода дано целое число n ( 1 ≤ n ≤ 30 ) — количество точек, которое должна назвать ваша программа.

Затем n раз ваша программа должна вывести по два целых числа x и y ( 0 ≤ x ≤ 10 ⁹ , 0 ≤ y ≤ 10 ⁹ ) — координаты очередной точки. Все выведенные вами точки должны быть различными.

В ответ на каждую пару координат ваша программа получит на вход строку « black », если точка имеет чёрный цвет, или « white », если точка имеет белый цвет.

После того, как все n точек будут обработаны, вы должны вывести четыре целых числа x ₁ , y ₁ , x ₂ и y ₂ ( 0 ≤ x ₁ , y ₁ ≤ 10 ⁹ , 0 ≤ x ₂ , y ₂ ≤ 10 ⁹ ) — координаты точек ( x ₁ , y ₁ ) и ( x ₂ , y ₂ ) , через которые проходит прямая, разделяющая n точек на белые и чёрные. Точки ( x ₁ , y ₁ ) и ( x ₂ , y ₂ ) не должны совпадать.

Примечание

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

Иллюстрация к первому примеру.

$\text{[math]}$

Примеры

Входные данные

5

black

black

white

white

black

Выходные данные

#113940

Петербург?

Темы: [Интерактивные задачи] [Мосты] [Алгоритмы на графах]

– Это что за остановка – Бологое иль Поповка? – А с платформы говорят: – Это город Ленинград.

«Вот какой рассеянный», Самуил Маршак

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

Проснувшись и открыв окно, Алина задалась вопросом весьма философского свойства: «Где я?». С перрона потерявшейся девочке сообщили, что этот город, не похожий ни на что вокруг, представляет собой неориентированный граф на $n$ вершинах и $m$ ребрах. Сeй невероятный факт, однако, нисколько не удивил Алину. Она давно мечтала побывать в одном таком городе — Петербурге. Его уникальной отличительной особенностью является то, что хотя бы половина его ребер — мосты (определение дано в конце условия). Так как никакие другие города Алине не интересны, она решила ограничиться расспросом находящихся на платформе эрудированных путешественников. Любой из их них может по данной вершине $v$ сообщить любое ещё не названное ребро, исходящее из нее, или же заявить об отсутствии таковых.

Алина неуверена в своих силах, поэтому попросила вас помочь ей определить, попала ли она в Петербург. Так как её поезд скоро продолжит свой путь, задать больше $3n$ вопросов не получится.

Обратите внимание, что в графе могут присутствовать петли и кратные ребра.

Протокол взаимодействия

В первой строке стандартного потока ввода даны два целых числа $n$ и $m$ ($1 \le n, m \le 100\,000$) — число вершин и ребер в графе соответственно.

Для того, чтобы узнать очередное ребро, исходящее из $u$-й вершины ($1 \le u \le n$), нужно вывести « ? $u$ ». После этого ваша программа на вход получит целое число $v$ ($-2 \le v \le -1$ или $1 \le v \le n$) — $v = a + b - u$, если существует ребро $ab$, которое инцидентно вершине $u$ и ещё не было названо , $-1$, если такого ребра не существует и $-2$, если вы превысили допустимое число запросов. В последнем случае ваша программа должна немедленно завершиться, в ином случае жюри не гарантирует корректность полученного вами вердикта.

Вам разрешается задать не более $3n$ вопросов.

Чтобы сообщить, что ответ найден, требуется вывести « ! Yes » или « ! No », в зависимости от того, является ли загаданный граф Петербургом. В случае положительного ответа выведите $\lceil\frac{m}{2}\rceil$ строк, по два целых числа $u_i$ и $v_i$ в каждой ($1 \le u_i, v_i \le n$), обозначающих, что ребро $(u_i, v_i)$ является мостом. Любое ребро в приведенном списке должно встречаться не более одного раза (кратные ребра считаются различными).

Запрос на вывод ответа не входит в ограничение на $3n$ запросов.

Не забывайте сбрасывать буфер после каждого запроса. Например, на языке C++ надо использовать функцию fflush(stdout) или вызов cout.flush() , на Java вызов System.out.flush() , на Pascal flush(output) и stdout.flush() для языка Python.

Система оценки

Подзадача 0. Тесты из условия

Подзадача 1. (27 баллов) $N, M \leq 10$. Пройдена подзадача 0.

Подзадача 2. (30 баллов) $N \leq 10000, M \leq 20000$. Пройдена подзадача 1.

Подзадача 3. (1 балл за каждый пройденный тест) Нет дополнительных ограничений. Пройдена подзадача 2.

Примечание

Ввод-вывод в примерах демонстрирует пример взаимодействия вашей программы с проверяющей системой.

В первом примере был загадан граф на трех вершинах с ребрами $(1, 2)$, $(2, 3)$ и $(3, 1)$.

Во втором примере была загадан граф на четырех вершинах с ребрами $(1, 2)$, $(2, 3)$, $(3, 4)$ и $(2, 3)$.

Ребро, соединяющее вершины $u$ и $v$, называется мостом, если после его удаления между вершинами $u$ и $v$ не существует пути.

Примеры

Входные данные

Выходные данные

? 3

? 1

? 2

? 1

? 1

? 3

! No

Входные данные

Выходные данные

? 1

? 2

? 3

? 1

? 3

? 3

? 2

? 4

! Yes
1 2
3 4

#113941

Слабое звено

Темы: [Задачи на моделирование] [Список]

В Берляндии по воскресеньям проходит известое шоу — игра «Слабое звено».

В игре принимают участие $n$ игроков, которые выстраиваются в круг. Каждому игроку сопоставлен рейтинг — некоторое целое число $a_i$.

Игра проходит в несколько раундов, каждый из которых выглядит следующим образом:

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

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

Вам нужно выяснить для каждого участника, останется ли он до конца, или номер раунда, в котором он покинет игру.

Входные данные

В первой строке дано одно целое число $n$ ($2 \le n \le 200\,000$) — количество участников в игре.

Вторая строка содержит $n$ целых чисел $a_i$ ($1 \le a_i \le 200\,000$) — рейтинги всех участников игры в том порядке, в котором они стоят, при этом участник с номером $n$ является соседом участника с номером $1$.

Выходные данные

Выведите $n$ целых чисел — номер раунда, в котором участник игры с номером $i$ покинет игру, или $0$, если этот игрок останется до конца игры.

Раунды нумеруются последовательными целыми числами начиная с $1$.

Примечание

В первом примере игра проходит следующим образом (при помощи _ обозначаются выбывшие участники):

$[4; 5; 5; 2; 3] \to [4; 5; 5; \_; 3] \to [4; 5; 5; \_; \_] \to [\_; 5; 5; \_; \_]$

После этого игра заканчивается, так как осталось ровно два человека.

Во втором примере игра проходит следующим образом:

$[5; 1; 3; 1; 5] \to [5; \_; 3; \_; 5] \to [5; \_; \_; \_; 5]$

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

Примеры

Входные данные

5
4 5 5 2 3

Выходные данные

3 0 0 1 2

Входные данные

5
5 1 3 1 5

Выходные данные

0 1 2 1 0

Входные данные

3
6 6 6

Выходные данные

0 0 0

Входные данные

4
6 5 5 6

Выходные данные

0 0 0 0

#113942

Бургеры в McDuck's

Темы: [Динамическое программирование] [Динамическое программирование: два параметра]

Популярная сеть быстрого питания «McDuck's» открыла новый филиал в Берляндии. В ресторане установлено $k$ плит. Для того чтобы приготовить бургер, надо жарить котлету в течение минуты на одной из плит, поэтому ресторан может готовить не более $k$ бургеров в минуту.

Известно, что в «McDuck's» придут $n$ клиентов. $i$-й из них придёт в момент времени $t_i$, закажет $x_i$ бургеров и будет готов заплатить за них $c_i$ бурлей. Каждый клиент готов ждать заказ в течение $w$ минут и, если через $w$ минут после прихода он не получил $x_i$ бургеров, он не заплатит ничего. При этом каждый клиент готов получать только свежие бургеры, то есть только те, котлеты для которых были поджарены не раньше времени $t_i$. Из-за таких сложных требований ресторан не всегда сможет выполнить все заказы всех клиентов.

Менеджеров ресторана заинтересовало, какую максимальную прибыль может получить «McDuck's». Помогите им ответить на этот непростой вопрос. Можно считать, что на готовку бургеров не расходуется никаких денег.

Входные данные

В первой строке содержатся три целых числа $n$, $k$ и $w$ ($1 \le n \le 100\,000$, $1 \le k \le 10$, $1 \le w \le 60$) — число клиентов, число плит и время ожидания клиента, соответственно.

Следующие $n$ строк содержат описания клиентов, состоящие из трёх целых чисел — $t_i$, $x_i$, $c_i$ ($1 \le t_i, x_i, c_i \le 10^9$) — время (в минутах) прихода $i$-го клиента, число бургеров, которые он закажет и число бурлей, которые он готов заплатить, соответственно. Клиенты перечислены в порядке возрастания времени прихода, то есть для любого $i \ge 2$ верно, что $t_{i - 1} \le t_i$.

Выходные данные

В единственной строке выведите одно число — максимальную прибыль ресторана.

Примечание

В первом тестовом примере первую котлету можно поставить жариться в момент времени 0 и тогда в момент времени 1 она будет готова и её можно будет дать в бургере первому клиенту. В момент времени 1 можно поставить жариться ещё одну котлету, она будет готова в момент времени 2 и её можно будет дать в бургере второму клиенту.

Примеры

Входные данные

2 1 1
1 1 5
1 1 7

Выходные данные

Входные данные

Выходные данные

#113943

Конфеты детям

Темы: [Арифметические алгоритмы] [Остатки] [Перебор]

На детском празднике дети водили хороводы. Как только музыка закончила играть, дети всё ещё стояли в кругу. Тут Лена вспомнила, что родители дали ей коробку с $k$ конфетками «Wilky May». Лена не жадина, поэтому она решила раздать все свои конфетки друзьям из хоровода. Лена знает, что некоторые её друзья сладкоежки, а некоторые нет. Сладкоежки берут из коробки две конфетки, если в коробке есть хотя бы две конфетки, а иначе берут одну. Остальные друзья Лены всегда берут ровно одну конфетку из коробки.

Чтобы начать раздавать конфетки, Лена вышла из хоровода, после чего в хороводе остались $n$ ее друзей. Чтобы раздавать конфетки было проще, Лена присвоила каждому другу в хороводе номер в порядке по часовой стрелке, начиная с её лучшего друга Ромы, который получил номер $1$.

Лена дала коробку другу, который получил номер $l$, после чего каждый друг Лены, начиная с друга с номером $l$, брал конфетки из коробки и передавал коробку следующему в порядке по часовой стрелке другу. После того, как друг с номером $r$ взял конфетки, в коробке конфеток не осталось. Обратите внимание, что возможно, что некоторые друзья Лены брали конфетки из коробки несколько раз, то есть коробка могла пройти несколько полных кругов по хороводу.

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

Входные данные

В единственной строке задаются четыре целых числа $n$, $l$, $r$, $k$ ($1 \le n, k \le 100$, $1 \le l, r \le n$) — количество детей в хороводе, номер друга, которому Лена отдала коробку конфет, номер друга, который взял последнюю конфетку и количество конфет в коробке, соответственно.

Выходные данные

Выведите одно целое число — максимально возможное количество сладкоежек среди друзей Лены или « -1 » (без кавычек), если Лена ошиблась в своих наблюдениях.

Примечание

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

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

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

В четвёртом примере Лена ошиблась и такой ситуации быть не могло.

Примеры

Входные данные

4 1 4 12

Выходные данные

Входные данные

5 3 4 10

Выходные данные

Входные данные

10 5 5 1

Выходные данные

Входные данные

5 4 5 6

Выходные данные

-1

Страница: << 321 322 323 324 325 326 327 >> Отображать по:

Выбрано

Отменить

Добавить в контест