`Всеукраїнський центр проведення олімпіад в мережі Інтернет

Задача Typo. На комп’ютерах серії “Буг” кожна літера задається матрицею у N рядківта M стовпчиків, кожен піксель якої або чорний, або білий. Введемо поняття кернінгу між сусідніми символами. Кернінгом назвемо суму відстаней (тобто кількість білих пікселів) між найлівішим чорним пікселем правої літери і найправішим чорним пікселем лівої літери по кожному рядку. До прикладу, нехай N = M = 3 і ми розглядаємо два сусідні символи:  У даному випадку у першому рядку відстань рівна 1, у другому 2, утретьому 1, тож сумарно маємо 4, а отже і кернинг буде 4. Вам дані

нариси N символів (причому кожен символ містить хоча б один чорний піксель у кожному рядку). Потрібно визначити, чи можна з них скласти послідовність (можливо, з повторами) так, щоб сума кернінгів між усіма

парами сусідніх літер складала рівно X. В порожнього рядку сумою кернінгів буде 0. Оскільки це дуже важлива задача, ми попросимо вивести відповідь для багатьох запитів.

Технічні умови. Програма Typo читає з пристрою стандартного введення 3 цілих числа N, M, K (1 ≤ N, M, K ≤ 100) - розміри матриці, що задають кожен символ та кількість символів. Далі слідують K*N рядків по M символів, причому кожні N послідовних рядків задають нарис певного символа. “#” (символ решітки) при цьому означає чорний піксель, ‘.’ (символ крапки) - білий.     Далі слідує число Q (1<=Q<=100) -кількість запитів, після чого слідують Q цілих невід’ємних чисел (кожне не перевищує 109) - власне, запити.  Програма має вивести рівно Q символів “Y” у випадку, якщо навідповідний запит відповідь “так” (тобто можна скласти послідовність з символів відповідним кернінгом) або “N” у іншому випадку.

Приклад

Введення          

3 3 2

.##

##.

.##

.#.

.#.

.#.

3

4 5 2

Виведення

YYN

© LIKT 1998-2024