secv

Time limit: 0.2s
Memory limit: 16MB
Input: secv.in
Output: secv.out

Se consideră două numerele naturale KK și SS și un șir de NN numere naturale a1a_1, a2a_2, \dots, aNa_N. O secvenţă de lungime KK este un subşir format din KK elemente aflate pe poziţii consecutive în şir: aia_i, ai+1a_{i+1}, \dots, ai+k1a_{i+k-1}. Parcurgând șirul de la stânga la dreapta, începând cu primul element, se elimină prima secvență de lungime KK, cu suma elementelor strict mai mare decât numărul SS. În urma ștergerii șirul va avea NKN - K elemente: a1a_1, a2a_2, \dots, aNKa_{N-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 NN, KK, SS și cele NN 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 aia_i din șir cu proprietatea următoare: ștergerea lui aia_i conduce la obținerea unui șir în care se mai poate elimina cel puțin o secvență de KK elemente cu sumă strict mai mare ca SS.

Date de intrare

Fișierul de intrare secv.in conţine pe prima linie un număr natural PP; numărul PP poate avea doar valoarea 11 sau valoarea 22. A doua linie conține, în această ordine, separate prin câte un spațiu, numerele NN, KK și SS. 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 PP este 11, se va rezolva numai cerinta 11. Î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 PP este 22, se va rezolva numai cerinta 22. Î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 KK elemente cu sumă strict mai mare ca SS.

Restricții și precizări

  • 0<KN1 000 0000 < K \leq N \leq 1 \ 000 \ 000
  • 0<S1 000 000 0000 < S \leq 1 \ 000 \ 000 \ 000
  • 0a1,a2,,aN1 0000 \leq a_1, a_2, \dots, a_N \leq 1 \ 000
  • Pentru rezolvarea corectă a primei cerinţe se acordă 4040 de puncte iar pentru rezolvarea corectă a celei de a doua cerințe se acordă 6060 de puncte

Exemplul 1

secv.in

1
14 3 7
1 2 1 3 1 4 5 2 1 4 1 8 2 3

secv.out

3

Explicație

Prima secvență de sumă strict mai mare decât 77 începe de pe poziția 44 și este formată din elementele 3 1 43 \ 1 \ 4; după eliminarea ei șirul devine:
11, 22, 11, 55, 22, 11, 44, 11, 88, 22, 33.
A doua secvență ce va fi ștearsă începe de pe poziția 22 și este formată din 2 1 52 \ 1 \ 5; după eliminarea ei șirul devine: 11, 22, 11, 44, 11, 88, 22, 33
A treia secvență ce va fi ștearsă începe de pe poziția 44 și este formată din elementele 4 1 84 \ 1 \ 8; după eliminarea ei șirul devine: 11, 22, 11, 22, 33 și nu mai conține nici o secvență de 33 elemente alăturate de sumă mai mare decât 77.

Exemplul 2

secv.in

2
9 7 18
3 3 2 1 3 3 3 3 1

secv.out

2

Explicație

Două elemente au această proprietate. Dacă eliminăm elementul al treilea, de valoare 22, se poate obține șirul 33, 33, 11, 33, 33, 33, 33, 11 care conține o secvență de 77 elemente de sumă strict mai mare ca 1818, începând cu elementul de pe poziția 11.
Dacă eliminăm elementul al patrulea, de valoare 11, se poate obține șirul 33, 33, 22, 33, 33, 33, 33, 11 care conține o secvență de 77 elemente de sumă strict mai mare ca 1818, începând cu elementul de pe poziția 11.

Problem info

ID: 1086

Editor: stefdasca

Author:

Source: ONI 2016 Baraj Juniori: Problema 3

Tags:

ONI 2016 Baraj Juniori

Log in or sign up to be able to send submissions!