Simulare ONI 2018 | gene

Gigel este curios să afle în ce zonă a țării au trăit cei mai mulți dintre strămoșii săi. El reușește să adune informații despre structura genetică a persoanelor din diferite părți ale țării și speră că, prin compararea cu propria structură genetică, să identifice o zonă pătratică în care au trăit cei mai mulți dintre strămoșii săi.

Structura genetică a unei persoane este reprezentată sub forma unei secvențe cu cel mult $20$ de caractere (litere mici ale alfabetului englez). O persoană poate fi considerată strămoș a lui Gigel dacă gradul de similaritate dintre secvența corespunzătoare persoanei respective și cea a lui Gigel este mai mare strict decât un număr $K$, cunoscut.

Gradul de similaritate dintre două secvențe este reprezentat de numărul de caractere comune celor două secvențe. De exemplu pentru secvențele abcdabd și acbdaad gradul de similaritate este $6$ ($2$ caractere a, $2$ caractere d, $1$ caracter b, $1$ caracter c).

Gigel reprezintă harta țării sub forma unui tablou bidimensional cu $N$ linii și $M$ coloane în care fiecare element reprezintă structura genetică a unei persoane din zona respectivă.

Cerință

Cunoscând $N$, $M$, $K$ , structura genetică pentru Gigel și reprezentarea hărții identificată de acesta, să se determine:

1. poziția pe hartă și structura genetică pentru persoana, sau persoanele, pentru care gradul de similaritate cu structura genetică a lui Gigel este maxim;
2. o zonă pătratică, de dimensiune maximă în care toate persoanele ar putea fi strămoși ai lui Gigel.

Date de intrare

Fișierul de intrare gene.in conţine pe prima linie numărul natural $C$, care nu poate avea decât valorile $1$ sau $2$ și indică numărul cerinței care va fi rezolvată. Pe a doua linie numerele naturale $N$, $M$ și $K$ , separate prin câte un spațiu, cu semnificația de mai sus. Pe a treia linie se află structura genetică a lui Gigel, iar pe următoarele $N \times M$ linii câte o secvență de maximum $20$ de litere mici ale alfabetului englez, care reprezintă structurile genetice ale persoanelor din țară, în ordinea parcurgerii hărții pe linii.

Date de ieșire

Fișierul de ieşire gene.out va conţine răspunsul la cerința rezolvată.

Dacă s-a rezolvat prima cerință, fișierul de ieșire va conține, pe linii separate, datele de identificare pentru persoanele cu cel mai mare grad de similaritate, după cum urmează: câte două numere naturale, separate prin câte un spațiu, care reprezintă poziția pe hartă a unei persoane urmate de un spațiu și secvența care indică structura ei genetică.

Dacă s-a rezolvat cerința $2$, pe prima linie a fișierului de ieșire se vor scrie, separate prin câte un spațiu, trei numere naturale $x y lgmax$ reprezentând poziția colțului din stânga sus, exprimată în ordine prin indicele liniei și al coloanei, respectiv lungimea maximă a laturii pătratului identificat pe hartă.

Restricții și precizări

• $0 \lt N, M \leq 500$
• $0 \lt K \leq 20$
• colțul din stânga sus al hărții are poziția $(1, 1)$
• dacă pentru cerința $1$ există mai multe persoane cu grad de similaritate maxim, se vor afișa în ordine lexicografică a poziției pe hartă (în ordine crescătoare a indicelui de linie, iar în caz de egalitate pentru acesta, în ordine crescătoare a indicelui de coloană);
• dacă pentru cerința $2$ există mai multe zone maximale, se va afișa cea cu indicele de linie cel mai mic, iar în caz de egalitate și pentru acesta, cea cu indicele de coloană mai mic;
• pentru rezolvarea corectă a primei cerinţe se acordă $30$ de puncte, pentru rezolvarea corectă a celei de a doua cerințe se acordă $70$ de puncte.

Exemplul 1

gene.in

1
3 3 3
acgt
aaacctg
abrcg
saasdfs
ecctg
abnctt
agtatggt
aaa
ccgtabd
bbbb

gene.out

1 1 aaacctg
3 2 ccgtabd

Explicație

Secvența corespunzătoare lui Gigel este: acgt

Pentru secvențele din hartă gradele de similaritate sunt:

$aaacctg$ – grad $4$
$abrcg$ – grad $3$
$saasdfs$ – grad $1$
$ecctg$ – grad $3$
$abnctt$ – grad $3$
$agtatggt$ – grad $3$
$aaa$ – grad $1$
$ccgtabd$ – grad $4$
$bbbb$ – grad $0$

deci maximul este $4$ și apare pentru două dintre secvențe

Exemplul 2

gene.in

2
4 4 2
acgt
aec
ctg
abvf
acgtaaa
bbbbttg
saa
acgec
actgt
abvf
nctt
cagtatggt
acgtaaa
bbabttg
saatg
sdfs
fhgj

gene.out

2 3 2 

Explicație

Pentru harta dată, gradele de similaritate cu secvența acgt sunt, în ordine: $2 3 1 4 2 1 3 4 1 2 4 4 3 3 0 1$. Deci reprezentarea hărții în formă bidimensională este:

$\begin{pmatrix} 2 & 3 & 1 & 4 \\ 2 & 1 & 3 & 4 \\ 1 & 2 & 4 & 4 \\ 3 & 3 & 0 & 1 \end{pmatrix}$

Cea mai mare zonă pătratică, în care toate gradele sunt mai mari strict decât $2$ are latura $2$ și începe la linia $2$, coloana $3$.