Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Bovine Genomics №3

Двумерные массивы

У Фермера Джона есть N коров с пятнами и N коров без пятен. ФД, как генетик, знает, что пятна на коровах вызваны мутациями в одной позиции коровьего генома.
За большие деньги ФД выписал геномы своих коров. Каждый геном есть строка длины M, построенная из четырёх символов A, C, G, T. Когда он выписал их, у него получилась такая таблица (для N=3):
 
Позиция:                  1 2 3 4 5 6 7 ... M
 
Пятнистая корова 1: A A T C C C A ... T
Пятнистая корова 2: G A T T G C A ... A
Пятнистая корова 3: G G T C G C A ... A
 
Без пятен корова 1: A C T C C C A ... G
Без пятен корова 2: A C T C G C A ... T
Без пятен корова 3: A C T T C C A ... T

Внимательно проанализировав эту таблицу, он предположил, что позиция 2 есть потенциальное место в геноме, которое отвечает за пятнистость. Потому что в этой позиции у коров без пятен находится один и тот же символ С, а у пятнистых коров находятся символы A или G. Причём G больше никогда не появлялось на позиции 2. Позиция 1 не может объяснять пятнистость, поскольку A в этой позиции есть и у пятнистых коров.
 
По заданным геномам коров ФД, посчитайте количество позиций, которые потенциально могли бы объяснять пятнистость.
 
ФОРМАТ ВВОДА:
 
Первая строка ввода содержит N и M, оба - положительные целые числа не более 100. Каждая из следующих N строк содержит по M символов. Они описывают геномы пятнистых коров. Следующие N строк описывают геномы коров без пятен.

ФОРМАТ ВВОДА:
 
Вычислите количество позиций генома (целое число в интервале от 0…M), которые потенциально могут объяснять пятнистость. Такие позиции можно предсказывать по заданной информации.
 
Ввод Вывод
3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT
1