1. O vrecku čo zradilo ostatné

Vedec mal zvláštny deň. Od rána rozmýšľal, ako oklamať nudu — a tak sa rozhodol, že si odváži svoje poklady. V skrini mal n vreciek mincí, ktoré vyzerali úplne rovnako. No jedna vec ho trápila: v jednom vrecku sa ukrývali falošné mince, o niečo ťažšie ako ostatné.

Namiesto toho, aby vážil každé vrecko zvlášť, dostal geniálny nápad. Z každého vrecka odobral nejaký počet mincí, až mal na váhe poriadnu hromadu. Potom sa postavil k váhe, pozrel na číslo a s úsmevom vyhlásil: „Už viem, ktoré vrecko je falošné!“

Úloha

Máme \(n\) vreciek mincí. Práve v jednom vrecku sú všetky mince falošné (každá falošná minca váži \(55\) gramov), vo všetkých ostatných vreckách sú mince reálne (každá reálna minca váži \(50\) gramov). Pred vážením si môžeme z každého z vreciek odobrať ľubovoľný počet mincí a zložiť ich do jednej spoločnej kôpky. Kôpku potom zvážime na váhe, ktorá nám povie celkovú hmotnosť odobratých mincí v gramoch.

Vrecká sú magické a tak je v každom nekonečne veľa mincí.

Tvojou úlohou je na základe čo najmenej vážení určiť index vrecka, v ktorom sú falošné mince.

Formát vstupu a výstupu

Táto úloha je interaktívna. To znamená, že váš program komunikuje s testovačom. Testovaču pokladáte otázky a on vám na ne bude odpovedať.

Na prvom riadku vstupu je jedno celé číslo \(n\) (\(1 \leq n \leq 100\)) — počet vreciek s mincami. Následne môžete pokladať otázky vo forme ? i1 i2 i3 ... in, kde i1, i2, …, in sú počty mincí odobraných z jednotlivých vreciek. Z každého vrecka môžete odobrať \(0\) až \(10^9\) mincí. Ako odpoveď na každú otázku testovač vypíše jeden riadok s jedným celým číslom - súčtom hmotností všetkých odobraných mincí v gramoch.

Keď už budete vedieť odpoveď, vypíšte riadok vo formáte ! x, kde x je index vrecka s falošnými mincami (\(1 \leq x \leq n\)). Následne by mal váš program skončiť.

Vstupy sú tvorené viacerými sadami líšiacimi sa v maximálnom počte povolených otázok. Za každú sadu môžete získať \(2\) body.

Keďže ide o interaktívnu úlohu, po vypísaní každej otázky je nutné flushovať výstupný buffer. V jazyku C++ to dosiahneme napríklad použitím std::endl namiesto '\n', v Pythone parametrom printu : print("text na vypísanie", flush=True).

Ak si tým stále nie ste istí, môžete len doplniť tento template, ktorý celú komunikáciu rieši za vás:

# Vrati sucet vah v kopke. Z vrecka i dame do kopky pocty_minci[i] minci
def odvaz(pocty_minci):
    assert len(pocty_minci) == n
    print("?", *pocty_minci, flush=True)
    result = int(input())
    return result

def odpovedaj(index):
    print("!", index, flush=True)
    exit(0)

n = int(input())

# V nizsie uvedenom priklade je n = 5
if n == 5:
    # V nizsie uvdedenom priklade dostaneme ako odpoved_1 cislo 250
    odpoved_1 = odvaz([1, 2, 2, 0, 0])

    # Podobne v tomto pripade dostaneme odpoved 385
    odpoved_2 = odvaz([0, 0, 0, 7, 0])

    # Program odpovie 4 a skonci
    odpovedaj(4)

else:
    odpovedaj(42)

Príklad komunikácie

5
? 1 2 2 0 0
250
? 0 0 0 7 0
385
! 4

Máme \(5\) vreciek. V prvom meraní zoberieme jednu mincu z prvého vrecka, po dvoch z druhého a tretieho a žiadne z ostatných. Váha nám povie, že dokopy vážia \(250\)g. \(5\) reálnych mincí váži \(1 \cdot 50 + 2 \cdot 50 + 2 \cdot 50 = 250\)g, takže falošné mince nemôžu byť v prvom, druhom ani treťom vrecku. V druhom meraní zoberieme \(7\) mincí zo štvrtého vrecka, ktoré vážia \(385\)g. \(7\) reálnych mincí by vážilo \(7 \cdot 50 = 350\)g, takže štvrté vrecko musí obsahovať falošné mince.