Fişierul intrare/ieşire:atlantis.in, atlantis.outSursăInfotehnium 2019 clasa a 6-a avansati
AutorCristian FrancuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.5 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Atlantis (clasa a 6-a)

Atlantis este o insulă digitală formată din n munţi înşiruiţi de la stânga la dreapta. Munţii au formă de cuburi lipite unul de altul. Ei au toţi aceeaşi lăţime, dar înălţimi diferite între ele, cunoscute, exprimate în metri de la nivelul apei. Munţii sunt numerotaţi de la 1 la n. Unii locuitori au propus, pentru modernizare, schimbarea numelui insulei în Minecraftis, iar alţii în Legolandis, dar nici una din denumiri nu a fost aprobată de OSIM.

Deoarece i-au supărat pe zei (gurile rele spun că l-au supărat de fapt pe Platon), insula a început să se scufunde! Ea se scufundă foarte repede, cu un metru la fiecare minut. Regele insulei vrea să salveze cât mai mulţi locuitori şi de aceea are nevoie de informaţii vitale.

Cerinţe

Scrieţi un program care, citind un număr natural nenul n, un şir de n numere reprezentând înălţimile munţilor şi numărul k de minute determină:

  1. câţi munţi se vor afla sub apă după k minute (un munte este sub apă dacă apa a depăşit înălţimea muntelui)
  2. numerele (indicii) munţilor în ordinea în care ei se scufundă
  3. pentru fiecare munte de la stânga la dreapta, al câtelea este el în ordinea de scufundare a munţilor.

Date de intrare

Fişierul de intrare atlantis.in conţine pe prima linie un număr C. Pentru toate testele, C poate lua numai valorile 1, 2 sau 3. Pe a doua linie se află numerele n şi k, iar pe a treia linie cele n numere naturale despărţite prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire atlantis.out va conţine:

  • dacă C=1, va conţine un singur număr natural reprezentând numărul de munţi aflaţi sub apă după k minute
  • dacă C=2, va conţine numerele (indicii) munţilor în ordinea lor de scufundare sub apă, separate prin spaţii
  • dacă C=3, va conţine pentru fiecare munte, de la stânga la dreapta, ordinea lui de scufundare, cele n numere fiind afişate cu spaţii între ele

Restricţii

  • 1 ≤ n ≤ 100 000
  • 1 ≤ numerele din şir ≤ 100 000
  • 0 ≤ k ≤ 2 miliarde
  • Munţii au înălţimi diferite între ele
  • Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, pentru rezolvarea corectă a celei de a doua cerinţe se acordă 40 de puncte, iar pentru rezolvarea corectă a celei de a treia cerinţe se acordă 40 de puncte.
  • Dimensiunea maximă a sursei: 15KB

Exemple

atlantis.inatlantis.outExplicaţie
1
10 8
13 9 3 12 1 4 10 8 16 2
4
Explicaţie: După 8 minute 4 munţi vor fi acoperiţi cu apă, cei cu înălţimile
de 1, 2, 3, respectiv 4
(C fiind 1, se rezolvă doar prima cerinţă)
2
10 8
13 9 3 12 1 4 10 8 16 2
5 10 3 6 8 2 7 4 1 9
Explicaţie: Munţii se scufundă în astfel: întâi al cincilea munte (înălţime 1),
apoi cel cu numărul 10 (înălţime 2), apoi cel cu numărul 3 (înălţime 3), apoi cel
cu numărul 6 (înălţime 4) şi aşa mai departe. (C fiind 2, se rezolvă doar a doua cerinţă)
3
10 8
13 9 3 12 1 4 10 8 16 2
9 6 3 8 1 4 7 5 10 2
Explicaţie: Primul munte (înălţime 13) se va scufunda al nouălea, al doilea
munte (înălţime 9) se va scufunda al şaselea, al treilea munte (înălţime 3) se
va scufunda al treilea, şi aşa mai departe. (C fiind 3, se rezolvă doar a treia cerinţă)
Trebuie sa te autentifici pentru a trimite solutii. Click aici