O vrecku čo zradilo ostatné | Korešpondenčný seminár z programovania

Ú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.

Sada	1	2	3	4
Maximálny počet otázok	100	99	20	1

Sada

Maximálny počet otázok

100

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.

Priame prehľadávnie

Najjednoduchším riešením, ktoré by nám mohlo napadnúť, je postupne vždy z jediného vrecka zobrať jednu mincu a odvážiť ju. Potom podľa hodnoty na váhe hneď vieme, či sú mince v danom vrecku falošné alebo nie.

Takéto riešenie však v najhoršom prípade potrebuje $n$ vážení, čo postačuje na vyriešenie prvej sady.

Môžeme si ale všimnúť, že keď už sme odvážili všetky vrecká okrem jedného a všetky obsahovali pravé mince, tak falošné musia byt v tom poslednom. Takto si vieme ušetriť jedno váženie a tak vyriešiť aj druhú sadu.

def odvaz(vahy_minci):
    assert len(vahy_minci)==n
    print("?", *vahy_minci, flush=True)
    result = int(input())
    return result

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

n = int(input())

for i in range(n):
    vahy_minci = [0]*n
    vahy_minci[i] = 1 
    vysledok = odvaz(vahy_minci)

    if vysledok == 55:
        odpovedaj(i+1)

Zaujímavejšie prístupy

Tretia sada sa dá vyriešiť riešeniami založenými na rôznych dekompozíciách.

Jednou možnosťou je rozdeliť si vrecúška na niekoľko skupín (napríklad mať skupiny po 10 vrecúškach) a najprv zistiť, v ktorej skupine sa falošné vrecko nachádza. Následne si individuálne prejdeme len vrecká v tejto skupine a zistíme, ktoré konkrétne vrecko obsahuje falošné mince.

Takéto riešenie nám zaberie $S + K$ vážení, kde $S$ je počet skupín a $K$ je maximálny počet vreciek v skupine. To by sa dalo ešte optimalizovať rovnakým trikom ako v minulej sekcii, ale na vyriešenie tretej sady to nebolo potrebné.

def odvaz(vahy_minci):
    assert len(vahy_minci)==n
    print("?", *vahy_minci, flush=True)
    result = int(input())
    return result

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

n = int(input())

# Rozdelime si mince do vreciek po najviac desiatich

skupiny = [[]]

for i in range(n):
    if len(skupiny[-1]) == 10:
        # ak je posledna skupina plna, vytvorime novu
        skupiny.append([])
    skupiny[-1].append(i)

spravna_skupina = None

# Hladame skupinu, v ktorej je falosna minca
for skupina in skupiny:
    vahy_minci = [0]*n
    for index in skupina:
        vahy_minci[index] = 1

    vysledok = odvaz(vahy_minci)
    vaha_vsetky_prave = len(skupina) * 50

    if vysledok != vaha_vsetky_prave:
        spravna_skupina = skupina
        break

# Hladame falosnu mincu v spravnej skupine
for index in spravna_skupina:
    vahy_minci = [0]*n
    vahy_minci[index] = 1

    vysledok = odvaz(vahy_minci)
    if vysledok != 50:
        odpovedaj(index + 1)

Táto myšlienka sa dá rozšíriť aj na viacero úrovní – skupinu, kde sa nachádza falošné vrecko môžeme opäť rozdeliť na menšie skupiny a takto pokračovať, až kým nám neostane len jediné vrecko. Ak vám táto myšlienka príde zaujímavá, mohli by vás zaujať Intervaláče.

V každom prípade vám však takéto riešenia s poslednou sadou vstupov nepomôžu pretože…

Optimálne riešenie

Na vyriešenie celej úlohy však stačí použiť iba jediné váženie.

Po chvíľke rozmýšľania si uvedomíme, že tu nám už nebude stačiť z každého vrecka brať maximálne jednu mincu. V skutočnosti si môžeme všimnúť silnejšiu vec – z každej dvojice vreciek musíme zobrať iný počet mincí. Ak by sme tak nespravili a náhodou by sa stalo, že by v jednom z nich boli falošné mince, nemali by sme šancu určiť, ktoré z nich to je.

Predpokladajme teda, že sme z každého vrecka zobrali iný počet mincí, z prvého sme ich zobrali $a_1$, z druhého $a_2$, …, z $n$-tého $a_n$. Keby boli všetky mince pravé, váha by ukázala $P=50 \cdot (a_1 + a_2 + … + a_n)$ gramov. Ale ak bolo $i$-te vrecko falošné, váha nám v skutočnosti ukázala hodnotu $W=50 \cdot (a_1 + a_2 + … + a_{i-1} + a_{i+1} + … + a_n) + 55 \cdot a_i$. To znamená, že rozdiel medzi skutočnou a očakávanou hmotnosťou je $W - P = 5 \cdot a_i$. $W$ ale poznáme z váženia a $P$ vieme jednoducho spočítať. Teda potom vieme, že $a_i = \frac{W - P}{5}$, a keďže sme z každého vrecka zobrali iný počet mincí, vieme jednoznačne určiť, ktoré vrecko je falošné.

Prakticky je najjednoduchšie zobrať z $i$-teho vrecka $i$ mincí, potom je $a_i = i$ a teda $i = \frac{W - P}{5}$.

def odvaz(vahy_minci):
    assert len(vahy_minci)==n
    print("?", *vahy_minci, flush=True)
    result = int(input())
    return result

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

n = int(input())

while True:
    # Z i-teho vrecka vezmeme i minci
    pocty_minci = list(range(1, n+1))

    #  Ak by boli vsetky prave, tak by vazili presne p gramov
    p = sum(pocty_minci) * 50

    w = odvaz(pocty_minci)

    odpovedaj((w-p)//5)

Aktuálne

Ostatné