Simulare ONI 2018 | gene

This was the problem page during the contest. Access the current page here.
Time limit: 0.2s Memory limit: 64MB Input: gene.in Output: gene.out

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 2020 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 KK, 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 66 (22 caractere a, 22 caractere d, 11 caracter b, 11 caracter c).

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

Cerință

Cunoscând NN, MM, KK , 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 CC, care nu poate avea decât valorile 11 sau 22 și indică numărul cerinței care va fi rezolvată. Pe a doua linie numerele naturale NN, MM și KK , 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×MN \times M linii câte o secvență de maximum 2020 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 22, pe prima linie a fișierului de ieșire se vor scrie, separate prin câte un spațiu, trei numere naturale xylgmaxx 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<N,M5000 \lt N, M \leq 500
  • 0<K200 \lt K \leq 20
  • colțul din stânga sus al hărții are poziția (1,1)(1, 1)
  • dacă pentru cerința 11 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 22 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ă 3030 de puncte, pentru rezolvarea corectă a celei de a doua cerințe se acordă 7070 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:

aaacctgaaacctg – grad 44
abrcgabrcg – grad 33
saasdfssaasdfs – grad 11
ecctgecctg – grad 33
abncttabnctt – grad 33
agtatggtagtatggt – grad 33
aaaaaa – grad 11
ccgtabdccgtabd – grad 44
bbbbbbbb – grad 00

deci maximul este 44 ș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: 23142134124433012 3 1 4 2 1 3 4 1 2 4 4 3 3 0 1. Deci reprezentarea hărții în formă bidimensională este:

(2314213412443301)\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 22 are latura 22 și începe la linia 22, coloana 33.

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