La copa xocolata P10080

0.62 La rivalitat entre UPC-1 i UPC-2 ha arribat a nivells èpics. Segons UPC-2, ells van guanyar vuit entrenaments i UPC-1 només quatre, però ningú recorda exactament quants cops va guanyar cada equip. Encara que guanyar entrenaments no serveixi per a res, a la pràctica dona el que s’anomena Aura, que és el recurs més important en un SWERC.

Ja a Lisboa, la practice session durava dues hores, no tenia cap valor competitiu i només servia per provar l’entorn de programació. Això, òbviament, no va impedir que UPC-2 es posés a speedrunejar problemes mentre tots els altres equips testejaven el teclat, aconseguint quedar primers de 150 equips. Durant les hores posteriors, en Bernat i en Manuel van repetir que “la copa xocolata no val res” per baixar-li els fums a UPC-2. (Enveja? Ves a saber.) Però guanyar la practice session sí que serveix, perquè duplica l’Aura de l’equip guanyador.

0.38

Abans dels entrenaments, UPC-1 tenia Aura $A$ i UPC-2 tenia Aura $B$. Després,

• Cada vegada que UPC-1 guanyava un entrenament, UPC-1 sumava Aura $x$, i UPC-2 restava Aura $y$.

• Cada vegada que UPC-2 guanyava un entrenament, UPC-2 sumava Aura $x$, i UPC-1 restava Aura $y$.

Es van fer $n$ entrenaments. Amb $n$ caràcters es codifica el resultat de cadascun: ‘1’ si el va guanyar UPC-1, ‘2’ si el va guanyar UPC-2, i ‘?’ si ningú recorda qui el va guanyar.

Quin és el mínim nombre d’entrenaments amb ‘?’ que va haver de guanyar UPC-1 per acabar estrictament amb més Aura que UPC-2 al final del SWERC? Recordeu que UPC-2 va guanyar la copa xocolata, i que per tant la seva Aura es va duplicar al final de tot.

Entrada

L’entrada consisteix en diversos casos, cadascun amb els cinc enters $A$, $B$, $x$, $y$ i $n$, seguits d’una paraula amb els $n$ caràcters que codifiquen els resultats dels entrenaments. Suposeu que els cinc nombres estan entre 1 i $10^4$.

Sortida

Per a cada cas, escriviu el mínim nombre d’entrenaments amb ‘?’ que va haver de guanyar UPC-1 per acabar al final amb estrictament més Aura que UPC-2. Si és impossible, escriviu “estan ben cuinats”.