Simulation - Lot 2017 Baraj 4 Juniori | cod

This was the problem page during the contest. Access the current page here.
Time limit: 0.03s Memory limit: 2MB Input: cod.in Output: cod.out

Un spărgător care doreşte să golească un seif are nevoie de codul acestuia şi pentru aceasta are deja o secvenţă de KK 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 MM respectiv NN 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 c1c_1, c2c_2, \dots, cKc_K ce reprezintă codul spărgătorului, precum şi alte două şiruri de numere naturale x1x_1, x2x_2, \dots, xMx_M şi y1y_1, y2y_2, \dots, yNy_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 KK, MM şi NN separate prin câte un spaţiu, care reprezintă lungimile celor trei coduri, pe linia a doua se găsesc KK numere naturale separate prin câte un spaţiu reprezentând codul spărgătorului. Pe linia a treia se găsesc MM numere naturale separate prin câte un spaţiu reprezentând codul primului asociat, iar pe linia a patra se găsesc NN 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

  • 1KM,N2551 \leq K \leq M,N \leq 255
  • codurile conţin numere naturale din intervalul [1,255][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 KK

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=2K = 2 şi este şirul 55, 22. Cele două coduri ale asociaţilor sunt de lungimi M=8M = 8 şi respectiv N=9N = 9 şi sunt date de şirurile de pe liniile 33 şi 44.

44 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 55, 66, 22, 66. Există un cod de lungime 55 comun celor două coduri ale asociaţilor, anume 5 6 5 9 65 \ 6 \ 5 \ 9 \ 6, dar nu conţine ca subşir codul 5 25 \ 2.

Log in or sign up to be able to send submissions!