Fișierul intrare/ieșire secv.in, secv.out Sursă ONI 2016 baraj gimnaziu
Autor Dana Lica Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.5 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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:

  1. Determină numărul secvențelor care se vor elimina respectând condiția din enunț.
  2. 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 KN
  • 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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii