Problem G
Genetikk
Languages
de
en
et
is
ja
lt
lv
no
pl
ru
sv
En vanlig teknikk som superskurker bruker for å unngå å bli fanget er å klone seg selv. Du har klart å fange en ond superskurk og hennes $N-1$ kloner, men du ønsker å finne ut hvem av de som er den ekte superskurken.
Til hjelp har du hver persons DNA-sekvens, som hver består av $M$ tegn, hvor hvert tegn er enten A, C, G eller T. Du vet også at klonene aldri er helt perfekte kopier, men at de har DNA-sekvenser som skiller seg fra den ekte superskurken på nøyaktig $K$ posisjoner.
Kan du identifisere den ekte superskurken?
Input
Første linje inneholder tre heltall $N$, $M$, og $K$, hvor $1 \le K \le M$. De neste $N$ linjene representerer DNA sekvenser. Hver av disse linjene inneholder $M$ tegn, hvor hvert tegn er enten A, C, G eller T.
I input vil det være nøyaktig én sekvens som skiller seg fra alle de andre sekvensene i nøyaktig $K$ posisjoner.
Advarsel: dette problemet har ganske mye input og vil kreve at du bruker raske IO-rutiner om du bruker Java.
Output
Skriv ut et heltall – indeksen av DNA-sekvensen som tilhører superskurken. Sekvensene er numerert begynnende med $1$.
Begrensninger
Løsningen din vil bli testet på et sett av testgrupper, hver verdt et visst antall poeng. Hver testgruppe inneholder et sett av tester. For å få poeng for en testgruppe må du løse alle testene i den gruppen. Din endelige poengsum vil være den høyeste poengsummen du har fått på en enkelt innlevering.
|
Group |
Points |
Limits |
Yttligere begrensninger |
|
1 |
27 |
$3 \le N, M \le 100$ |
|
|
2 |
19 |
$3 \le N, M \le 1800$ |
Hvert tegn er enten A eller C. |
|
3 |
28 |
$3 \le N, M \le 4100$ |
Hvert tegn er enten A eller C. |
|
4 |
26 |
$3 \le N, M \le 4100$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
4 3 1 ACC CCA ACA AAA |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 4 3 CATT CAAA ATGA TCTA |
4 |
