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 \le x \le n$. Podeu ajudar la Ivet?

Entrada

L’entrada conté diverses partides. Cada partida comença amb una $n$ entre 1 i $10^9$. 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 \le 30$, com l’exemple d’entrada 1.

• Cas B:   Casos de tot tipus.