e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Olympiad in Informatics, IV Stage, I Round

Ты k-ый?

У Казака Уса имеются три секретных массива $a$, $b$, $c$ из натуральных чисел. Обозначим их длины как $|a|$, $|b|$ и $|c|$ соответственно. Эти длины не обязательно одинаковы. Известно, что каждый массив отсортирован, то есть, каждый следующий элемент не меньше предыдущего. Вы хотите получить определенную информацию об этих массивы, а именно~--- значение $k$ -го элемента в отсортированном объединении массивов. То есть, если из этих трех массивов сделать один большой массив длины $|a|+|b|+|c|$, отсортировать его, то следует узнать $k$ -ый элемент в таком массиве. Казак Ус отказывается показывать Вам эти массивы. Однако он согласился на следующее: Вы можете узнавать значение определенных чисел. Вы можете выбрать определенный массив и определенную позицию в этом массиве, после чего Казак Ус сообщит Вам значение этого элемента. Обратите внимание, что Вы можете делать эту операцию много раз, не обязательно над одним и тем же массивом. Поскольку Козак --- очень занятой человек, он позволил вам задать ему не более $Q$ вопросов Вам следует узнать $k$-ый наибольший элемент в объединении массивов. \InputFile Первая строка содержит пять целых чисел $|a|$, $|b|$, $|c|$, $k$, $g$ ($0 \leq |a|, |b|, |c| \leq 10^6$, $1 \leq k \leq |a| + |b| + |c|$). Гарантируется, что все упомянутые числа находятся в границах $[1, 10^9]$. Число $g$ ($0 \leq g \leq 9$) --- номер группы тестов (см. Оценивание). \Interaction Сначала следует считать пять целых чисел $|a|$, $|b|$, $|c|$, $k$, $g$. Чтобы сделать запрос, выведите <<1 $r$ $m$>>. Здесь $r$~--- номер массива: если $r=1$, то операция будет осуществлена над массивом $a$, если $r=2$, то над массивом $b$, если $r=3$, то над $c$. А $m$~--- номер позиции в этом массиве. Если Вы, например, выполняете операцию над массивом $a$, то, чтобы получить первый элемент, нужно чтобы $m=1$, а чтобы получить последний, нужно чтобы $m=|a|$. Пример запроса <<1 3 10>>~--- получить $10$-ое число в массиве $c$. После вывода запроса не забудьте вывести символ новой строки и сбросить буфер вывода. В противном случае вы получите вердикт \t{Исчерпан лимит времени}. Для сброса буфера используйте: \begin{itemize} \item \t{fflush(stdout)} або \t{cout.flush()} в C++; \item \t{System.out.flush()} в Java; \item \t{flush(output)} в Pascal; \item \t{stdout.flush()} в Python; \end{itemize} смотрите документацию для других языков. Обратите внимание, что если Ваш запрос недействителен (лимит запросов превышен или запрос не удовлетворяет ограничением), интерактор выведет <<-1>> и прекратит работу. Если вы считаете <<-1>>, то немедленно завершите программу, чтобы получить вердикт \t{Неверный ответ} вместо произвольного вердикта. Когда Вы найдете ответ $x$, выведите <<2 $x$>>. \Scoring Пусть $n = \max(|a|, |b|, |c|)$, а также $m = \max(a_i, b_j, c_t)$. \begin{enumerate} \item ($6$ баллов): $n \leq 10, Q = 150$; \item ($4$ балла): $|b|=0, |c|=0, m \leq 2, Q = 150$; \item ($9$ баллов): $|c|=0, m \leq 2, Q = 125$; \item ($10$ баллов): $m \leq 2, Q = 125$; \item ($13$ баллов): $|c|=0, Q = 1000$; \item ($13$ баллов): $|c|=0, Q = 125$; \item ($17$ баллов): $Q = 1000$; \item ($21$ балл): $Q = 125$; \item ($7$ баллов): $Q = 65$. \end{enumerate} \Example \begin{example} \exmp{3 3 3 2 0 2 5 5 2 6 6 6 7 10}{ 1 1 1 1 1 2 1 1 3 1 2 1 1 2 2 1 2 3 1 3 1 1 3 2 1 3 3 2 2 } \end{example}
Time limit 3 seconds
Memory limit 256 MiB
Author Daniel Ostashev
Source 2021 Ukrainian Olympiad in Informatics, Stage IV, Round I