Soluții trimise

Rezumat problemă

#2497 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ă.

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.

ID   Utilizator Problema Data încărcării Stare
Lupau Alin (Bubu_Orange) gene 05 Octombrie 2021, 12:49 Evaluare finalizată 100
Ionescu Laura (guzgandemunte) gene 05 Septembrie 2021, 11:33 Evaluare finalizată 100
Ionescu Laura (guzgandemunte) gene 05 Septembrie 2021, 10:51 Evaluare finalizată 30
Ionescu Laura (guzgandemunte) gene 05 Septembrie 2021, 10:48 Evaluare finalizată 30
Tirziu Petre (petre) gene 13 Iunie 2021, 20:41 Evaluare finalizată 100
Tirziu Petre (petre) gene 13 Iunie 2021, 20:40 Evaluare finalizată 40
Tirziu Petre (petre) gene 13 Iunie 2021, 20:40 Evaluare finalizată 25
Tirziu Petre (petre) gene 13 Iunie 2021, 20:29 Evaluare finalizată 40
Tirziu Petre (petre) gene 13 Iunie 2021, 20:28 Evaluare finalizată 25
Tirziu Petre (petre) gene 13 Iunie 2021, 19:41 Evaluare finalizată 30
Tirziu Petre (petre) gene 13 Iunie 2021, 19:38 Evaluare finalizată 25
Tirziu Petre (petre) gene 13 Iunie 2021, 19:30 Evaluare finalizată 20
Tirziu Petre (petre) gene 13 Iunie 2021, 19:26 Evaluare finalizată 20
Stoica Tica Justin Sfefan (justinstoica) gene 08 Iunie 2021, 12:09 Evaluare finalizată 10
Popescu Adrian (Popescu_Adrian) gene 08 Iunie 2021, 09:46 Evaluare finalizată 100
Popescu Adrian (Popescu_Adrian) gene 08 Iunie 2021, 09:04 Evaluare finalizată 70
Dumitru Alexandru (AlexandruDumitru) gene 13 Mai 2021, 19:06 Evaluare finalizată 100
Dumitru Alexandru (AlexandruDumitru) gene 13 Mai 2021, 19:05 Evaluare finalizată 95
Dumitru Alexandru (AlexandruDumitru) gene 13 Mai 2021, 18:24 Evaluare finalizată 25
NU NU (ciorbel) gene 23 Aprilie 2021, 06:12 Evaluare finalizată 100
Savu Stefan Catalin (Savu_Stefan_Catalin) gene 14 Aprilie 2021, 17:27 Evaluare finalizată 100
Savu Stefan Catalin (Savu_Stefan_Catalin) gene 14 Aprilie 2021, 17:23 Evaluare finalizată 90
Savu Stefan Catalin (Savu_Stefan_Catalin) gene 14 Aprilie 2021, 17:22 Evaluare finalizată 80
Savu Stefan Catalin (Savu_Stefan_Catalin) gene 14 Aprilie 2021, 17:21 Evaluare finalizată 80
Savu Stefan Catalin (Savu_Stefan_Catalin) gene 14 Aprilie 2021, 17:14 Evaluare finalizată 0
Savu Stefan Catalin (Savu_Stefan_Catalin) gene 14 Aprilie 2021, 17:14 Evaluare finalizată 50
Soiu Cristian Ionuț (SparkleMan) gene 07 Aprilie 2021, 17:01 Evaluare finalizată 85
buruiana stefan (Buruiana_Stefan) gene 07 Aprilie 2021, 16:59 Evaluare finalizată 100
Soiu Cristian Ionuț (SparkleMan) gene 07 Aprilie 2021, 16:56 Evaluare finalizată 45
Soiu Cristian Ionuț (SparkleMan) gene 07 Aprilie 2021, 16:56 Evaluare finalizată 45
Soiu Cristian Ionuț (SparkleMan) gene 07 Aprilie 2021, 16:55 Evaluare finalizată 45
Soiu Cristian Ionuț (SparkleMan) gene 07 Aprilie 2021, 16:55 Evaluare finalizată 45
Soiu Cristian Ionuț (SparkleMan) gene 07 Aprilie 2021, 16:55 Evaluare finalizată 45
Soiu Cristian Ionuț (SparkleMan) gene 07 Aprilie 2021, 16:54 Evaluare finalizată 45
Soiu Cristian Ionuț (SparkleMan) gene 07 Aprilie 2021, 16:50 Evaluare finalizată 45
Soiu Cristian Ionuț (SparkleMan) gene 07 Aprilie 2021, 16:50 Evaluare finalizată 45
buruiana stefan (Buruiana_Stefan) gene 07 Aprilie 2021, 16:35 Evaluare finalizată 30
Soiu Cristian Ionuț (SparkleMan) gene 07 Aprilie 2021, 16:20 Evaluare finalizată 30
Dima Alexandru (AlexDd) gene 06 Aprilie 2021, 21:29 Evaluare finalizată 100
Dima Alexandru (AlexDd) gene 06 Aprilie 2021, 21:27 Evaluare finalizată 95
Dima Alexandru (AlexDd) gene 06 Aprilie 2021, 21:25 Evaluare finalizată 95
Dima Alexandru (AlexDd) gene 06 Aprilie 2021, 21:21 Evaluare finalizată 40
Dima Alexandru (AlexDd) gene 06 Aprilie 2021, 21:08 Evaluare finalizată 30
Dima Alexandru (AlexDd) gene 06 Aprilie 2021, 21:07 Evaluare finalizată 10
Dima Alexandru (AlexDd) gene 06 Aprilie 2021, 18:38 Evaluare finalizată 20
Dima Alexandru (AlexDd) gene 06 Aprilie 2021, 18:37 Evaluare finalizată 20
Vraja Luca (LORDEN) gene 06 Aprilie 2021, 11:17 Evaluare finalizată 100
Silaghi Vlad (Silaghi_Vlad) gene 06 Aprilie 2021, 11:03 Evaluare finalizată 30
Caracioni Octavian (octavian202) gene 06 Aprilie 2021, 10:58 Evaluare finalizată 100
Vraja Luca (LORDEN) gene 06 Aprilie 2021, 10:40 Evaluare finalizată 30