3729 - Exclusiv

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

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>