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

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


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

În acest an evenimentul ”Hour of Code” a înregistrat un număr record de participanţi din ţara noastră. În cadrul acestui eveniment una dintre cele mai accesate aplicaţii a fost Lightbot, care a permis elevilor să-şi testeze abilităţile de programare.
Aplicaţia Lightbot are N nivele, numerotate consecutiv de la 1 la N, în ordinea strict crescătoare a complexităţii lor. Lightbot a permis fiecărui participant să înceapă cu orice nivel strict mai mic decât N-1 şi să sară peste un singur nivel, fără a finaliza codul, trecând la nivelul următor celui sărit. La finalizarea cu succes a codului corespunzător nivelului curent, participantul este promovat la nivelul imediat următor. Fiecare participant a început scrierea codurilor la un nivel P şi a sărit peste un nivel L (P < L < P + K), finalizând K nivele memorate ca o succesiune de numere naturale de forma P, P+1,..., L-1, L+1,..., P+K. Succesiunile de nivele finalizate de participanţi au fost memorate în fişierul lightbot.in. Succesiunile corespunzătoare participanţilor nu se intercalează în fişier.

Cerinţă

Scrieţi un program care citeşte succesiunile corespunzătoare nivelelor finalizate de participanţii care au jucat Lightbot şi determină:
1. numărul total de participanţi;
2. numărul celui mai dificil nivel care a fost rezolvat de un număr maxim de participanţi;
3. pentru fiecare participant, numărul nivelului sărit de acesta.

Date de intrare

Fişierul de intrare lightbot.in conţine pe prima linie una dintre valorile 1 , 2 sau 3, reprezentând cerinţa 1 dacă se cere determinarea numărului total de participanţi, cerinţa 2 dacă se cere determinarea numărului celui mai dificil nivel care a fost rezolvat de un număr maxim de participanţi, respectiv cerinţa 3, dacă se cere determinarea, pentru fiecare participant, a numărului nivelului sărit de acesta.
A doua linie a fişierului conţine numărul natural N de nivele corespunzător aplicaţiei Lightbot, iar pe a treia linie, succesiunile de numere naturale nenule corespunzătoare nivelelor finalizate de participanţi, separate două câte două prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire lightbot.out va conţine pe prima linie un număr natural M, reprezentând numărul total de participanţi dacă cerinţa a fost 1, un număr natural reprezentând numărul celui mai dificil nivel care a fost rezolvat de un număr maxim de participanţi, dacă cerinţa a fost 2, respectiv, o secvenţă de M numere naturale separate prin câte un spaţiu ce reprezintă nivele sărite de participanţi în ordinea succesiunilor memorate în fişier, dacă cerinţa a fost 3.

Restricţii

• 3 ≤ N ≤ 200000.
• 1 ≤ X ≤ N, pentru orice număr X memorat pe a treia linie a fişierului lightbot.in.
• 1 ≤ P < L < P + K ≤ N, pentru orice succesiune de K nivele finalizate, corespunzătoare unui participant, care a început scrierea codurilor la nivelul P şi a sărit peste nivelul L.
• O secvenţă de valori consecutive aparţine unui singur participant.
• A treia linie a fişierului de intrare conţine cel mult 400000 de numere.
• Pentru rezolvarea corectă a cerinţei 1 se obţine 20% din punctaj.
• Pentru rezolvarea corectă a cerinţei 2 se obţine 40% din punctaj.
• Pentru rezolvarea corectă a cerinţei 3 se obţine 40% din punctaj.

Exemple

lightbot.inlightbot.outExplicaţii
1 10 1 2 4 2 4 6 7 9 3 Sunt trei participanţi, care au finalizat nivelele: 1 2 4 (primul), 2 4 (al doilea) şi 6 7 9 (al treilea).
2 10 1 2 4 2 4 6 7 9 4 Nivele 2 şi 4 au fost finalizate de câte doi participanţi, cel mai greu fiind nivelul 4.
3 10 1 2 4 2 4 6 7 9 3 3 8 Primul participant a sărit nivelul 3, al doilea nivelul 3, iar al treilea nivelul 8.

autor: Prof. Florentina Ungureanu
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONIG 2015: cript, scadere, tv1, nebuni, spioni1, ssk, magic7, restaurare, sort2dist, echer, teren1, iepuras1, inventie
De acelaşi autor: ferma1, echer
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, case, 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, iepuras1, castig
surse trimise | ajutor