Fişierul intrare/ieşire:secv.in, secv.outSursăONI 2016 baraj gimnaziu
AutorDana LicaAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Secv (baraj gimnaziu)

Notă: punctarea acestei probleme este uşor modificată faţă de original, din limitări ale varena. 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.insecv.outExplicaţ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 sa te autentifici pentru a trimite solutii. Click aici