Fişierul intrare/ieşire:case1.in, case1.outSursăONI 2009 clasa a 5-a
AutorCristina IordaicheAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.5 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Case1 (clasa a 5-a)

În pădurea cu alune aveau case n pitici numerotaţi de la 1 la n, vine veveriţa şi spune ”Vreau să stau şi eu aici!”.
Cele n căsuţe sunt aşezate în linie şi fiecare căsuţă este identificată printr-o plăcuţă pe care este scris un număr. Prima căsuţă este a piticului numerotat cu 1 şi are plăcuţa cu numărul 1, cea de-a doua căsuţa este a celui de-al doilea pitic şi are plăcuţa cu numărul 2, şi aşa mai departe, ultima căsuţă este cea a piticului cu numărul n şi are plăcuţa cu numărul n. Auzind că veveriţa vrea să intre într-o căsuţă niciun pitic nu vrea să o primească în căsuţa lui.

Într-o zi, după ce piticii au plecat de acasă, veveriţa de supărare a luat plăcuţele de pe căsuţe, le-a amestecat şi a pus câte o plăcuţă în fiecare căsuţă. La întoarcere, piticii văd că nu mai au plăcuţe pe case şi fiecare dintre ei trebuie să-şi recupereze plăcuţa propriei case. Fiecare pitic intră în casa lui, găseşte plăcuţa de acolo şi se deplasează în căsuţa cu numărul de ordine egal cu numărul scris pe plăcuţa găsită. Apoi, continuă în acelaşi mod cu noua plăcuţă găsită, până când piticul descoperă plăcuţa cu numărul casei lui. În timpul căutării unei plăcuţe, se poate întâmpla ca un pitic, din cauza plăcuţei găsite în acel moment să meargă de la căsuţa la care se află la una din căsuţele aflate în stânga ei. Aceasta se consideră o întoarcere pe parcursul căutării.

Cerinţă

Să se scrie un program care să determine:

a) câţi dintre pitici îşi găsesc propriile plăcuţe în casele lor;
b) care este cel mai mare număr de căsuţe vizitate de un pitic până când îşi găseşte propria plăcuţă (se numără începând cu căsuţa proprie până la căsuţa care conţine plăcuţa căutată, inclusiv aceasta)
c) piticul care a vizitat cele mai multe căsuţe şi a făcut cele mai puţine întoarceri. Dacă există mai mulţi pitici care să îndeplinească aceste condiţii, să se afişeze piticul cu numărul cel mai mic.

Date de intrare

Din fişierul de intrare case1.in se citesc de pe prima linie numărul n care reprezintă numărul căsuţelor. De pe cea de-a doua linie, se citesc n numere, despărţite prin câte un spaţiu, care reprezintă numerele plăcuţelor puse de veveriţă în căsuţe.

Date de ieşire

În fişierul de ieşire case1.out se va scrie pe prima linie un singur număr care reprezintă câţi dintre pitici îşi găsesc propriile plăcuţe în casele lor. Pe a doua linie se va scrie un singur număr natural reprezentând cel mai mare număr de căsuţe vizitate de un pitic până când îşi găseşte propria plăcuţă. Pe cea de-a treia linie se va scrie un singur număr care reprezintă piticul care a vizitat cele mai multe căsuţe şi a făcut cele mai puţine întoarceri; dacă există mai mulţi pitici care să îndeplinească aceste condiţii, se afişează piticul cu numărul cel mai mic.

Restricţii

  • 1 ≤ n ≤ 10000

Exemplu

case1.incase1.outExplicaţii
4
3 2 4 1
1
3
1
Sunt 4 căsuţe:
 
 
După ce veveriţa ascunde plăcuţele în căsuţe:
 
 
Plăcuţe găsite de piticul 1: 3-4-1, a vizitat 3 căsuţe, întoarceri 0
Plăcuţe găsite de piticul 2: 2, a vizitat o căsuţă, întoarceri 0
Plăcuţe găsite de piticul 3: 4-1-3, a vizitat 3 căsuţe, întoarceri 1
Plăcuţe găsite de piticul 4: 1-3-4, a vizitat 3 căsuţe, întoarceri 1
Cel mai mare număr de căsuţe vizitate de un pitic este 3. Dintre piticii
1, 3 şi 4 care au vizitat exact 3 căsuţe, doar piticul 1 are 0 întoarceri.
Trebuie sa te autentifici pentru a trimite solutii. Click aici