Editing 2073 - PlatouK v2

Sursa: [https://www.pbinfo.ro/probleme/2073/platouk-v2 - PlatouK v2]
----
== Cerinţa ==
Fiind dat un șir de numere, numim 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!

Asupra unui şir se poate efectua următoarea operaţiune:

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: 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 citește un șir de n numere naturale din intervalul [0,10000] și un număr k și determină:

lungimea maximă a unui platou care poate să apară în şir în urma efectuării operaţiunii de mai sus de maxim k ori
elementul din care este format platoul obținut după cele k operațiuni

== Date de intrare ==
Programul va citi:

* pe prima linie un număr natural k;
* pe a doua linie un număr natural n;
* pe a treia linie un şir de n numere naturale separate prin câte un spaţiu.
* pe a patra linie p, care reprezinta cerința; p poate fi 1 sau 2

== Date de ieșire == 
Dacă datele sunt introduse corect, pe ecran se va afișa: 
'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.


== Restricţii şi precizări ==
* 1 ≤ n ≤ 1000000
* 1 ≤ k ≤ 100
* pentru cerința 1 – 50% din punctaj
* pentru cerința 2 – 50% din punctaj
* dacă sunt mai multe platouri de lungime maxima se va afișa cel mai mare considera cel format din valoarea cea mai mare
toate testele au soluție

== Exemplu 1 ==
; Intrare
: 2
: 16 
: 2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2
: 1
; Ieșire
: Datele sunt introduse corect.
: 4

== Exemplu 2 ==
; Intrare
: 2
: 6
: 2 2 2 3 3 3
: 1
; Ieșire
: Datele nu corespund restrictiilor impuse


== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 2073 - PlatouK v2

def validate_input(k, n, arr):
    if not 1 <= k <= 100 or not 1 <= n <= 1000000:
        return False
    if len(arr) != n:
        return False
    for i in arr:
        if not 0 <= i <= 10000:
            return False
    return True


def find_longest_plateau(k, arr):
    n = len(arr)
    longest_plateau = 0
    plateau_element = -1

    for i in range(n):
        j = i + 1
        while j < n and arr[i] == arr[j]:
            j += 1
        plateau_len = j - i
        if plateau_len > longest_plateau:
            longest_plateau = plateau_len
            plateau_element = arr[i]

    return longest_plateau, plateau_element


def solve(k, n, arr):
    if not validate_input(k, n, arr):
        print("Datele nu corespund restrictiilor impuse.")
        return

    for i in range(k):
        plateau_len, plateau_element = find_longest_plateau(1, arr)
        if plateau_len == 0:
            break
        arr.remove(plateau_element)
        _, new_element = find_longest_plateau(1, arr)
        arr.insert(arr.index(new_element) + 1, plateau_element)

    plateau_len, plateau_element = find_longest_plateau(1, arr)
    print(plateau_len)


if __name__ == "__main__":
    k = int(input())
    n = int(input())
    arr = list(map(int, input().split()))
    p = int(input())

    if p == 1:
        solve(k, n, arr)
    else:
        print("Datele sunt introduse corect.")


</syntaxhighlight>
== Explicatie Rezolvare ==
validare(n, k, sir, cerinta) - Aceasta este o funcție de validare care primește ca parametri: n - numărul de elemente din șir, k - numărul maxim de operații permise, sir - lista cu elemente din șir și cerinta - un intreg care specifica cerinta (1 sau 2). Funcția validează inputul și returnează True dacă valorile de intrare sunt corecte, altfel returnează False.

lungime_platou(platou) - Această funcție primește ca parametru un platou, adică o secvență formată din valori identice. Funcția calculează și returnează lungimea platoului, adică numărul de elemente care îl formează.

rezolva(sir, k) - Această funcție primește ca parametri: sir - lista cu elemente din șir și k - numărul maxim de operații permise. Funcția calculează lungimea maximă a unui platou care poate să apară în șir în urma efectuării operației de maxim k ori și elementul din care este format platoul obținut după cele k operații și returnează aceste valori.

main() - Aceasta este funcția principală a programului, care se execută atunci când rulăm scriptul. Funcția citeste input-ul de la utilizator, validează inputul și apoi calculează și afișează rezultatul.