Fișierul intrare/ieșire | secv.in, secv.out | Sursă | ONI 2016 baraj gimnaziu |
---|---|---|---|
Autor | Dana Lica | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 0.5 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Secv (baraj gimnaziu)
Notă: punctarea acestei probleme este ușor modificată față de original, din limitări ale NerdArena. Ultimele cinci teste sunt duplicat, pentru a obține împărțirea corectă de 40/60p între cele două cerințe.
Se consideră două numerele naturale K și S și un șir de N numere naturale a1, a2, ..., aN. O secvență de lungime K este un subșir format din K elemente aflate pe poziții consecutive în șir: ai, ai+1, .., ai+k-1. Parcurgând șirul de la stânga la dreapta, începând cu primul element, se elimină prima secvență de lungime K, cu suma elementelor strict mai mare decât numărul S. În urma ștergerii șirul va avea N-K elemente: a1, a2, ..., aN-K. Operația de ștergere continuă după aceleași reguli până când nu mai există secvențe care pot fi eliminate.
Cerințe
Să se scrie un program care citind numerele N, K , S și cele N elemente din șir rezolvă cerințele:
- Determină numărul secvențelor care se vor elimina respectând condiția din enunț.
- Considerând că în șirul citit nu sunt posibile eliminări de secvențe conform condiției din enunț, programul determină numărul de elemente ai din șir cu proprietatea următoare: ștergerea lui ai conduce la obținerea unui șir în care se mai poate elimina cel puțin o secvență de K elemente cu sumă strict mai mare ca S.
Date de intrare
Fișierul de intrare secv.in conține pe prima linie un număr natural P; numărul P poate avea doar valoarea 1 sau valoarea 2. A doua linie conține, în această ordine, separate prin câte un spațiu, numerele N, K și S. A treia linie conține, în ordine elementele șirului, despărțite prin câte un spațiu.
Date de ieșire
Dacă valoarea lui P este 1, se va rezolva numai cerinta 1. În acest caz, fișierul de ieșire secv.out va conține pe prima linie un număr natural reprezentând numărul secvențelor eliminate. Dacă valoarea lui P este 2, se va rezolva numai cerinta 2. În acest caz, fișierul de ieșire secv.out va conține pe prima linie un număr natural reprezentând numărul elementelor din șir care au proprietatea că ștergerea fiecăruia în parte ar genera un șir în care se mai pot elimina cel puțin o secvență de K elemente cu sumă strict mai mare ca S.
Restricții
- 0 < N ≤ 1 000 000 și K ≤ N
- 0 < S ≤ 1 000 000 000
- 0 ≤ a1, a2, ..., aN ≤ 1 000
- Pentru rezolvarea corectă a primei cerințe se acordă 40 de puncte iar pentru rezolvarea corectă a celei de a doua cerințe se acordă 60 de puncte
Exemplu
secv.in | secv.out | Explicație |
---|---|---|
1 14 3 7 1 2 1 3 1 4 5 2 1 4 1 8 2 3 |
3 |
Prima secvență de sumă strict mai mare decât 7 începe de pe poziția 4 și este formată din elementele 3 1 4; după eliminarea ei șirul devine: 1 2 1 5 2 1 4 1 8 2 3. A doua secvență ce va fi ștearsă începe de pe poziția 2 și este formată din 2 1 5; după eliminarea ei șirul devine: 1 2 1 4 1 8 2 3 A treia secvență ce va fi ștearsă începe de pe poziția 4 și este formată din elementele 4 1 8; după eliminarea ei șirul devine: 1 2 1 2 3 și nu mai conține nici o secvență de 3 elemente alăturate de sumă mai mare decât 7 |
2 9 7 18 3 3 2 1 3 3 3 3 1 |
2 |
Două elemente au această proprietate. Dacă eliminăm elementul al treilea, de valoare 2, se poate obține șirul 3 3 1 3 3 3 3 1 care conține o secvență de 7 elemente de sumă strict mai mare ca 18, începând cu elementul de pe poziția 1. Dacă eliminăm elementul al patrulea, de valoare 1, se poate obține șirul 3 3 2 3 3 3 3 1 care conține o secvență de 7 elemente de sumă strict mai mare ca 18, începând cu elementul de pe poziția 1. |