Hide

Problem G
Gen

Languages de en et is ja lt lv no pl ru sv

Fyrir illmenni sem ætla sér heimsyfirráð er algeng leið til að forðast handtöku að klóna sig. Þú hefur handsamað illmenni og $N-1$ klóna þess og ert nú að reyna finna hver er alvöru illmennið.

Þér til hjálpar hefurðu DNA röð hverrar persónu, hver þeirra samanstendur af $M$ táknum, hver stafur er A, C, G eða T. Þú veist einnig að klónarnir eru ekki skapaðir fullkomlega, heldur eru raðir þeirra frábrugðnar röð upprunalega illmennisins á nákvæmlega $K$ stöðum.

Getur þú auðkennt illmennið?

Inntak

Fyrsta línan inniheldur þrjár heiltölur $N$, $M$ og $K$ þar sem $1 \le K \le M$. Næstu $N$ línur tákna DNA raðirnar. Hver þessarra lína samanstendur af $M$ táknum, hvert þeirra er A, C, G eða T.

Í inntakinu er nákvæmlega ein röð sem er frábrugðin öllum hinum rununum á nákvæmlega $K$ stöðum.

Úttak

Skrifaðu út eina heiltölu – vísi DNA raðarinnar sem tilheyrir illmenninu. Fyrsta röðin er númer $1$.

Takmarkanir

Lausnin þín verður prófuð á einhvern fjölda prufuhópa, hver hópur gefur einhvern fjölda stiga. Hver hópur inniheldur einhvern fjölda prufutilvika. Til að fá stig fyrir hóp þarftu að leysa öll prufutilvik innan hópsins. Lokastigin eru fengin úr skilunum sem gáfu hæst stig.

Hópur

Stig

Takmarkanir

Auka takmarkanir

1

27

$2 \le N, M \le 100$

 

2

19

$2 \le N, M \le 1800$

Hver stafur er annað hvort A eða C.

3

28

$2 \le N, M \le 4100$

Hver stafur er annað hvort A eða C.

4

26

$2 \le N, M \le 4100$

 
Sýnidæmis inntak 1 Sýnidæmis úttak 1
4 3 1
ACC
CCA
ACA
AAA
3
Sýnidæmis inntak 2 Sýnidæmis úttak 2
4 4 3
CATT
CAAA
ATGA
TCTA
4