Условие
Вдохновленный шедевром Казимира Малевича «Черный квадрат», Петр Палевич решил создать собственную версию картины. Он приготовил полотно в виде прямоугольной сетки с $m \times n$ белыми квадратами — $m$ строк по $n$ ячеек каждая.
Петр покрасил некоторые клетки в черный цвет так, что черные ячейки сформировали квадрат размером $s \times s$ ячеек. Но на следующий день Петр разочаровался в своем творении и уничтожил его, разрезав полотно горизонтальными полосами размера $1 \times n$, после чего сжег их в камине.
На следующее утро Петр передумал и решил восстановить картину. Он попытался найти ее останки в камине, и, к счастью, одну из полос, а именно $k$-ую сверху, огонь не тронул.
Теперь Петр задумался, можно ли восстановить картину на основе этой полосы. Помогите ему сделать это.
Входные данные
Первая строка содержит четыре целых числа: $m$,$n$,$s$ и $k$.
$(1 \leq m,n \leq 5000, 1 \leq s \leq \min(m,n), 1 \leq k \leq m).$
Вторая строка содержит $n$ символов и описывает $k$-ую строку картины, ‘.’ означает белую клетку, ‘*’ означает черную клетку.
Выходные данные
Если изображение может быть однозначно восстановлено, то следует вывести «Unique». Если существует несколько вариантов восстановления картины, то вывести «Ambiguous». Если ни одной соответствующей картины не существует, вывести «Impossible».
Тесты
| Входные данные | Выходные данные |
| $3$ $4$ $2$ $3$ ..** |
Unique |
| $4$ $4$ $2$ $3$ *.*. |
Impossible |
| $3$ $5$ $2$ $2$ .**.. |
Ambiguous |
| $2$ $8$ $1$ $2$ ……*. |
Unique |
Код задачи
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); int s = sc.nextInt(); int k = sc.nextInt(); String stripe = sc.next(); int number_of_stars = 0; boolean end_of_stars = false; boolean sec_seq = false; String result = new String(); for (int i = 0; !sec_seq && i < stripe.length(); i++){ if ('*' == stripe.charAt(i)) { if (end_of_stars == true) sec_seq = true; else number_of_stars++; } else { if (end_of_stars == false && number_of_stars != 0){ end_of_stars = true; } } } if (sec_seq == true) result = "Impossible"; else { if (number_of_stars == 0) { if (s > k-1 && s > m-k) result = "Impossible"; else { if (n > s) result = "Ambiguous"; else { if ((s > m - k && k - 1 == s) || (s > k - 1 && m - k == s)){ result = "Unique"; } else result = "Ambiguous"; } } } else { if (number_of_stars != s) result = "Impossible"; else { if (m == s || s == 1 || k == 1 || k == m) result = "Unique"; else result = "Ambiguous"; } } } System.out.print(result); } } |
Решение
Основная сложность задачи заключается в аккуратном рассмотрении всех возможных вариантов. После прочтения строки символов, которую представляет собой вытащенная из огня полоска, исследуем ее на количество подряд идущих символов $*$. Если последовательностей из звездочек в одной строке несколько, то никакие добавленные полоски не смогут сделать из нее квадрат, и тогда решений нет. Иначе дальнейшее решение делится на два случая:
- Спасенная из огня полоска не содержит звездочек. Тогда мы проверяем, может ли поместиться квадрат из звездочек хотя бы в одну из двух частей, на которые эта полоска делит картину. Если да, проверяем, однозначно ли определяем этот квадрат, или же имеется несколько вариантов его возможного расположения в них.
- Спасенная из огня полоска содержит звездочки. Тогда, если количество звездочек не совпадает с длиной стороны квадрата, то построить его невозможно, а иначе проверяем, однозначно ли определяем этот квадрат. Здесь необходимо аккуратно рассмотреть все «особенные» случаи, такие как квадрат, состоящий из одной звездочки, а также первая и последняя полоски картины. Очевидно, что в этих случаях расположение квадрата определяется единственным образом.