.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » case

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
case


Timp maxim de execuţie / test:
0.2s
Memorie totala disponibilă / stivă:
2MB / 1MB

Î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 case.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 case.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

Exemple

case.incase.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-2, 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.

autor: Prof. Cristina Iordaiche
propunător: Prof. Emanuela Cerchez
Liceul de Informatică ″Grigore Moisil″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2009: bile, checkin, numere, text, reactii, volei, magic2, sirag, taste, tetris, origami, rafturi, joc2, br, reinvent, perspic, tir, patrate2, nrcuv2, matrice, patrate1, pikachu, taxe, cartonas, desen2
De acelaşi autor: melci, ceas, sotron, piramida, vraji, pinochio, zar, maraton1, taburet, medalion, cladiri2, remi1, imprimanta, praslea
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Despre structura repetitiva: cifre1, super, schimb, jeton, descfib, taxe, romane, mobile, cuburi3, tzigla, morse, powerpuff, multimi, ucif, tabel, ocr, numere7, cifre2, piramida, vraji, reforma, cartonas, cabina, desen2, exponent, cifre3, concurs3, joc13, reactivi, vanatoare, submult, paranteze, tort, copaci1, ogorul, puncte3, efort, muzeu, smith, biliard, palc, prod3, fazanr, cadouri, bursa, meteo, prodmax, zar, tren4, lego, maraton1, cluburi, domino1, jump, alo, cifra1, case1, brazi, greiere, divizori, pitag, porumb, secv9, divk, rachete, pin, sumacifre, aritm, psp, triplu, triunghi3, cmmdcsecv, ssmax, ape, furnici1, domino2, acoperire1, ore, pegals, b2k, sumdivprod, subsecvmax, dale, bancomat, sume4, alice, porumb1, albine2, culegere, stele1, medalion, cifreco, meteo1, unupatru, xyz, vistiernic, chibrituri, bete1, greieri, interviu, prieten, prize, conturi, numere12, martisoare, piramide, pagini, punctul, tablita, pavare1, ordine, covor1, speciale, echer, numere13
surse trimise | ajutor