1655 - Platou

Cerința

Fiind dat un şir de numere, denumim secvenţă a acestuia o parte dintre termenii şirului luaţi de pe poziţii consecutive. Denumim platou al acestui şir o secvenţă formată din valori identice. Lungimea unui platou este egală cu numărul de elemente care îl formează.

De exemplu, în şirul de numere 1 1 1 7 7 3 4 4 4 7 7 avem:

• platourile 1 1 1 şi 4 4 4 ambele având lungimea 3;
• platourile 7 7 (cel care începe în poziţia a patra) şi 7 7 (cel care începe pe poziţia a zecea), ambele având lungimea 2;
• platoul 3 care are lungimea 1.

În schimb nu avem platoul 7 7 7 7 deoarece cele patru elemente egale cu 7 nu sunt pe poziţii consecutive!

Se dă un şir de n numere. Fiecare dintre aceste numere aparţine intervalului [0,1000000]. Asupra acestui şir se pot efectua o singură dată următoarele două operaţiuni în această ordine:

1. se extrage un platou la alegere;
2. se inserează platoul extras la pasul anterior într-o poziţie la alegere din şirul rezultat după extragere.

De exemplu, dacă avem următorul şir inițial: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 2 2 8 extragem platoul 2 2 format din elementele aflate în penultima şi antepenultima poziţie şi obţinem şirul: 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8

În şirul rezultat inserăm platoul 2 2 (pe care l-am extras în pasul anterior) în poziţia a doua şi obţinem şirul: 2 2 2 2 5 0 5 8 8 8 4 9 9 9 0 0 8

Să se scrie un program care pentru un şir dat determină:

1. Lungimea maximă a unui platou din şirul dat iniţial precum şi valoarea cea mai mare a elementelor care formează un platou de lungime maximă.
2. Lungimea maximă a unui platou care poate să apară în şir în urma efectuării celor două operaţiuni precum şi valoarea cea mai mare a elementelor care ar putea forma un astfel de platou.

Date de intrare

Fișierul de intrare input.txtconține:

• pe prima linie un număr natural V care poate avea valoarea 1 sau valoarea 2;
• pe a doua linie un număr natual n;
• pe a treia linie un şir de n numere naturale separate prin câte un spaţiu, reprezentând elementele şirului dat. Fiecare dintre aceste numere aparţine intervalului [0,1.000.000].

Date de ieșire

Fișierul de ieșire output.txtva conține:

• dacă V=1, atunci pe această linie se vor scrie cele două numere care reprezintă răspunsul la prima cerinţă.
• dacă V=2, atunci pe această linie se vor scrie cele două numere care reprezintă răspunsul la a doua cerinţă.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000

Exemplul 1

input.txt:

1

16

2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2

output.txt:

3 9

Explicație:

V=1, deci se rezolvă NUMAI prima cerinţă. Lungimea maximă a unui platou din şirul dat este 3. Sunt două astfel de platouri: 8 8 8 şi 9 9 9. Valoarea cea mai mare din care este format unul dintre aceste platouri este 9.

Exemplul 2

input.txt:

2

16

2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2

output.txt:

4 8

Explicație:

V=2, deci se rezolvă NUMAI a doua cerinţă. În urma executării celor două operațiuni pot să apară platouri de lungime maximă 4 în două moduri: 2 2 2 2 respectiv 8 8 8 8.

Valoarea cea mai mare din care este format unul dintre aceste platouri este 8.

Exemplul 3

input.txt:

2

999999999999999

2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2

Output:

Input-ul nu convine conditiilor

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verificare(n):

   if not(1<=n<=1000000):
       print("Input-ul nu convine conditiilor")
       exit()

with open("input.txt", "r") as fin, open("output.txt", "w") as fout:

   v = int(fin.readline())
   n = int(fin.readline())
   verificare(n)

   l=list(map(int, fin.readline().split()))

   if v == 1:
       x = l[0]
       lcrt = 1
       lmax = 1
       valmax = x

       for i in range(0,n - 1):
           y = l[i]
           if x == y:
               lcrt += 1
           else:
               lcrt = 1

           if lcrt > lmax:
               lmax = lcrt
               valmax = x
           elif lmax == lcrt and x > valmax:
               valmax = x

           x = y

       fout.write(f"{lmax} {valmax}\n")
   else:
       x = l[0]
       lcrt = 1
       max1 = [0] * 1000002
       max2 = [0] * 1000002

       for i in range(0,n - 1):
           y = l[i]
           if x == y:
               lcrt += 1
           else:
               if lcrt >= max1[x]:
                   max2[x] = max1[x]
                   max1[x] = lcrt
               elif lcrt > max2[x]:
                   max2[x] = lcrt
               lcrt = 1

           x = y

       if lcrt >= max1[x]:
           max2[x] = max1[x]
           max1[x] = lcrt
       elif lcrt > max2[x]:
           max2[x] = lcrt

       rezmax = 0
       valmax = 0
       for i in range(1000001, -1, -1):
           if max1[i] + max2[i] > rezmax:
               rezmax = max1[i] + max2[i]
               valmax = i

       fout.write(f"{rezmax} {valmax}\n")

</syntaxhighlight>