Editing 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 <code>1 1 1 7 7 3 4 4 4 7 7</code> avem:

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

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

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

# se extrage un platou la alegere;
# 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: <code>2 2 5 0 5 8 8 8 4 9 9 9 0 0 2 2 8</code> extragem platoul <code>2 2</code> format din elementele aflate în penultima şi antepenultima poziţie şi obţinem şirul: <code>2 2 5 0 5 8 8 8 4 9 9 9 0 0 8</code>

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

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

# 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ă.
# 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 <code>input.txt</code>conține:

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

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code>va conține:

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

= Restricții și precizări =

* <code>1 ≤ n ≤ 1.000.000</code>

== 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:

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

== 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:

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

Valoarea cea mai mare din care este format unul dintre aceste platouri este <code>8</code>.

== 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>