Задача №114784. Угадай массив
Это интерактивная задача. Ваша программа будет взаимодействовать с программой жюри, используя стандартный ввод и вывод.
Алиса и Боб решили сыграть в игру под названием «Угадай массив». Правила игры очень простые: Алиса загадала массив целых чисел размера \(n\), а Бобу нужно угадать этот массив, сделав не больше \(n\) запросов о сумме на отрезке.
За один ход Боб может сделать к Алисе запрос одного из двух типов:
- « ? l r » — узнать сумму чисел на отрезке массива с \(l\)-го по \(r\)-й элемент включительно;
- « ! » — сообщить Алисе, что он готов дать ответ. После этого запроса Алиса ожидает от Боба \(n\) целых чисел — загаданный массив.
На каждый запрос первого типа, Алиса говорит Бобу сумму чисел на запрошенном отрезке. Но чтобы отгадывать было сложнее, после каждого запроса Алиса делает один отрезок запрещенным . В дальнейших запросах Боб не может запрашивать сумму чисел на запрещенных отрезках.
Помогите Бобу угадать загаданный массив, сделав не более \(n\) запросов первого типа.
В первой строке ввода дано целое число \(n\) — размер загаданного массива (\(1 \leqslant n \leqslant 10^4\)). Гарантируется, что все числа в массиве по модулю не превосходят \(10^{9}\).
Далее запускается протокол взаимодействия с программой жюри — интерактором.
Интерактор ожидает от вашей программы запросы двух типов: « ? l r » или « ! », где \(l\), \(r\) — целые числа — границы отрезка, на котором вы хотите узнать сумму (\(1 \leqslant l \leqslant r \leqslant n\)). После каждого запроса должен следовать перевод строки. При несоблюдении вашей программой формата запросов, ваше решение может получить произвольный вердикт (отличный от OK ).
После запроса первого типа необходимо считать со стандартного ввода три целых числа \(s\), \(l_b\) и \(r_b\) — сумму чисел на запрошенном отрезке \(s\) и границы нового запрещенного отрезка \([l_b, r_b]\), на котором запрашивать сумму больше нельзя (\(|s| \leqslant 10^{18}\); \(1 \leqslant l_b \leqslant r_b \leqslant n\)).
Запрос второго типа означает, что ваша программа готова дать ответ на задачу. После запроса второго типа необходимо вывести \(n\) целых чисел — загаданный массив.
Обратите внимание, ваша программа может сделать не более \(n\) запросов первого типа. При превышении данного ограничения, а также при попытке узнать сумму на запрещенном ранее отрезке, интерактор выведет « -1 -1 -1 » и завершится с вердиктом WA . Чтобы не получить вердикт TL или IL , считав из ввода значения « -1 -1 -1 », ваша программа должна завершить свою работу с нулевым кодом возврата.
3 0 1 2 3
3