2073 - PlatouK v2: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 43: Line 43:
* dacă sunt mai multe platouri de lungime maxima se va afișa cel mai mare considera cel format din valoarea cea mai mare
* 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
toate testele au soluție
== Exemplu 1 ==
; Intrare
; Intrare
: 2
: 2
Line 49: Line 51:
: 1
: 1
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele sunt introduse corect.
: Datele sunt introduse correct.
: 4
: 4
== Exemplu 2 ==
; Intrare
: 2
: 6
: 2 2 2 3 3 3
: 1
; Ieșire
: Datele nu corespund restrictiilor impuse
: 3


== Rezolvare ==  
== Rezolvare ==  
Line 58: Line 69:
# 2073 - PlatouK v2
# 2073 - PlatouK v2


def citire_lista():
def lungime_maxima_platou(arr, k, counter=0):
     try:
     if counter == k:
        k = int(input())
         max_len, result = 0, None
        n = int(input())
         for i in range(len(arr)):
         lista = list(map(int, input().split()))
            j = i + 1
         p = int(input())
            while j < len(arr) and arr[j] == arr[i]:
        return k, lista, p
                j += 1
    except:
            if j - i > max_len:
        print("Datele nu corespund restrictiilor impuse.")
                max_len = j - i
 
                result = arr[i]
def rezolva(k, lista):
         return max_len, result
    try:
    max_len, result = 0, None
        # calculam dictionarul frecventelor
    for i in range(len(arr) - 1):
        frecvente = {}
         if arr[i] == arr[i+1]:
        for element in lista:
            tmp_arr = arr[:i] + arr[i+2:]
            frecvente[element] = frecvente.get(element, 0) + 1
            tmp_arr.insert(i, arr[i:i+2])
          
             len_platou, val_platou = lungime_maxima_platou(tmp_arr, k, counter+1)
        # gasim elementul cu cea mai mare frecventa
             if len_platou > max_len:
        max_frecventa = max(frecvente.values())
                max_len = len_platou
        element_max_frecventa = max(k for k, v in frecvente.items() if v == max_frecventa)
                result = val_platou
       
     return max_len, result
        # calculam lungimea maxima a unui platou dupa k operatii
        lungime_maxima = min(max_frecventa + k, len(lista))
         return lungime_maxima if p == 1 else element_max_frecventa
    except:
        print("Datele nu corespund restrictiilor impuse.")
 
def valideaza(valoare):
    try:
        if isinstance(valoare, int):
             print("Datele sunt introduse corect.")
             print(valoare)
        else:
            print("Datele sunt introduse corect.")
            print(*valoare)
     except:
        print("Datele nu corespund restrictiilor impuse.")


if __name__ == "__main__":
if __name__ == "__main__":
     k, lista, p = citire_lista()
     k = int(input())
     rezultat = rezolva(k, lista)
    n = int(input())
     valideaza(rezultat)
    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)




Line 105: Line 106:
</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Funcția citire_lista() primește datele de intrare și le citește folosind funcții predefinite în Python. Aceasta returnează un tuplu format din k, lista și p.
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.


Funcția rezolva(k, lista) primește k și lista citite de la intrare și implementează algoritmul descris în cerință pentru a determina lungimea maximă a unui platou sau elementul din care este format platoul, în funcție de cerința specificată. Pentru a face acest lucru, funcția calculează mai întâi un dicționar al frecvențelor elementelor din lista și găsește elementul cu cea mai mare frecvență. Pentru a găsi lungimea
Î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."

Revision as of 22:40, 13 May 2023

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

<syntaxhighlight lang="python" line>

  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)


</syntaxhighlight>

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."