Задача №114482. Как узнать свои баллы
Это интерактивная задача.
Петя участвует в контесте, где участники узнают результаты тестирования каждой из своих посылок только после конца соревнования.
В контесте, в котором участвовал Петя, \(n\) задач, пронумерованных от \(1\) до \(n\). По каждой из этих задач он сдал решение. После соревнования он очень волновался — ведь от того, сколько баллов он получил по каждой задаче, зависит то, какое место он занял. К сожалению, результаты станут известны только на награждении, до которого еще несколько часов.
Петя решил заранее узнать свой результат — выпытать у жюри количество баллов, полученное им по каждой задаче, задавая им странные вопросы. Пусть Петя получил \(c_1, c_2, \ldots, c_n\) баллов по задачам \(1, 2, \ldots, n\), соответственно. Петя не знает эти числа, но хочет их узнать.
Петя называет номера трех различных задач контеста и просит жюри сказать ему сумму минимального и максимального количества баллов, полученных им по этим трем задачам. К счастью, жюри, ничего не подозревая, отвечает на его странные вопросы. Более формально, если Петя спросит про три задачи \(i\), \(j\), \(k\), то в ответ ему скажут число \(min(c_i, c_j, c_k) + max(c_i, c_j, c_k)\).
Помогите Пете отгадать числа \(c_1, c_2, \ldots, c_n\), задав не более \(4n\) вопросов членам жюри.
Сначала на вход вашей программе подается одно целое число \(n\) — количество задач, которое было в контесте (\(5 \leq n \leq 1000\)).
После этого ваша программа может делать запросы: чему равна сумма минимального и максимального баллов, полученных Петей по задачам \(i\), \(j\), \(k\). Для этого нужно вывести в выходной поток в отдельной строке « \(?\) \(i\) \(j\) \(k\) » (\(1 \leq i, j, k \leq n\), \(i \neq j\), \(j \neq k\), \(i \neq k\)). В ответ на запрос во входном потоке будет записано одно целое число \(min(c_i, c_j, c_k) + max(c_i, c_j, c_k)\).
Если ваша программа сделает более \(4n\) запросов или задаст некорректный запрос, она получит вердикт « Wrong Answer ».
Определив баллы Пети, ваша программа должна вывести в выходной поток « \(!\) \(c_1\) \(c_2\) \(\ldots\) \(c_n\) » — баллы, полученные Петей по каждой из задач.
Гарантируется, что баллы, полученные Петей по каждой из задач, удовлетворяют ограничениям \(0 \leq c_i \leq 10^9\) для всех \(1 \leq i \leq n\). Также все числа \(c_i\) фиксированы заранее и не будут меняться в ходе тестирования вашей программы.
5
2
4
4
1
? 1 2 3
? 1 3 5
? 5 4 3
? 1 4 2
! 1 0 2 1 3
После каждого действия вашей программы выводите символ перевода строки. Если вы используете « writeln » в Паскале, « cout <\( \)< ... <\( \)< endl » в C\(++\), « System.out.println » в Java или « print » в Python, сброс потока вывода у вас происходит автоматически, дополнительно делать « flush » не oбязательно. Если вы используете другой способ вывода, рекомендуется делать « flush », но все равно обязательно требуется выводить символ перевода строки.
5 1 0 2 1 3
10