Sim-4-1 | catelusi

This was the problem page during the contest. Access the current page here.
Time limit: 0.3s Memory limit: 256MB Input: Output:

Daniel și-a deschis o "grădiniță" și are în grija sa NN cățeluși de diferite vârste pe care i-a dresat să stea într-un cerc. Cățelușii sunt numerotați de 11 la NN și pentru fiecare cățeluș ii cu valori între 11 și NN cunoaștem vârsta sa ViV_i. Fiecare cățeluș ii îi are ca vecini pe cățelușii i1i − 1 și i+1i + 1. Dat fiind că ei stau într-un cerc, cățeii de pe pozițiile 11 și NN sunt de asemenea vecini.

Daniel trebuie să țină cățelușii concentrați pentru câteva ore și decide să se joace un joc cu ei. Pentru jocul ales de Daniel e necesar să împartă cățelușii în echipe de câte KK cățeluși puși în ordine consecutivă în cerc. Deoarece cățeii au vârste diferite ea vrea să aleagă un KK astfel încât echipele să fie cât mai echilibrate. Pentru a evalua cât de echilibrată va fi împărțirea în echipe de câte KK el calculează un coeficient de echilibru astfel:

  • Alege toate subsecvențele de câte KK cățeluși consecutivi
  • Alege minimul din fiecare subsecvență
  • Alege maximul dintre aceste minime, coeficientul de echilibru

El ar vrea ca respectivul coeficient să fie cât mai mare, dar să rămână mai mic strict decât o valoare SS dată.

Ajutați-l pe Daniel să găsească numărul KK pentru care se obține cel mai mare coeficient de echilibru mai mic strict decât SS. Dacă există mai multe valori KK pentru care se obține rezultatul ideal, se va afișa cel mai mare dintre ele.

Cerință

Dându-se NN, SS și vârstele cățelușilor, să se afle cel mai mare număr KK pentru care se obține coeficientul de echilibru ideal.

Date de intrare

Pe prima linie se află două numere naturale NN și SS, separate printr-un spațiu, cu semnificația din enunț. Pe a doua linie a fișierului de intrare se află NN numere naturale separate prin câte un spațiu, V1,V2,,VNV_1, V_2, \dots, V_N, reprezentând vârstele cățelușilor în ordinea în care sunt așezați în cerc.

Date de ieșire

Se va afișa un singur număr natural, KK, rezultatul cerut.

Restricții și precizări

  • 1N1 000 0001 \leq N \leq 1 \ 000 \ 000
  • 1KN1 \leq K \leq N
  • 0S,Vi1 000 000 0000 \leq S, V_i \leq 1 \ 000 \ 000 \ 000
  • Se garantează că există cel puțin un cățelus, cu vârsta mai mică decât SS.
    # Punctaj Restricții
    1 26 1N1 0001 \leq N \leq 1 \ 000
    2 31 1N100 0001 \leq N \leq 100 \ 000
    3 43 Fără restricții suplimentare

Exemplul 1

stdin

5 3
1 2 3 4 5

stdout

4

Explicație

Luăm toate subsecvențele de cățeluși de lungime 44:
1 2 3 41 \ 2 \ 3 \ 4 \rightarrow minimul este 11
2 3 4 52 \ 3 \ 4 \ 5 \rightarrow minimul este 22
3 4 5 13 \ 4 \ 5 \ 1 \rightarrow minimul este 11
4 5 1 24 \ 5 \ 1 \ 2 \rightarrow minimul este 11
5 1 2 35 \ 1 \ 2 \ 3 \rightarrow minimul este 11
Valoarea maximă a unui minim este de 22 ce este mai mic strict decât 33.

Exemplul 2

stdin

4 3
2 4 2 4

stdout

4

Explicație

Luăm toate subsecvențele de cățeluși de lungime 44:
2 4 2 42 \ 4 \ 2 \ 4 \rightarrow minimul este 22
4 2 4 24 \ 2 \ 4 \ 2 \rightarrow minimul este 22
2 4 2 42 \ 4 \ 2 \ 4 \rightarrow minimul este 22
4 2 4 24 \ 2 \ 4 \ 2 \rightarrow minimul este 22
Maximul este 22 ce este mai mic strict decât 33.
Luăm toate subsecvențele de lungime 33:
2 4 22 \ 4 \ 2 \rightarrow minimul este 22
4 2 44 \ 2 \ 4 \rightarrow minimul este 22
2 4 22 \ 4 \ 2 \rightarrow minimul este 22
4 2 44 \ 2 \ 4 \rightarrow minimul este 22
Maximul este 22 ce este mai mic strict decât 33.
Luăm toate subsecvențele de lungime 22:
2 42 \ 4 \rightarrow minimul este 22
4 24 \ 2 \rightarrow minimul este 22
2 42 \ 4 \rightarrow minimul este 22
4 24 \ 2 \rightarrow minimul este 22
Maximul este 22 ce este mai mic strict decât 33.
Remarcăm că obținem valoarea ideală pentru KK egal 22, 33 și 44, dar deoarece în caz de egalitate alegem KK cel mai mare, răspunsul final este 44.

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