Давним давно, фрактальна цивілізація витворила художній твір, що складається з лінійних рядів плиток. У них було тільки два типи плитки, які вони могли б використовувати: золото (G) і свинець (L).
Кожна частина фрактальної твору заснована на двох параметрах: оригінальна послідовність K плиток і складність C. Для даної вихідної послідовності, художній твір зі складністю 1 це просто вихідна послідовність, і витвір зі складністю X + 1 визначається рекурсивно з художнього твору зі складністю X за наступним правилом:
- замінити кожну плитку L у витворі мистецтва складності X іншою копією вихідної послідовності
- замінити кожну плитку G у витворі мистецтва складності X повторенням K плиток типу G
Наприклад, для вихідної послідовності LGL, витворами мистецтва зі складністю з 1 по 3 є:
- C = 1: LGL (що є просто вихідною послідовністю)
- С = 2: LGLGGGLGL
- C = 3: LGLGGGLGLGGGGGGGGGLGLGGGLGL
Ось ілюстрація того, як витвір зі складністю 2 генерується з художнього твору зі складністю 1:
Ви щойно виявили шматок фрактальної мистецтва з дуже забрудненими плитками, щоб дізнатися, чи з золота вони чи зі свинцю. Оскільки Ви експерт археолог знайомий з місцевою фрактальною культури, ви знаєте значення K і C для художніх робіт, але ви не знаєте вихідну послідовність. Оскільки золото є захоплюючим, ви хотіли б знати, чи є принаймні одна плитка G в художньому творі. Ваш бюджет дозволяє найняти S аспірантів, кожен з яких може очистити одну плитку за вашим вибором (із плиток [formula]K^C[/formula] в художньому творі), щоб побачити чи ця плитка G або L.
Чи можливо вибрати набір не більше, ніж S конкретних плиток для очищення, таким чином, що незалежно від того, якою була оригінальна послідовність була, можна буде визначити точно, чи присутня в художньому творі, щонайменше одна плитка G? Якщо так, то які плитки треба очистити?
Вхідні дані
Перший рядок вхідного файлу містить кількість тестових випадків T, за ним T тестових наборів даних. Кожен складається з одного рядка з трьома цілими числами: K, C і S.
Вихідні дані
Для кожного тесту вивести один рядок, що містить Case #X: у, де х позначає номер тестового прикладу (починаючи з 1) і у має значення або "IMPOSSIBLE" (неможливо), якщо не можна вибрати такого набору плиток, щоб визначити чи є хоча б одна плитка G у даному витворі мистецтва, або список додатніх цілих чисел, кількістю між 1 і S, які є положеннями плиток, які треба перевірити. Позиції плиток пронумеровані від 1 для крайньої лівої плитки до K^C для крайньої правої плитки. Ваші обрані позиції можуть бути в будь-якому порядку, але всі вони повинні бути різними.
Якщо існує декілька допустимих наборів плитки, ви можете вивести будь-який із них. Пам'ятайте, що як тільки ви відправите відповідь на малий набір даних і він буде прийнятий, ви не зможете повторно завантажити інший варіант і відправити його. Дивіться FAQ: [url]https://codejam.withgoogle.com/codejam/faq.html#5-2[/url] для більш докладного пояснення. [b]Це нагадування НЕ буде з'являтися в задачах у більш пізніх раундах.[/b]
Обмеження
1 ≤ T ≤ 100.
1 ≤ K ≤ 100.
1 ≤ C ≤ 100.
K^C ≤ 10^18.
Малий набір даних
S = K.
Великий набір даних
1 ≤ S ≤ K.
Зразок
Вхідні дані
5
2 3 2
1 1 1
2 1 1
2 1 2
3 2 3
Вихідні дані
Case #1: 2
Case #2: 1
Case #3: IMPOSSIBLE
Case #4: 1 2
Case #5: 2 6
Примітка: для деяких з цих прикладів випадків, існують інші коректні розв’язки.
У випадку №1, існує чотири можливих вихідних послідовностей: GG, GL, LG і LL. З них можуть бути створені наступні твори мистецтва, відповідно:
Оригінальна послідовність GG : GGGGGGGG
Оригінальна послідовність GL : GGGGGGGL
Оригінальна послідовність LG: LGGGGGGG
Оригінальна послідовність LL: LLLLLLLL
Один коректний розв’язок - це просто подивитися на плитку №2. Якщо плитка №2 виявляється G, то ви будете знати напевно, що художній твір містить принаймні одну плитку G. (Ви не будете знати, чи вихідна послідовність була GG, GL, або LG, але це не має значення.) Якщо плитка №2 виявляється L, то ви будете знати, що вихідна послідовність повинна бути LL, тому в художньому творі немає плиток G. Таким чином, 2 є коректним розв’язком.
З іншого боку, це не було б коректно, просто перевірити плитку №1. Якщо виявиться там L, ви будете тільки знати, що вихідна послідовність може бути або LG або LL. Якщо вихідна послідовність LG, є принаймні одна плитка G в художньому творі, але якщо вихідна послідовність є LL, то плиток G немає. Таким чином, число 1 не буде коректним розв’язком.
Зверніть увагу, що 1 2 також є правильним розв’язком, тому що плитка №2 вже містить всю необхідну інформацію. 1 2 3 не є правильним розв’язком, оскільки він використовує занадто багато плитки (дозволено тільки 2 плитки перевірити).
У випадку №2, твір повинен складатися тільки з однієї плитки: або G або L. Дивлячись на цю плитку буде тривіальним визначити, чи присутня плитка G у ньому.
У випадку №3, який не буде доступний в малому наборі даних, твір повинен бути або GG, GL, LG або LL. Ви можете дивитися тільки на одну плитку, і жодної із них самої по собі не досить, щоб відповісти на це питання. Якщо ви бачите L для плитки №1, ви не будете знати, чи це твір LG або LL, так що ви не будете знати, чи присутня тут хоча б одна плитка G. Якщо ви бачите L для плитки №2, ви не будете знати, чи цей твір GL або LL, так що ви не будете знати, чи присутні тут плитки G.
Прикладі №4 схожий на випадок №3, але з доступом до ще однієї плитки. Тепер ви можете просто подивитися на всю картину.
У випадку №5, існує вісім можливих оригінальних послідовностей, і вони будуть створювати наступні твори мистецтва:
Оригінальна послідовність GGG: GGGGGGGGG
Оригінальна послідовність GGL: GGGGGGGGL
Оригінальна послідовність GLG: GGGGLGGGG
Оригінальна послідовність GLL: GGGGLLGLL
Оригінальна послідовність LGG: LGGGGGGGG
Оригінальна послідовність LGL: LGLGGGLGL
Оригінальна послідовність LLG: LLGLLGGGG
Оригінальна послідовність LLL: LLLLLLLLL
Один із правильних розв’язків - це перевірити плитки №№ 2 і 6. Якщо вони обидва виявляються плитками L, то твір мусить складатися лише із плиток L. В іншому випадку, принаймні, один плитка G присутня. Слід зазначити, що вивід 1 2 для цього випадку не буде правильним розв’язком, оскільки навіть якщо ці плитки і виявляються плитками L, це не виключає оригінальну послідовність LLG. Вивід 6 2 буде правильним розв’язком, тому що порядок позицій у вашому розв’язку не має значення.
Немає коментарів:
Дописати коментар