Hide

Problem B
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 N1 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 1KM. 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

3N,M100

 

2

19

3N,M1800

Hvert tegn er enten A eller C.

3

28

3N,M4100

Hvert tegn er enten A eller C.

4

26

3N,M4100

 
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
Hide

Please log in to submit a solution to this problem

Log in