Медіанне божевілля
Це інтерактивна задача.
Загадана деяка перестановка чисел від до , де парне. Ви можете задавати запити наступного вигляду:
Для даного набору різних індексів непарної довжини , ви можете дізнатись таке число , що є медіаною елементів .
Відомо, що . Вгадайте перестановку за не більше ніж запитів.
Гарантується, що перестановка зафіксована перед початком взаємодії. Іншими словами, інтерактор не адаптивний.
Нагадаємо, що медіана непарної кількості чисел визначається наступним чином:
Нехай — це ці числа в порядку зростання (де — кількість чисел). Тоді медіаною є число .
Qarşılıqlı təsir
Почніть взаємодію, зчитавши одне ціле число (, парне) — довжину перестановки.
Щоб задати питання, необхідно вивести в одному рядку спочатку символ «?
», потім ціле число , а потім цілих чисел (, , непарне, всі попарно різні) — індекси, для яких необхідно знайти медіану.
У відповідь програма журі виведе таке число , що є медіаною елементів .
Коли ви визначили перестановку, то виведіть спочатку символ «!
», а потім чисел . Після цього ваша програма має завершити роботу.
Після кожного запиту і виводу відповіді не забудьте вивести перехід рядка і скинути буфер виводу. Для скидання буферу використовуйте:
fflush(stdout)
чиcout.flush()
в C++;System.out.flush()
в Java;flush(output)
в Pascal;stdout.flush()
в Python;
Nümunələr
Qeyd
В прикладі загадана перестановка .
Перший запит в прикладі — хочемо дізнатись медіану елементів , що дорівнюють відповідно. Медіана цих чисел — , тобто , тому інтерактор відповідає числом .
Другий запит в прикладі — хочемо дізнатись медіану елементів , що дорівнюють відповідно. Медіана цих чисел — , тобто , тому інтерактор відповідає числом .
Третій запит в прикладі — хочемо дізнатись медіану елементів , що дорівнюють відповідно. Медіана цих чисел — , тобто , тому інтерактор відповідає числом .
Четвертий запит в прикладі — хочемо дізнатись медіану елементів , що дорівнюють відповідно. Медіана цих чисел — , тобто , тому інтерактор відповідає числом .