2073 - PlatouK v2

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

3

Rezolvare

Rezolvare ver. 1

# 2073 - PlatouK v2

def lungime_maxima_platou(arr, k, counter=0):
    if counter == k:
        max_len, result = 0, None
        for i in range(len(arr)):
            j = i + 1
            while j < len(arr) and arr[j] == arr[i]:
                j += 1
            if j - i > max_len:
                max_len = j - i
                result = arr[i]
        return max_len, result
    max_len, result = 0, None
    for i in range(len(arr) - 1):
        if arr[i] == arr[i+1]:
            tmp_arr = arr[:i] + arr[i+2:]
            tmp_arr.insert(i, arr[i:i+2])
            len_platou, val_platou = lungime_maxima_platou(tmp_arr, k, counter+1)
            if len_platou > max_len:
                max_len = len_platou
                result = val_platou
    return max_len, result

if __name__ == "__main__":
    k = int(input())
    n = int(input())
    arr = list(map(int, input().split()))
    p = int(input())
    if p not in (1, 2):
        print("Datele nu corespund restricțiilor impuse.")
    else:
        print("Datele sunt introduse corect.")
        max_len, result = lungime_maxima_platou(arr, k)

Explicatie Rezolvare

Funcția max_platou care primește ca parametrii lista de numere și numărul maxim de mutări și returnează lungimea maximă a unui platou care poate să apară în șir în urma efectuării operațiilor și elementul din care este format platoul obținut după cele k operații.

Funcția parcurge lista și găsește cel mai lung platou care se poate forma într-un număr maxim de k mutări și returnează lungimea acestuia și valoarea elementului din care este format. Pentru a găsi acest platou se realizează următoarele operații:

Pentru fiecare platou din listă: Se încearcă mutarea acestuia într-o poziție arbitrară Se calculează lungimea maximă a unui platou din șirul obținut după mutare și numărul de mutări efectuate pentru a ajunge la acel șir Dacă lungimea maximă a platoului din șirul obținut este mai mare decât cea a platoului maxim găsit până acum, se actualizează lungimea maximă și elementul din care este format platoul maxim Funcția main care se execută doar dacă acest fișier este rulat direct, nu importat în altul. Funcția citește datele de intrare, validează aceste date și apelează funcția max_platou pentru a afișa rezultatul.

În funcția main, se citesc datele de intrare și se validează, adică se verifică dacă acestea corespund condițiilor impuse în enunțul problemei. Dacă datele de intrare sunt corecte, se apelează funcția max_platou pentru a calcula lungimea maximă a unui platou care poate să apară în șir în urma efectuării operațiilor și elementul din care este format platoul obținut după cele k operații. Dacă datele nu sunt corecte, se afișează mesajul "Datele nu corespund restricțiilor impuse."