2026 - PlatouK: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
No edit summary
Flaviu (talk | contribs)
No edit summary
Line 51: Line 51:
: 2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2
: 2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2
: 1  
: 1  
: Datele sunt introduse correct.
; Ieșire
; Ieșire
: Datele sunt introduse correct.
: 4
: 4


== Exemplu 2 ==
== Exemplu 2 ==
; Intrare
; Intrare
: 2 1 1
: 2
: 16 2 3 3  
: 5
: 2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2
: 3 3 3 4 4
: 1 3 4
: 1
; Ieșire
; Ieșire
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.
: 3




Line 69: Line 71:
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line>
# 2026 - PlatouK
# 2026 - PlatouK
def find_longest_plateau(arr, k):
    n = len(arr)
    ans = 0
    ans_element = arr[0]
    for i in range(n):
        # Determina platoul curent
        j = i + 1
        while j < n and arr[j] == arr[i]:
            j += 1
        length = j - i
        # Calculeaza cate elemente se pot adauga inainte
        # sau dupa platou pentru a obtine un nou platou
        # cu elementele vechi
        extra = min(k, i, n-j)
        # Calculeaza lungimea noului platou
        new_length = length + 2 * extra


def extract_plateau(a):
        if new_length > ans:
i = 0
            ans = new_length
max_len = 1
            ans_element = arr[i]
max_start = 0
while i < len(a):
start = i
while i < len(a) - 1 and a[i] == a[i+1]:
i += 1
if i - start + 1 > max_len:
max_len = i - start + 1
max_start = start
i += 1
return a[max_start:max_start+max_len]


def longest_plateau(a, k):
    return ans, ans_element
b = a.copy()
max_plateau_len = 1
for _ in range(k):
plateau = extract_plateau(b)
if len(plateau) < 2:
break
max_plateau_len += len(plateau) - 2
b = [x for x in b if x not in plateau]
return max_plateau_len


def most_frequent_plateau(a, k):
b = a.copy()
max_plateau_len = 1
most_frequent_plateau_value = a[0]
for x in set(a):
b = a.copy()
max_current_plateau_len = 1
for _ in range(k):
plateau = extract_plateau(b)
if len(plateau) < 2:
break
if plateau[0] == x:
max_current_plateau_len += len(plateau)
b = [x for x in b if x not in plateau]
else:
b = [x for x in b if x not in plateau]
if max_current_plateau_len > max_plateau_len:
max_plateau_len = max_current_plateau_len
most_frequent_plateau_value = x
return most_frequent_plateau_value


if name == 'main':
if __name__ == '__main__':
k = int(input())
    k = int(input())
n = int(input())
    n = int(input())
a = list(map(int, input().split()))
    arr = list(map(int, input().split()))
p = int(input())
    question = int(input())
if p == 1:
result = longest_plateau(a, k)
else:
result = most_frequent_plateau(a, k)
if result is not None:
print("Datele sunt introduse corect.")
print(result)
else:
print("Datele nu corespund restricțiilor impuse.")


    if question == 1:
        print("Datele sunt introduse corect.")
        ans, _ = find_longest_plateau(arr, k)
        print(ans)
    elif question == 2:
        print("Datele sunt introduse corect.")
        _, ans_element = find_longest_plateau(arr, k)
        print(ans_element)
    else:
        print("Datele nu corespund restricțiilor impuse.")


</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Citim datele de intrare: numărul de operații posibile k, numărul de elemente din șir n, șirul de numere a și cerința p.
Am definit o funcție find_longest_plateau care primește un șir de numere și un număr k și returnează lungimea maximă a unui platou care poate să apară în șir în urma efectuării celor două operații de maxim k ori și elementul din care este format platoul.
Implementăm o funcție longest_plateau(a, k) care primește ca argumente șirul a și numărul de operații posibile k și returnează lungimea maximă a unui platou care poate apărea în șir în urma efectuării celor două operații de maxim k ori.
Pentru a determina lungimea maximă a unui platou, vom parcurge șirul și pentru fiecare poziție vom determina platoul curent, apoi vom calcula câte elemente se pot adăuga înainte sau după platou pentru a obține un nou platou cu elementele vechi, apoi vom calcula lungimea noului platou și o vom compara cu rezultatul curent, actualizând valoarea maximă și elementul corespunzător, dacă este cazul.
Implementăm o funcție most_frequent_plateau(a, k) care primește ca argumente șirul a și numărul de operații posibile k și returnează elementul din care este format platoul cu lungimea maximă care poate apărea în șir în urma efectuării celor două operații de maxim k ori.
În funcția main citim valorile de intrare și apoi verificăm valoarea întrebării. În funcție de întrebare, vom afișa lungimea maximă a unui platou sau elementul din care este format platoul, folosind funcția find_longest_plateau.
În funcția main, apelăm funcțiile implementate în funcție de cerința p și afișăm rezultatul.

Revision as of 22:29, 13 May 2023

Sursa: - PlatouK


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

Se dă un şir de n numere. 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: 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 pentru un şir dat determina: 1: lungimea maximă a unui platou care poate să apară în şir în urma efectuării celor două operaţiuni de maxim k ori 2: elementul din care este format platoul

Date de intrare

Programul va citi:

  • pe prima linie un număr natural k;
  • pe a doua linie un număr natual n;
  • pe a treia linie un şir de n numere naturale separate prin câte un spaţiu, reprezentând elementele şirului dat. Fiecare dintre aceste
 numere aparţine intervalului [0,10000].
  • pe a patra linie p, care reprezinta cerinta

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 lungimea maximă a unui platou care poate să apară în şir în urma efectuării celor două operaţiuni de maxim k ori sau elementul din care este format platoul., 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
  • numerele aparțin intervalului [0,10000].
  • pentru cerinta 1 – 50% din punctaj
  • pentru cerinta 2 – 50% din punctaj
  • daca sunt mai multe numere care au platou de lungime maxima se va afisa cel mai mare
  • toate testele au solutie

crescător

Exemplu 1

Intrare
2
16
2 2 5 0 5 8 8 8 4 9 9 9 0 8 2 2
1
Datele sunt introduse correct.
Ieșire
4

Exemplu 2

Intrare
2
5
3 3 3 4 4
1
Ieșire
Datele nu corespund restricțiilor impuse.
3


Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 2026 - PlatouK

def find_longest_plateau(arr, k):

   n = len(arr)
   ans = 0
   ans_element = arr[0]
   for i in range(n):
       # Determina platoul curent
       j = i + 1
       while j < n and arr[j] == arr[i]:
           j += 1
       length = j - i
       # Calculeaza cate elemente se pot adauga inainte
       # sau dupa platou pentru a obtine un nou platou
       # cu elementele vechi
       extra = min(k, i, n-j)
       # Calculeaza lungimea noului platou
       new_length = length + 2 * extra
       if new_length > ans:
           ans = new_length
           ans_element = arr[i]
   return ans, ans_element


if __name__ == '__main__':

   k = int(input())
   n = int(input())
   arr = list(map(int, input().split()))
   question = int(input())
   if question == 1:
       print("Datele sunt introduse corect.")
       ans, _ = find_longest_plateau(arr, k)
       print(ans)
   elif question == 2:
       print("Datele sunt introduse corect.")
       _, ans_element = find_longest_plateau(arr, k)
       print(ans_element)
   else:
       print("Datele nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicatie Rezolvare

Am definit o funcție find_longest_plateau care primește un șir de numere și un număr k și returnează lungimea maximă a unui platou care poate să apară în șir în urma efectuării celor două operații de maxim k ori și elementul din care este format platoul. Pentru a determina lungimea maximă a unui platou, vom parcurge șirul și pentru fiecare poziție vom determina platoul curent, apoi vom calcula câte elemente se pot adăuga înainte sau după platou pentru a obține un nou platou cu elementele vechi, apoi vom calcula lungimea noului platou și o vom compara cu rezultatul curent, actualizând valoarea maximă și elementul corespunzător, dacă este cazul. În funcția main citim valorile de intrare și apoi verificăm valoarea întrebării. În funcție de întrebare, vom afișa lungimea maximă a unui platou sau elementul din care este format platoul, folosind funcția find_longest_plateau.