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


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.
Source: ACM ICPC NEERC, 2009 (modified)