Se consideră un şir x₁, x₂, …, x_n de n numere naturale distincte, două câte două. Pentru o secvenţă de k numere (x_p, x_p+1, ..., x_p+k-1), care începe cu numărul de pe poziţia p din şirul dat, definim gradul său ca fiind numărul de numere din secvenţă, care rămân pe aceleaşi poziţii după ordonarea crescătoare a secvenţei. De exemplu, pentru n=7 şi şirul format din numerele: 1, 5, 7, 4, 6, 2, 9, secvenţa formată din numerele 7, 4, 6, 2 (corespunzătoare lui p=3 şi k=4) are gradul egal cu 2 deoarece, după ordonarea crescătoare a numerelor din secvenţă, aceasta devine 2, 4, 6, 7, numerele 4 şi 6 rămânând pe aceleaşi poziţii.

Cerinţă[edit]

Scrieţi un program care citeşte numerele n, k, x₁, x₂, …, x_n, cu semnificaţia din enunţ, şi apoi determină:

a) gradul întregului şir de numere;

b) poziţia primului element din prima secvenţă de lungime k ce are gradul maxim, precum şi gradul acestei secvenţe.

Date de intrare[edit]

Fișierul de intrare grad1.in conține pe prima linie numerele n şi k, separate printr-un spaţiu, iar pe linia următoare n numere naturale distincte x₁, x₂, …, x_n, corespunzătoare şirului de numere, separate prin câte un spaţiu.

Date de ieșire[edit]

Fișierul de ieșire grad1.out va conține pe prima linie un număr natural reprezentând gradul întregului şir de numere, iar pe următoarea linie două numere naturale, separate printr-un singur spaţiu, primul număr reprezentând poziţia primului element din prima secvenţă de lungime k ce are grad maxim şi cel de-al doilea număr reprezentând gradul acestei secvenţe.

Restricții și precizări[edit]

0 < n < 10001
0 < k < n+1
Numerele din şir sunt numere naturale strict mai mici decât 32000.
O secvenţă de numere din şir reprezintă o succesiune de numere din acel şir, aflate pe poziţii consecutive.
Gradul întregului şir de numere este egal cu gradul secvenţei de n numere care începe cu numărul de pe poziţia 1 şi conţine toate cele n numere din şir.
Pentru rezolvarea corectă a subpunctului a) se obţine 40% din punctaj.
Pentru rezolvarea corectă a subpunctului b) se obţine 60% din punctaj.

Exemplu:[edit]

grad1.in

7 4
1 5 7 4 6 2 9

grad1.out

3
3 2

Explicație[edit]

După ordonare, şirul 1 5 7 4 6 2 9 devine 1 2 4 5 6 7 9, pe aceleaşi poziţii rămân 1, 6 şi 9, deci gradul întregului şir este 3.

Avem patru secvenţe cu câte 4 elemente:

1 5 7 4, care are gradul 1
5 7 4 6, care are gradul 0
7 4 6 2, care are primul număr pe poziţia 3 și gradul 2.
4 6 2 9, care are gradul 1.

Încărcare soluție[edit]

Lipește codul aici[edit]

<syntaxhighlight lang="python" line="1"> def read_input(filename):

   with open(filename, 'r') as fin:
       n, k = map(int, fin.readline().split())
       x = [0] + [int(num) for num in fin.readline().split()]
   return n, k, x

def sort_subarray(y, n):

   sorted = False
   while not sorted:
       sorted = True
       for i in range(1, n):
           if y[i] > y[i + 1]:
               y[i], y[i + 1] = y[i + 1], y[i]
               sorted = False

def main():

   n, k, x = read_input("grad1.in")
   y = x.copy()
   sort_subarray(y, n)
   g = sum(1 for i in range(1, n + 1) if x[i] == y[i])
   
   with open("grad1.out", 'w') as fout:
       fout.write(f"{g}\n")
       
       y = x[1:k+1]
       sort_subarray(y, k)
       gmax = sum(1 for i in range(1, k + 1) if x[i] == y[i])
       pmax = 1
       
       for i in range(2, n - k + 2):
           j = 1
           while j <= k and y[j] != x[i - 1]:
               j += 1
           if j <= k:
               y[j] = x[i + k - 1]
               while j > 1 and y[j - 1] > y[j]:
                   y[j], y[j - 1] = y[j - 1], y[j]
                   j -= 1
               while j < k and y[j] > y[j + 1]:
                   y[j], y[j + 1] = y[j + 1], y[j]
                   j += 1
           
           gr = sum(1 for j in range(1, k + 1) if y[j] == x[i + j - 1])
           if gr > gmax:
               gmax = gr
               pmax = i
       
       fout.write(f"{pmax} {gmax}")

if __name__ == "__main__":

   main()

</syntaxhighlight>