Fişierul intrare/ieşire:	joc10.in, joc10.out	Sursă	ONI 2009 clasa a 9-a
Autor	Adriana Simulescu	Adăugată de	Pripoae Teodor Anton •toni2007
Timp execuţie pe test	0.075 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Joc10

Pentru un concurs de design de jocuri, Gigel vrea să construiască un joc. La joc participă n concurenţi numerotaţi de la 1 la n. Fiecare concurent are la dispoziţie câte un şir de m încăperi, numerotate de la 1 la m. Scopul jocului este de a găsi o comoară ascunsă în una din aceste încăperi. Fiecare încăpere conţine un cod, număr natural, fie egal cu 0, fie având cel puţin 2 cifre. Ultima cifră indică numărul de etape de penalizare, adică numărul de etape în care concurentul nu are voie să părăsească încăperea. Numărul obţinut prin eliminarea ultimei cifre a codului indică numărul încăperii în care se va deplasa acesta la următoarea etapă sau la expirarea penalizării.

Există două excepţii de la regula de definire a codului: numărul 9999 codifică o încăpere conţinând o comoară, iar numărul 0 o încăpere conţinând o capcana.

În etapa 1 fiecare jucător intră în încăperea 1 din şirul său de încăperi. În funcţie de codul găsit în încăpere sunt posibile următoarele situaţii:

• codul găsit este 9999 ceea ce înseamnă că jucătorul este câştigător şi jocul se încheie la finalul acestei etape;
• codul găsit este 0 ceea ce duce la eliminarea sa din joc;
• pentru celelalte coduri, după efectuarea etapelor de penalizare, jucătorul efectuează o deplasare în încăperea indicată de cod. De exemplu la întâlnirea codul 157, după efectuarea celor 7 etape de penalizare jucătorul se va deplasa în camera 15.

Trecerea de la o etapă la alta se realizează simultan pentru toţi concurenţii.

Cerinţă

Fiind dat numărul n de concurenţi, numărul m de încăperi alocate fiecărui concurent, şi codurile din cele n×m încăperi să se determine câştigătorul jocului, numărul încăperii în care a găsit comoara, numărul de etape parcurse până când câştigătorul găseşte comoara precum şi numărul de concurenţi eliminaţi din joc până la etapa respectivă (inclusiv).

Date de intrare

Prima linie a fişierului de intrare joc10.in conţine două numere naturale n şi m, separate printr-un spaţiu, reprezentând numărul concurenţilor, respectiv numărul încăperilor.
Următoarele n linii conţin câte m numere naturale, separate prin câte un spaţiu, reprezentând codurile din fiecare încăpere.

Date de ieşire

Prima linie a fişierului de ieşire joc10.out va conţine patru numere naturale separate prin câte un spaţiu, reprezentând indicele câştigătorului, numărul încăperii unde a găsit comoara, numărul etapei în care a câştigat şi respectiv numărul de concurenţi eliminaţi din joc.

Restricţii

• 1 ≤ n ≤ 400
• 1 ≤ m ≤ 900
• Pentru toate testele de intrare se garantează că există exact un câştigător.

Exemplu

Explicaţie

Câştigă jucătorul al 2-lea, după 7 etape, iar încăperea în care a găsit comoara este încăperea 5. În cele 7 etape a fost eliminat un singur concurent şi anume primul concurent.
Încăperile prin care trece jucătorul câştigător până la final sunt: 1->3->6->2->8->5

Cum se trimit solutii?