AjM: Pagină nouă: == Enunt == Se consideră doi vectori care conțin numere naturale: s cu M elemente și v cu N elemente. Numim secvență i-exclusivă o secvență a vectorului s care nu conține niciuna dintre valorile v[1], v[2], …, v[i]. == Cerinţa == Scrieți un program care să determine, pentru orice 1 ≤ i ≤ N, lungimea maximă a unei secvențe i-exclusive. == Date de intrare == Fișierul de intrare exclusiv.in conține pe prima linie numerele naturale M și N. Pe linia a doua s...

2024-06-03T16:31:19Z

Pagină nouă: == Enunt == Se consideră doi vectori care conțin numere naturale: s cu M elemente și v cu N elemente. Numim secvență i-exclusivă o secvență a vectorului s care nu conține niciuna dintre valorile v[1], v[2], …, v[i]. == Cerinţa == Scrieți un program care să determine, pentru orice 1 ≤ i ≤ N, lungimea maximă a unei secvențe i-exclusive. == Date de intrare == Fișierul de intrare exclusiv.in conține pe prima linie numerele naturale M și N. Pe linia a doua s...

New page

== Enunt ==
Se consideră doi vectori care conțin numere naturale: s cu M elemente și v cu N elemente. Numim secvență i-exclusivă o secvență a vectorului s care nu conține niciuna dintre valorile v[1], v[2], …, v[i].
== Cerinţa ==
Scrieți un program care să determine, pentru orice 1 ≤ i ≤ N, lungimea maximă a unei secvențe i-exclusive.
== Date de intrare ==
Fișierul de intrare exclusiv.in conține pe prima linie numerele naturale M și N. Pe linia a doua se află M numere naturale reprezentând elementele vectorului s, iar pe linia a treia N numere naturale reprezentând elementele vectorului v. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.
== Date de ieșire ==
Fișierul de ieșire exclusiv.out va conține N linii. Pe linia i (1 ≤ i ≤ N) va fi scris un număr natural care reprezintă lungimea maximă a unei secvențe i-exclusive.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 2.000
* 3 ≤ M ≤ 100.000
* Vectorii s și v conțin numere naturale mai mici sau egale cu 2.000.000.000, memorate începând cu poziția 1
* Valorile din fiecare vector nu sunt obligatoriu distincte două câte două.
* O subsecvență nevidă în s este formată din elemente situate pe poziții consecutive (s[i], s[i + 1], …, s[j]), i ≤ j. O subsecvență i-exclusivă poate fi și vidă, lungimea ei fiind 0.
== Exemplu ==
; exclusiv.in
20 6
11 5 11 7 2 10 11 9 2 77 88 88 88 2 7 2 2 77 2 11
11 5 7 9 5 2
; exclusiv.out
12
12
7
6
6
4
<br>

== Explicație ==
Cea mai lungă secvență 1-exclusivă (care nu conține valoarea 11) este 9 2 77 88 88 88 2 7 2 2 77 2 și are lungimea 12.
Cea mai lungă secvență 2-exclusivă (care nu conține valorile 11 și 5) este 9 2 77 88 88 88 2 7 2 2 77 2 și are lungimea 12.
Cea mai lungă secvență 3-exclusivă (care nu conține valorile 11, 5 și 7) este 9 2 77 88 88 88 2 și are lungimea 7.
Cea mai lungă secvență 4-exclusivă (care nu conține valorile 11, 5, 7 și 9) este 2 77 88 88 88 2 și are
lungimea 6.
Cea mai lungă secvență 5-exclusivă (care nu conține valorile 11, 5 7, 9 și 5) este 2 77 88 88 88 2 și are lungimea 6.
Cea mai lungă secvență 6-exclusivă (care nu conține valorile 11, 5, 7, 9, 5 și 2) este 77 88 88 88 și are lungimea 4.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def longest_exclusive_sequence(s, v):
last_position = {value: -1 for value in v}
longest_sequence = 0
current_sequence = 0

for value in s:
if value in last_position:
current_sequence = min(current_sequence + 1, 1 + last_position[value])
else:
current_sequence += 1
last_position[value] = current_sequence
longest_sequence = max(longest_sequence, current_sequence)

return longest_sequence

def main():
M, N = map(int, input().split())
s = list(map(int, input().split()))
v = list(map(int, input().split()))

result = []
for i in range(N):
result.append(longest_exclusive_sequence(s, v[:i+1]))

for length in result:
print(length)

if __name__ == "__main__":
main()

</syntaxhighlight>

3729 - Exclusiv - Revision history