Magazin

Time limit: 0.1s Memory limit: 128MB Input: magazin.in Output: magazin.out

În inima bazarului plin de viață din Istanbul, Emir pășește într-un magazin mic, dar plin de mister, ascuns între tarabele cu mirodenii și obiecte de artizanat. Magazinul este cunoscut printre localnici ca locul unde se găsesc cele mai valoroase pietre prețioase, însă prețul lor se află într-un joc complicat.

Proprietarul magazinului, un bătrân înțelept, îl provoacă pe Emir cu o enigmă:

În magazinul meu am un șir de pietre prețioase, de valori nu neapărat distincte. Dacă vei găsi în acest șir toate perechile de pietre care însumate dau exact suma SS, vei primi o mică recompensă.

Dar adevărata provocare este și mai interesantă:

Sau, dacă vei găsi cel mai scurt șir continuu de pietre care însumează suma SS, și vei alege cel mai din stânga astfel de șir, îți voi dezvălui o cale secretă spre o comoară ascunsă în bazar.

Emir trebuie să decidă cum să rezolve provocarea magazinului: să numere toate perechile sau să găsească cel mai scurt șir cu suma SS.

Ajută-l pe Emir, dacă:

  • C=1C=1, numără toate perechile distincte de pietre care însumate dau SS;
  • C=2C=2, găsește cel mai scurt interval continuu de pietre cu suma SS și, dacă există mai multe, alege-l pe cel mai din stânga. Dacă nu există niciun astfel de interval, afișează 1-1.

Cerință

Se dau două numere naturale NN și SS și un șir AA de NN numere naturale. Să se rezolve una din următoarele cerințe:

  • C=1C=1 să se afișeze numărul perechilor de numere de pe poziții distincte care însumate dau SS;
  • C=2C=2 să se afișeze intervalul de lungime minimă, iar dacă sunt mai multe să se afișeze cel mai din stânga, astfel încât suma elementelor intervalului să fie SS, iar dacă nu există un astfel de interval, să se afișeze 1-1.

Date de intrare

Fișierul de intrare magazin.in conține:

  • pe prima linie, trei numere naturale, CC, NN și SS, cu semnificația din enunț;
  • pe a doua linie NN numere naturale, reprezentând elementele șirului AA;

Numerele aflate pe aceeași linie a fişierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire magazin.out răspunsul la cerință.

Restricții și precizări

  • C{1,2}C \in \left\{1, 2\right\};
  • 1N1061 \leq N \leq 10^{6};
  • 0S10180 \leq S \leq 10^{18};
  • 0Ai109,1iN0 \leq A_{i} \leq 10^{9}, 1 \leq i \leq N;
  • Pentru C=1C=1 vectorul se garantează că va fi mereu sortat crescător.
# Punctaj Restricții
1 30 C=1,N10 000C=1, N \leq 10 \ 000
2 10 C=1,N300 000C=1, N \leq 300 \ 000
3 10 C=1C=1, fără restricții suplimentare
4 30 C=2,N10 000C=2, N \leq 10 \ 000
5 10 C=2,N300 000C=2, N \leq 300 \ 000
6 10 C=2C=2, fără restricții suplimentare

Exemplul 1

magazin.in

1 3 3
1 2 3

magazin.out

1

Explicație

După cum se vede, 1+2=31 + 2 = 3.

Exemplul 2

magazin.in

2 3 6
1 2 3

magazin.out

1 3

Explicație

După cum se vede, 1+2+3=61 + 2 + 3 = 6.

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