| Fișierul intrare/ieșire | exclusiv.in, exclusiv.out | Sursă | OJSEPI 2021, clasa 7-a |
|---|---|---|---|
| Autor | Nistor-Eugen Moț | Adăugată de |
Voicu Mihai Valeriu
•
bitoneko
|
| Timp de execuție pe test | 0.3 sec | Limită de memorie | 65536 KB |
| Scorul tău | N/A | Dificultate |
  4
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Exclusiv (clasa a 7-a)
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ță
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
- 1 ≤ N ≤ 2000
- 3 ≤ M ≤ 105
- Vectorii s și v conțin numere naturale mai mici sau egale cu 2·109
, memorate începând cu poziția 1 - O subsecvență nevidă în s este formată din elemente situate pe poziții consecutive , i ≤ j. O subsecvență i – exclusivă poate fi și vidă, lungimea ei fiind 0.
- Pentru teste valorand 10 puncte N = 1
- Pentru alte teste valorand 30 de puncte 1 < N ≤ 50 si M ≤ 1000
- Pentru alte teste valorand 40 de puncte 50 < N ≤ 2000 și 1000 < M ≤ 2000
- Pentru alte teste valorand 20 de puncte N = 2000 și 104 < M ≤ 105
Exemplu
| exclusiv.in | exclusiv.out | Explicații |
|---|---|---|
| 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 |
12 12 7 6 6 4 |
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 |
