#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.
ONIG 2018
ID | Utilizator | Problema | Data încărcării | Stare | ||
---|---|---|---|---|---|---|
gene | 20 Aprilie 2024, 23:38 | Evaluare finalizată | 100 | |||
gene | 20 Aprilie 2024, 23:33 | Evaluare finalizată | 40 | |||
gene | 20 Aprilie 2024, 18:35 | Evaluare finalizată | 30 | |||
gene | 20 Aprilie 2024, 14:22 | Evaluare finalizată | 10 | |||
gene | 20 Aprilie 2024, 12:38 | Evaluare finalizată | 30 | |||
gene | 20 Aprilie 2024, 12:37 | Evaluare finalizată | 10 | |||
gene | 20 Aprilie 2024, 12:36 | Evaluare finalizată | 10 | |||
gene | 18 Aprilie 2024, 17:47 | Evaluare finalizată | 100 | |||
gene | 18 Aprilie 2024, 15:13 | Evaluare finalizată | 90 | |||
gene | 18 Aprilie 2024, 12:57 | Evaluare finalizată | E.C | |||
gene | 18 Aprilie 2024, 12:56 | Evaluare finalizată | E.C | |||
gene | 17 Aprilie 2024, 14:26 | Evaluare finalizată | 85 | |||
gene | 17 Aprilie 2024, 12:55 | Evaluare finalizată | 80 | |||
gene | 16 Aprilie 2024, 13:46 | Evaluare finalizată | 100 | |||
gene | 15 Aprilie 2024, 22:18 | Evaluare finalizată | 100 | |||
gene | 15 Aprilie 2024, 22:11 | Evaluare finalizată | 100 | |||
gene | 15 Aprilie 2024, 22:10 | Evaluare finalizată | 30 | |||
gene | 15 Aprilie 2024, 22:09 | Evaluare finalizată | 30 | |||
gene | 15 Aprilie 2024, 22:09 | Evaluare finalizată | E.C | |||
gene | 15 Aprilie 2024, 22:06 | Evaluare finalizată | 90 | |||
gene | 15 Aprilie 2024, 22:01 | Evaluare finalizată | 90 | |||
gene | 15 Aprilie 2024, 20:16 | Evaluare finalizată | 30 | |||
gene | 15 Aprilie 2024, 20:15 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 20:09 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 20:08 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 20:07 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 20:03 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 20:01 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 19:59 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 19:59 | Evaluare finalizată | E.C | |||
gene | 15 Aprilie 2024, 19:56 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 19:54 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 19:53 | Evaluare finalizată | E.C | |||
gene | 15 Aprilie 2024, 16:36 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 16:32 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 16:30 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 16:03 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 15:57 | Evaluare finalizată | 10 | |||
gene | 15 Aprilie 2024, 15:56 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 15:48 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 15:28 | Evaluare finalizată | 0 | |||
gene | 15 Aprilie 2024, 14:08 | Evaluare finalizată | 100 | |||
gene | 14 Aprilie 2024, 21:36 | Evaluare finalizată | 100 | |||
gene | 14 Aprilie 2024, 19:31 | Evaluare finalizată | 30 | |||
gene | 14 Aprilie 2024, 14:59 | Evaluare finalizată | 100 | |||
gene | 13 Aprilie 2024, 17:51 | Evaluare finalizată | 100 | |||
gene | 13 Aprilie 2024, 17:33 | Evaluare finalizată | 100 | |||
gene | 13 Aprilie 2024, 16:30 | Evaluare finalizată | 40 | |||
gene | 13 Aprilie 2024, 16:29 | Evaluare finalizată | 40 | |||
gene | 10 Aprilie 2024, 09:58 | Evaluare finalizată | 100 |