Условие
Вдохновленный шедевром Казимира Малевича «Черный квадрат», Петр Палевич решил создать собственную версию картины. Он приготовил полотно в виде прямоугольной сетки с $m \times n$ белыми квадратами — $m$ строк по $n$ ячеек каждая.
Петр покрасил некоторые клетки в черный цвет так, что черные ячейки сформировали квадрат размером $s \times s$ ячеек. Но на следующий день Петр разочаровался в своем творении и уничтожил его, разрезав полотно горизонтальными полосами размера $1 \times n$, после чего сжег их в камине.
На следующее утро Петр передумал и решил восстановить картину. Он попытался найти ее останки в камине, и, к счастью, одну из полос, а именно $k$-ую сверху, огонь не тронул.
Теперь Петр задумался, можно ли восстановить картину на основе этой полосы. Помогите ему сделать это.
Входные данные
Первая строка содержит четыре целых числа: $m$, $n$, $s$ и $k$ $ \left( 1 \leqslant m, n \leqslant 5000, 1 \leqslant s \leqslant \min \left( m, n \right), 1 \leqslant k \leqslant m \right) $.
Вторая строка содержит $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 |
Код
String
|
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 |
#include <iostream> #include <string> using namespace std; int main() { int m, n, s, k; cin >> m >> n >> s >> k; string str; cin >> str; int star_number = 0; bool end_of_stars = 0; bool sec_seq = 0; bool imp = 0; bool un = 0; bool amb = 0; for (int i = 0; i < str.length() && !sec_seq; i++){ if (str[i] == '*') { if (end_of_stars == 1) sec_seq = 1; else star_number++; } else { if ( (star_number != 0) and (end_of_stars == 0) ) end_of_stars = 1; } } if (sec_seq == 1) imp = 1; else { if (star_number == 0) { if (s > k-1 && s > m-k) imp = 1; else { if (n>s) amb = 1; else { if ( ( (s > m - k) and (k - 1 == s) ) or ( (s > k - 1) and (m - k == s) ) ) un = 1; else amb = 1; } } } else { if (star_number != s) imp = 1; else { if (m == s || s == 1 || k == 1 || k == m) un = 1; else amb = 1; } } } if (un == 1) cout << "Unique"; if (amb == 1) cout << "Ambiguous"; if (imp == 1) cout << "Impossible"; return 0; } |
C-string
|
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 |
#include <iostream> #include <cstring> using namespace std; int main() { const int MAXN = 5001; int m, n, s, k; cin >> m >> n >> s >> k; char seq [MAXN]; cin >> seq; int star_number = 0; bool end_of_stars = 0; bool sec_seq = 0; bool imp = 0; bool un = 0; bool amb = 0; for (int i = 0; i < strlen(seq) && !sec_seq; i++){ if (seq[i] == '*') { if (end_of_stars == 1) sec_seq = 1; else star_number++; } else { if ( (star_number != 0) and (end_of_stars == 0) ) end_of_stars = 1; } } if (sec_seq == 1) imp = 1; else { if (star_number == 0) { if (s > k-1 && s > m-k) imp = 1; else { if (n>s) amb = 1; else { if ( ( (s > m - k) and (k - 1 == s) ) or ( (s > k - 1) and (m - k == s) ) ) un = 1; else amb = 1; } } } else { if (star_number != s) imp = 1; else { if (m == s || s == 1 || k == 1 || k == m) un = 1; else amb = 1; } } } if (un == 1) cout << "Unique"; if (amb == 1) cout << "Ambiguous"; if (imp == 1) cout << "Impossible"; return 0; } |
Решение
Основная сложность задачи заключается в аккуратном рассмотрении всех возможных вариантов. После прочтения строки символов, которую представляет собой вытащенная из огня полоска, исследуем ее на количество подряд идущих символов ‘*’. Если последовательностей из звездочек в одной строке несколько, то никакие добавленные полоски не смогут сделать из нее квадрат, и тогда решений нет. Иначе дальнейшее решение делится на два случая:
- Спасенная из огня полоска не содержит звездочек. Тогда мы проверяем, может ли поместиться квадрат из звездочек хотя бы в одну из двух частей, на которые эта полоска делит картину. Если да, проверяем, однозначно ли определяем этот квадрат, или же имеется несколько вариантов его возможного расположения в них.
- Спасенная из огня полоска содержит звездочки. Тогда, если количество звездочек не совпадает с длиной стороны квадрата, то построить его невозможно, а иначе проверяем, однозначно ли определяем этот квадрат. Здесь необходимо аккуратно рассмотреть все «особенные» случаи, такие как квадрат, состоящий из одной звездочки, а также первая и последняя полоски картины. Очевидно, что в этих случаях расположение квадрата определяется единственным образом.
Если сравнивать, что выгоднее использовать в данной задаче для задания спасённой из огня полоски — строку или массив символов, — то использование строки способствует немного более быстрому решению задачи, чем массив символов; объём используемой памяти при этом не изменяется.
Ссылки
Условие на e-olymp.com
Код с использованием string на ideone.com
Код с использованием c-string на ideone.com