Més o menys? P17499

L’Anna i la Ivet han reinventat el joc consistent a endevinar un nombre fent preguntes. Primer, l’Anna pensa un nombre x entre 1 i n, i li diu la n a la Ivet. Després la Ivet fa tantes preguntes com vulgui, cada vegada dient un nombre y. Si x > y, l’Anna respondrà “mes”, si x < y, respondrà “menys”, i si x = y, dirà “si”.

En principi el joc acabaria aquí, però han decidit que poden seguir fent preguntes després d’haver encertat, o acabar abans d’haver encertat; total, només es tracta de passar l’estona. Tanmateix, la Ivet comença a sospitar que l’Anna li ha fet trampa, és a dir, que les respostes que li ha donat no són consistents amb cap 1 ≤ x ≤ n. Podeu ajudar la Ivet?

Entrada

L’entrada conté diverses partides. Cada partida comença amb una n entre 1 i 10⁹. Segueixen entre 1 i 1000 preguntes, totes nombres entre 1 i n, cadascuna amb la seva resposta. Un 0 marca el final de cada partida.

Sortida

Per a cada partida, si és segur que l’Anna ha fet trampa, escriviu “trampa!”. Altrament, si hi ha exactament una x entre 1 i n consistent amb totes les respostes, escriviu-la. Altrament, escriviu “ok”.

Puntuació

• Cas A:  ‍ Casos amb n ≤ 30, com l’exemple d’entrada 1.  ‍70% Punts ‍

• Cas B:  ‍ Casos de tot tipus.  ‍30% Punts ‍