Simulation - Lot 2017 Baraj 4 Juniori | cod

Un spărgător care doreşte să golească un seif are nevoie de codul acestuia şi pentru aceasta are deja o secvenţă de $K$ numere naturale care reprezintă în mod cert o parte din cod, care din păcate nu este obligatoriu complet. El primeşte de la doi asociaţi câte o secvenţă de $M$ respectiv $N$ numere naturale, care, spune fiecare din ei, este codul corect şi complet. Pentru că cele două coduri nu coincid, spărgătorul, pentru a-şi maximiza şansele, încearcă să determine un cod cât mai lung, format dintr-un şir de numere care este comun celor două şiruri primite de la asociaţi şi, în plus, să conţină ca subşir codul său.

Cerinţă

Dat un şir de numere naturale $c_1$, $c_2$, $\dots$, $c_K$ ce reprezintă codul spărgătorului, precum şi alte două şiruri de numere naturale $x_1$, $x_2$, $\dots$, $x_M$ şi $y_1$, $y_2$, $\dots$, $y_N$, ce reprezintă codurile celor doi asociaţi, să se determine lungimea maximă a unui şir de numere care este cod comun celor două coduri ale asociaţilor şi conţine, în plus, ca subşir codul spărgătorului.

Date de intrare

Fişierul cod.in conţine pe prima linie trei numere naturale $K$, $M$ şi $N$ separate prin câte un spaţiu, care reprezintă lungimile celor trei coduri, pe linia a doua se găsesc $K$ numere naturale separate prin câte un spaţiu reprezentând codul spărgătorului. Pe linia a treia se găsesc $M$ numere naturale separate prin câte un spaţiu reprezentând codul primului asociat, iar pe linia a patra se găsesc $N$ numere naturale separate prin câte un spaţiu reprezentând codul celui de-al doilea asociat.

Date de ieșire

Fişierul cod.out conţine pe prima linie un număr natural, care reprezintă lungimea maximă a unui cod ce respectă cerinţele.

Restricții și precizări

• $1 \leq K \leq M,N \leq 255$
• codurile conţin numere naturale din intervalul $[1, 255]$
• un subşir se obţine dintr-un şir prin eliminarea a zero, unul sau mai multe elemente, nu neapărat situate pe poziţii consecutive
• Pentru datele de intrare va exista întotdeauna o soluţie de lungime cel puţin $K$

Exemplu

cod.in

2 8 9
5 2
2 5 6 2 9 5 9 6
5 6 5 9 2 6 2 9 7

cod.out

4

Explicație

Codul spărgătorului are lungimea $K = 2$ şi este şirul $5$, $2$. Cele două coduri ale asociaţilor sunt de lungimi $M = 8$ şi respectiv $N = 9$ şi sunt date de şirurile de pe liniile $3$ şi $4$.

$4$ este lungimea maximă a codului comun celor două coduri ale asociaţilor şi care conţine ca subşir codul spărgătorului. Acesta este $5$, $6$, $2$, $6$. Există un cod de lungime $5$ comun celor două coduri ale asociaţilor, anume $5 \ 6 \ 5 \ 9 \ 6$, dar nu conţine ca subşir codul $5 \ 2$.