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

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


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

Iepuraşul Coconaş vrea să ajungă la grădina cu morcovi. Pentru aceasta el trebuie să traverseze prin salturi o zonă cu proprietăţi speciale. Zona este formată din N căsuţe numerotate de la 1 la N, dispuse una după cealaltă, iar fiecare căsuţă conţine un număr natural ce reprezintă cantitatea de energie necesară iepuraşului pentru a sări într-o altă căsuţă.
Iepuraşul pleacă dintr-o anumită căsuţă şi se deplasează, de la stânga la dreapta, spre grădina cu morcovi după următoarele reguli:
• numărul înscris în căsuţa în care se află iepuraşul reprezintă numărul de căsuţe peste care el va sări;
• dacă numărul înscris în căsuţa în care se află iepuraşul este număr prim, atunci energia lui se dublează şi va sări peste un număr dublu de căsuţe;
• numărarea căsuţelor peste care va sări se face de la stânga la dreapta şi începe cu căsuţa imediat următoare.
Astfel, dacă iepuraşul se află în căsuţa a treia şi numărul înscris în această căsuţă este 5, iepuraşul va ajunge în căsuţa cu numărul de ordine 13 (13=3+2*5).
• dacă iepuraşul ajunge într-o căsuţă care conţine numărul 0, el rămâne acolo pentru că nu mai are energie să sară mai departe, altfel el continuă să sară după regulile descrise mai sus;
• iepuraşul ajunge la grădina cu morcovi dacă ultimul salt pe care îl face depăşeşte căsuţa N.

Cerinţă

Scrieţi un program care citeşte trei numere naturale P, N şi K iar apoi N numere naturale şi determină:
1) dacă iepuraşul poate ajunge sau nu, la grădina cu morcovi pornind din căsuţa K şi numărul de salturi pe care le face iepuraşul pornind din căsuţa K;
2) căsuţa de pornire a iepuraşului, astfel încât drumul parcurs de el să traverseze un număr maxim de căsuţe. Pentru a determina numărul de căsuţe se vor lua în calcul: căsuţa de pornire, toate căsuţele peste care iepuraşul a sărit şi toate căsuţele în care a ajuns în urma salturilor. Iepuraşul poate porni din oricare căsuţă. În cazul în care există două sau mai multe căsuţe de pornire care conduc la acelaşi număr maxim de căsuţe traversate se va lua în considerare căsuţa cu numărul de ordine cel mai mic.

Date de intrare

Fişierul de intrare iepuras1.in conţine pe prima linie un număr natural P. Pentru toate testele de intrare, numărul P poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie a fişierului iepuras.in se găsesc, în această ordine, numerele naturale N şi K, separate prin câte un spaţiu. Pe a treia linie se găsesc N numere naturale separate prin câte un spaţiu, reprezentând valorile din fiecare căsuţă în ordine de la 1 la N.

Date de ieşire

Dacă valoarea lui P este 1, se va rezolva numai punctul 1) din cerinţe. În acest caz, fişierul de ieşire iepuras1.out va conţine pe prima linie cuvântul DA în cazul în care iepuraşul a ajuns în grădina cu morcovi , respectiv cuvântul NU în caz contrar, iar pe a doua linie va conţine un număr natural reprezentând numărul de salturi pe care le face iepuraşul pornind din căsuţa K.
Dacă valoarea lui P este 2, se va rezolva numai punctul 2) din cerinţe. În acest caz, fişierul de ieşire iepuras1.out va conţine pe prima linie două numere naturale separate printr-un spaţiu reprezentând, în ordine, căsuţa de pornire şi numărul maxim de căsuţe determinat, iar pe a doua linie, un şir de numere naturale separate prin câte un spaţiu reprezentând numerele din căsuţele în care iepuraşul nu s-a aflat sau nu a sărit pe parcursul drumului, de la stânga la dreapta, începând cu căsuţa 1. Dacă numărul maxim de căsuţe traversate este chiar N linia a doua nu va conţine niciun număr.

Restricţii

• 1 ≤ N ≤ 7000
• 1 ≤ K ≤ N
• 0 ≤ numerele conţinute în căsuţe ≤ 100
• Pentru rezolvarea corectă a primei cerinţe se acordă 30 de puncte, pentru rezolvarea corectă a celei de a doua cerinţe se acordă 70 de puncte.

Exemple

iepuras1.iniepuras1.outExplicaţii
1 14 3 2 3 4 0 1 1 2 1 4 0 0 2 1 1 NU 9 P = 1, pentru acest test, se rezolva cerinţa 1).
Iepuraşul pleacă din căsuţa 3, sare în căsuţa cu numărul de ordine 7 şi mai departe, în căsuţa cu numărul de ordine 11, unde găsind numărul 0 se opreşte.
2 14 3 2 3 6 0 1 1 2 1 4 0 0 2 3 1 2 13 2 6 0 1 1 2 0 0 2 1 P = 2, pentru acest test, se rezolvă cerinţa 2).
Pentru a traversa un număr maxim de căsuţe, iepuraşul pleacă din căsuţa cu numărul de ordine 2 şi sare, pe rând, în căsuţele cu numerele de ordine 8, 9, 13, şi apoi în grădină, traversând astfel 13 căsuţe (de la căsuţa 2 la căsuţa 14).
Iepuraşul nu s-a aflat sau nu a sărit în căsuţele de pe poziţiile 1, 3, 4, 5, 6, 7, 10, 11, 12 şi 14.

autor: Prof. Sanda Junea
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, lightbot, teren1, inventie
De acelaşi autor: rafturi, patrat1
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, lightbot, castig
surse trimise | ajutor