07/04/2025 05:21:26

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1296. Central Element

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

This is an interactive problem.

There is a permutation

$P$ of numbers 1 through

$n$ (

$3\ ≤\ n\ ≤\ 200$ ), not known to you,

$P\ =\ ⟨P_1,\ P_2,\ …,\ P_n⟩$ . You can ask the following type of questions: Given three distinct positions

$i$ ,

$j$ and

$k$ , which of

$P_i$ ,

$P_j$ and

$P_k$ is central? Element is central if it is neither minimal nor maximal.

For example, if the permutation is

$⟨2,\ 1,\ 4,\ 3⟩$ , and you ask about positions 1, 2, and 3, you receive 2, because 2 is the central element of the set

${P_1,\ P_2,\ P_3}\ =\ {2,\ 1,\ 4}$ . Note that you don't get the information at which position among 1, 2, and 3 it is located.

Your task is to find the permutation

$P$ . Actually, for each permutation

$P$ there is a set

$S(P)$ of permutations that cannot be distinguished from

$P$ using the allowed questions. You must find any permutation from this set.

Interaction and Output

You must write procedure solve with one integer parameter

$n$ , the size of the permutation.

void solve(int n); // C/C++

procedure solve(n:integer);

The procedure solve must call the function central with three integer arguments that you ask a question about and that return a response, and so on until you know the permutation

$P$ up to

$S(P)$ . You can ask at most

$2\ 000$ questions.

Once you know the answer, output the permutation

$P$ . After printing this line your program must exit.

28/11/2009	Занятие 6 (задачи NEERC 2009) (C)
21/11/2013	Занятие 10 для продолжающих (B)