يدرس Farmer John نسب القطيع: $M$ ثيران ($1 \le M \le 20$)، و$F$ أبقار ($1 \le F \le 20$)، لكنه لا يعرف السلالات الممكنة.
يعرف تسلسل DNA الفريد $DNA_{i}$ لكل حيوان. $DNA_{i}$ طوله $25$ وبالأحرف الكبيرة A و$C$ وG وT فقط. يريد الأطفال الممكنين لكل زوج ثور وبقرة.
لكل زوج اطبع عدد الحيوانات الأخرى الممكن أن تكون أطفاله إذا:
ليس أيًا من والديه، فلا بقرة أم نفسها ولا ثور أب نفسه؛
كل موضع DNA يطابق أحد الوالدين على الأقل في الموضع نفسه.
abc ممكن من (axx, xbc) وليس من (aaa, bbb).
اعتبر تسلسلات $3$ ثيران و$2$ بقرتين:
Bull 1: GTTTTTTTTTTTTTTTTTTTTTTTT
Bull 2: AATTTTTTTTTTTTTTTTTTTTTTT
Bull 3: GATTTTTTTTTTTTTTTTTTTTTTT
Cow 1: TTTTTTTTTTTTTTTTTTTTTTTTT
Cow 2: ATTTTTTTTTTTTTTTTTTTTTTTTالثور $2$ والبقرة $1$ قد يكونان والدي البقرة $2$:
Bull 2: AATTTTTTTTTTTTTTTTTTTTTTT
Cow 1: TTTTTTTTTTTTTTTTTTTTTTTTT
Cow 2: ATTTTTTTTTTTTTTTTTTTTTTTTحرفها الأول A قد يأتي من الثور $2$، والثاني T من البقرة $1$، والباقي من أي والد.
أنشئ مصفوفة أعداد الأطفال الممكنين لكل زوج.
الإدخال
السطر $1$: الصحيحان $M$ و$F$ مفصولان بمسافة.
الأسطر $2..M+1$: السطر $i+1$ يعطي التسلسل $DNA_{i}$ للثور $i$.
الأسطر $M+2..M+F+1$: السطر $j+M+1$ يعطي التسلسل $DNA_{j}$ للبقرة $j$.
الإخراج
- الأسطر $1..M$: السطر $i$ به $F$ أعداد صحيحة؛ العدد $j$ يحصي أطفال الثور $i$ والبقرة $j$ الممكنين.
أمثلة
الإدخال 1
2 3 TGAAAAAAAAAAAAAAAAAAAAAAA AGAAAAAAAAAAAAAAAAAAAAAAA ATAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAA TTAAAAAAAAAAAAAAAAAAAAAAA
الإخراج 1
2 1 0 0 0 2
ملاحظة
DNA لـ$2$ ثورين ثم لـ$3$ أبقار.
اعتبر الثور $1$ والبقرة $1$:
b1: TGAAAAAAAAAAAAAAAAAAAAAAA
c1: ATAAAAAAAAAAAAAAAAAAAAAAAالجزء المهم {T|A} ثم {G|T}.
اختبارات المطابقة للثور $0$ والبقرة $0$:
b1: TGAAAAAAAAAAAAAAAAAAAAAAA -- parent, can't be offspring
b2: AGAAAAAAAAAAAAAAAAAAAAAAA offspring! Matches [TA][GT]
c1: ATAAAAAAAAAAAAAAAAAAAAAAA -- parent, can't be offspring
c2: AAAAAAAAAAAAAAAAAAAAAAAAA -- second character is 'A'; must be G or T
c3: TTAAAAAAAAAAAAAAAAAAAAAAA offspring! Matches [TA][GT]Bull / Cow; parent, can't be offspring; offspring! Matches; second character is A; must be G or T: ثور؛ بقرة؛ والد، لا يمكن أن يكون طفلًا؛ طفل! يطابق؛ الحرف الثاني A ويجب أن يكون G أو T
إذن أول عنصر $2$، والبقية بالمثل.
مؤلف المسألة: Jacob Steinhardt، 2010