Miawinator: Pagină nouă: = 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 `...`


2024-01-04T23:19:17Z
Pagină nouă: = 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>...
New page
= 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>
1655 - Platou - Revision history
