Bulls
TopCoder SRM 572
Time Limit: 0.4s, Memory Limit: 64MiB
Повечето от Вас са чувал за играта "Бикове и Крави". Ели пък измисли вариант на играта, който тя нарича просто "Бикове".
Правилата са много прости: играта се играе от двама играчи, като всеки от тях в началото си намисля по едно число с K десетични цифри. Играчите се редуват, като на всеки ход правят предположение кое е числото на другия (тоест казват някакво K-цифрено число). Ако улучат това, което противникът си е намислил, те печелят играта. Ако ли пък не, другият играч е длъжен да каже на колко позиции цифрите на истинското число и предположението съвпадат (което са така наречените "бикове").
Например, ако единият си е намислил 1337, а другият предположи 1738 (тук K = 4), то първият ще отвърне "2 бика", тъй като цифрите на 1-ва и 3-та позиция съвпадат. Ако пък предположи 7777, то другият ще отвърне "1 бик", тъй като само цифрата на 4-та позиция съвпада.
Ели играе срещу един от блестящите си (буквално, особено на слънце) съученици – Едуард. Всеки от тях до момента е направил определен брой предположения. Разбира се, както някои от вас най-вероятно знаят, Едуард може да чете мисли, така че няма особен проблем да спечели играта. От друга страна пък Ели е не по-малко готина от него, така че той предпочита да поиграят известно време преди да победи.
Това, което Едуард не подозира, е, че Ели има на своя страна информатиката. Тя си води статистика на листче кои числа е предположила и колко познати позиции (бика) има за всяко от тях. Тя ви ги дава на вас с молба да определите дали има еднозначен отговор (и ако да, какъв е той) от досегашните й предположения и отговори.
Правилата са много прости: играта се играе от двама играчи, като всеки от тях в началото си намисля по едно число с K десетични цифри. Играчите се редуват, като на всеки ход правят предположение кое е числото на другия (тоест казват някакво K-цифрено число). Ако улучат това, което противникът си е намислил, те печелят играта. Ако ли пък не, другият играч е длъжен да каже на колко позиции цифрите на истинското число и предположението съвпадат (което са така наречените "бикове").
Например, ако единият си е намислил 1337, а другият предположи 1738 (тук K = 4), то първият ще отвърне "2 бика", тъй като цифрите на 1-ва и 3-та позиция съвпадат. Ако пък предположи 7777, то другият ще отвърне "1 бик", тъй като само цифрата на 4-та позиция съвпада.
Ели играе срещу един от блестящите си (буквално, особено на слънце) съученици – Едуард. Всеки от тях до момента е направил определен брой предположения. Разбира се, както някои от вас най-вероятно знаят, Едуард може да чете мисли, така че няма особен проблем да спечели играта. От друга страна пък Ели е не по-малко готина от него, така че той предпочита да поиграят известно време преди да победи.
Това, което Едуард не подозира, е, че Ели има на своя страна информатиката. Тя си води статистика на листче кои числа е предположила и колко познати позиции (бика) има за всяко от тях. Тя ви ги дава на вас с молба да определите дали има еднозначен отговор (и ако да, какъв е той) от досегашните й предположения и отговори.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и K – съответно броят предположения на Ели и с колко цифрени числа ираят двамата. Всеки от следващите N реда ще съдържа едно К-цифрено число, което е възможно да съдържа водещи нули, следвано от още едно естествено число - броя познати позиции (бикове).
Изход
Ако има точно едно възможно решение, го изпечатайте на един единствен ред на стандартния изход. Ако има повече от едно възможно решение, вместо това изведете "Ambiguity". Ако пък дадената информация е неконсистентна (тоест Едуард е излъгал на някой ход и задачата няма решение), изведете "Liar".
Ограничения
- 1 ≤ N ≤ 50
- 1 ≤ K ≤ 10
| Примерен Вход | Примерен Изход |
|---|---|
| 11 4 1234 2 4321 1 1111 1 2222 0 3333 2 4444 0 5555 0 6666 0 7777 1 8888 0 9999 0 | 1337 |
| 4 6 666666 2 666677 3 777777 1 999999 0 | Ambiguity |
| 3 4 0000 2 1111 2 2222 2 | Liar |
В първия пример от {1234->2, 2222->0, 4444->0} следва, че числото е {1?3?}. Допълнителната информация, {4321->1} ни казва, че или на втора позиция има 3, или на четвърта има 1. Но тъй като {1111->1} и имаме 1 на първа позиция, следователно не може да имаме и на 4-та. Така откриваме, че числото е {133?}. При пробването на {7777->1} се оказва, че имаме една седмица, която не може да е никъде другаде, освен на последната позиция.
Във втория пример някои от възможните конфигурации, които отговарят на досегашните въпроси, са {636172, 336617, 660007, ...}.
В третия пример имаме две нули, две единици и две двойки в четирицифрено число (!?).
Във втория пример някои от възможните конфигурации, които отговарят на досегашните въпроси, са {636172, 336617, 660007, ...}.
В третия пример имаме две нули, две единици и две двойки в четирицифрено число (!?).