Fişierul intrare/ieşire: | atlantis.in, atlantis.out | Sursă | Infotehnium 2019 clasa a 6-a avansati |
Autor | Cristian Francu | Adăugată de | |
Timp execuţie pe test | 0.5 sec | Limită de memorie | 32768 kbytes |
Scorul tău | N/A | Dificultate |
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ă:
- 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)
- numerele (indicii) munţilor în ordinea în care ei se scufundă
- 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.in | atlantis.out | Explicaţ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ţă) |