Genomica bovina (Argento)#10525
Il Contadino John ha mucche maculate e mucche senza macchie. Avendo recentemente completato un corso di genetica bovina, è convinto che le macchie sulle sue mucche siano causate da mutazioni nel genoma.
Dopo aver pagato una somma considerevole, il Contadino John ha determinato i genomi di tutte le sue mucche. Ogni genoma è una stringa di lunghezza , composta da quattro caratteri: A, C, G e . Disponendo i genomi delle mucche uno sotto l'altro, ottiene una tabella simile a quella riportata di seguito, per il caso n = 3:
Positions: 1 2 3 4 5 6 7 ... M
Spotty Cow 1: A A T C C C A ... T
Spotty Cow 2: G A T T G C A ... A
Spotty Cow 3: G G T C G C A ... A
Plain Cow 1: A C T C C C A ... G
Plain Cow 2: A G T T G C A ... T
Plain Cow 3: A G T T C C A ... T Esaminando attentamente questa tabella, egli nota che le posizioni e sono sufficienti per distinguere le mucche maculate da quelle senza macchie. In altre parole, guardando soltanto i caratteri in queste due posizioni, il Contadino John può determinare in modo univoco se una mucca è maculata oppure no. Ad esempio, se nella posizione si trova e nella posizione si trova , allora la mucca è necessariamente maculata.
Il Contadino John ritiene che la presenza delle macchie possa essere spiegata considerando un certo insieme di tre posizioni distinte nel genoma. Aiutalo a determinare il numero di insiemi di tre posizioni distinte che permettono di distinguere le mucche maculate da quelle senza macchie.
Nella prima riga sono contenuti n~(1 \le n \le 500) e m~(3 \le m \le 50). Nelle successive righe sono contenute stringhe di lunghezza che descrivono i genomi delle mucche maculate. Nelle ultime righe sono contenuti i genomi delle mucche senza macchie.
Stampa il numero di insiemi di tre posizioni che permettono di spiegare la presenza delle macchie. Un insieme di tre posizioni permette di spiegare la presenza delle macchie se il tratto «maculatura» può essere determinato con precisione del cento per cento per tutte le mucche del Contadino John, considerando soltanto i caratteri in queste tre posizioni dei loro genomi.
Esempio 1