Revizia anterioară Revizia următoare
| 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.07 sec | Limită de memorie | 65536 KB |
| Scorul tău | N/A | Dificultate |
   3.5
|
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], vv[2], ..., vv[i].
Cerință
Scrieti un program care sa determine, pentru orice 1 ≤ i ≤ N, lungimea maxima a unei secvente i – exclusive.
Date de intrare
Fișierul de intrare exclusiv.in contine pe prima linie numerele naturale M si N. Pe linia a doua se afla M numere naturale reprezentand elementele vectorului s , iar pe linia a treia N numere naturale reprezentand elementele vectorului v . Valorile scrise pe aceeasi linie sunt separate prin cate un spatiu.
Date de ieșire
Fișierul de ieșire exclusiv.out va contine N linii. Pe linia i (1 ≤ i ≤ N) va fi scris un numar natural care reprezinta lungimea maxima a unei secvente i – exclusive
Restricții
- 1 ≤ N ≤ 2000
- 3 ≤ M ≤ 105
- Vectorii s si v contin numere natural ≤ 2*109
, memorate incepand cu pozitia 1 - O subsecventa nevida in s este formata din elemente situate pe pozitii consecutive , i ≤ j. O subsecventa i – exclusiva poate fi si vida, 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 si 1000 < M ≤ 2000
- Pentru alte teste valorand 20 de puncte N = 2000 si 104 < M ≤ 105
Exemplu
| exclusiv.in | exclusiv.out |
|---|---|
| 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 |
Explicație
Cea mai lunga secventa 1 – exclusiva (care nu contine valoarea 11) este 9 2 77 88 88 88 2 7 2 2 77 2 si are lungimea 12.
Cea mai lunga secventa 2 – exclusiva (care nu contine valorile 11 si 5) este 9 2 77 88 88 88 2 7 2 2 77 2 si are lungimea 12.
Cea mai lunga secventa 3 – exclusiva (care nu contine valorile 11, 5 si 7) este 9 2 77 88 88 88 2 si are lungimea 7.
Cea mai lunga secventa 4 – exclusiva (care nu contine valorile 11, 5, 7 si 9) este 2 77 88 88 88 2 si are lungimea 6
Cea mai lunga secventa 5 – exclusiva (care nu contine valorile 11, 5, 7, 9 si 5) este 2 77 88 88 88 2 si are lungimea 6
Cea mai lunga secventa 6 – exclusiva (care nu contine valorile 11, 5, 7, 9, 5 si 2) este 77 88 88 88 si are lungimea 4
