Страница: << 518 519 520 521 522 523 524 >> Отображать по:

#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

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

#113938

Уравнения математической магии

Темы: [Битовые операции] [Разбор случаев]

Колоссально! — воскликнул горбоносый. — Программист! Нам нужен именно программист.

Аркадий и Борис Стругацкие, Понедельник начинается в субботу

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

Вам предстоит решить задачу для нескольких возможных значений параметра $a$. В первой строке находится целое число $t$ ($1 \le t \le 1000$) — количество этих значений.

В последующих $t$ строках находятся значения параметра $a$, каждое значение — целое число от $0$ до $2^{30} - 1$ включительно.

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

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

Можно доказать, что количество решений всегда конечно.

Примечание

Определим операцию побитового исключительного ИЛИ (XOR).

Пусть даны два целых неотрицательных числа $x$ и $y$, рассмотрим их двоичные записи (возможно с ведущими нулями): $x_k \dots x_2 x_1 x_0$ и $y_k \dots y_2 y_1 y_0$. Здесь $x_i$ это $i$-й бит числа $x$, а $y_i$ это $i$-й бит числа $y$.

Пусть $r = x \oplus y$ — результат операции XOR над числами $x$ и $y$. Тогда двоичной записью $r$ будет $r_k \dots r_2 r_1 r_0$, где:

 r_i = \left\{ \begin{aligned} 1, ~ \text{если} ~ x_i \ne y_i \\ 0, ~ \text{если} ~ x_i = y_i \end{aligned} \right. 

Для первого значения параметра только $x = 0$ является решением уравнения.

Для второго значения параметра решениями уравнения являются $x = 0$ и $x = 2$.

Примеры

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

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

1
2
1073741824

#113939

Уравнения математической магии

Темы: [Разбор случаев] [Битовые операции]

Колоссально! — воскликнул горбоносый. — Программист! Нам нужен именно программист.

Аркадий и Борис Стругацкие, Понедельник начинается в субботу

Изучая книгу «Уравнения математической магии» Роман Ойра-Ойра и Кристобаль Хунта обнаружили интересное уравнение: $a - (a \oplus x) - x = 0$ для заданого $a$, где знаком $\oplus$ обозначено побитовое исключающее ИЛИ (XOR) двух чисел (эта операция обозначается как ^ или xor во многих современных языках программирования). Поскольку данное уравнение предназначалось для решения на машине Алдан-3, все вычисления производились над целыми неотрицательными числами по модулю $2^{32}$. Ойра-Ойра быстро нашел $x$, являющееся решением, однако Кристобалю Хунте результат Ойры-Ойры показался недостаточно интересным, поэтому он спросил коллегу, сколько всего существует решений данного уравнения. Так как все вычисления производятся по модулю $2^{32}$, Кристобаля Хунту интересует количество таких решений $x$, что $0 \leq x < 2^{32}$. Такая задача оказалась для Ойры-Ойры слишком сложной, поэтому он обратился за помощью к Вам.

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

В первой строке задано одно целое число $a$ ($0 \leq a \leq 2^{32} - 1$).

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

Выведите одно целое число — количество неотрицательных решений уравнения.

Примечание

Определим операцию побитового ИЛИ (XOR). Пусть даны два целых неотрицательных числа $x$ и $y$, рассмотрим их двоичные записи (возможно с ведущими нулями): $x_k \dots x_2 x_1 x_0$ и $y_k \dots y_2 y_1 y_0$. Здесь $x_i$ это $i$-й бит числа $x$, а $y_i$ это $i$-й бит числа $y$. Пусть $r = x \oplus y$ — результат операции XOR над числами $x$ и $y$. Тогда двоичной записью $r$ будет $r_k \dots r_2 r_1 r_0$, где:

 r_i = \left\{ \begin{aligned} 1, ~ \text{если} ~ x_i \ne y_i \\ 0, ~ \text{если} ~ x_i = y_i \end{aligned} \right. 

В первом примере решениями уравнения являются $0$ и $2147483648 = 2^{31}$, так как $0 - (0 \oplus 0) - 0 = 0 - 0 - 0 = 0$ и $0 - (0 \oplus 2147483648) - 2147483648 = -4294967296 = -2^{32} = 0$ по модулю $2^{32}$.

Во втором примере решениями уравнения являются $0$, $2$, $2147483648 = 2^{31}$ и $2147483650 = 2^{31} + 2$.

В третьем примере решениями являются все $x$, для которых выполнено $0 \leq x < 2^{32}$.

Примеры

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

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

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

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

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

4294967295

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

4294967296

#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

Страница: << 518 519 520 521 522 523 524 >> Отображать по:

Выбрано

Отменить

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