InfoCNFB Mirror - Seniori | plagiat

Colegiul Național “Frații Buzești”
Centrul de Pregătire pentru Performanță în Informatică
InfoCNFB - Ediția a II-a, Seniori
9 decembrie 2023

Cerință

Spunem că un șir $(a_1, a_2, \dots, a_t)$ este plagiat al șirului $(b_1, b_2, \dots, b_t)$ dacă $a_1 - b_1 = a_2 - b_2 = \dots = a_t - b_t$.

Având două șiruri: $A$ de lungime $N \ (A_1, A_2, \dots, A_N)$ și $B$ de lungime $M \ (B_1, B_2, \dots, B_M)$, vrem să determinăm cea mai lungă subsecvență din $A$ pentru care există o subsecvență în $B$ căreia îi este plagiat. Cu alte cuvinte dacă $L$ este lungimea maximă căutată, există $i$ și $j$ astfel încât $(A_i, A_{i+1}, \dots, A_{i+L-1})$ este plagiat al secvenței $(B_j, B_{j+1}, \dots, B_{j+L-1})$.

Să se afiseze tripletul $(L, i, j)$. Dacă există mai multe soluții cu lungime maximă, o preferăm pe cea cu $i$ minim, daca încă există mai multe soluții, o vom prefera pe cea cu $j$ minim.

Date de intrare

Fișierul plagiat.in conține pe prima linie numărul $n$. Pe linia a doua sunt $n$ numere naturale separate prin spațiu, reprezentând elementele șirului $A$. Pe linia a treia se află un număr natural $m$. Pe linia a patra sunt $m$ numere naturale separate prin spațiu, reprezentând elementele șirului $B$.

Date de ieșire

Pe prima linie a fișierului plagiat.out se află cele trei numere naturale $L$, $i$, $j$, separate prin spațiu, cu semnificația descrisă mai sus.

Restricții și precizări

• $1 \leq n, m \leq 100 \ 000$;
• $0 \leq A_i, B_i \leq 1 \ 000$;
• Pentru $36$ de puncte $n, m \leq 300$;
• Pentru alte $24$ de puncte $n, m \leq 4 \ 000$;
• Pentru alte $16$ puncte $n, m \leq 10 \ 000$;
• Pentru restul de $24$ de puncte nu sunt restricții suplimentare.

Exemplu

plagiat.in

13
10 12 20 6 4 5 7 6 4 5 21 11 12
17
13 14 12 7 6 7 9 8 6 7 9 8 6 7 1 1 2

plagiat.out

7 4 8