Завдання конкурсного завдання полягає в тому, щоб розробити ефективну програму, яка зможе вирішити головоломку «прямокутники».
Головоломка вводиться в прямокутне поле. У поле вводяться порожні поля та поля з цифровою інформацією. Завдання полягає в тому, щоб всю площу введеного пазла розбити на прямокутники так, щоб:
- прямокутники покривали всю вказану площу,
- прямокутники не перекривалися,
- кожна заповнена коробка була в іншому прямокутнику,
- розмір прямокутника (площі) дорівнював номеру заповненого квадрата.
Розв’язуючи, ви знаєте, що ігрова зона має розмір не більше 32x32 квадратів, загальна кількість заповнених квадратів становить не більше 200, а заповнені числа знаходяться в діапазоні від 1 до 99.
На стандартному вводі програма отримує вхід пазла, введення завершується закінченням std. вхід (EOF активний). Точний формат введення можна побачити у прикладі нижче.
Програма аналізує введений пазл і вирішує, який з варіантів вийшов:
- запис недійсний
- входом була головоломка, яка має лише одне дійсне рішення. У цьому випадку програма відобразить це рішення.
- Введенням був пазл, який не вдалося зібрати (0 рішень). Програма виводить інформацію про невдалу спробу.
- Зазначена головоломка має багато рішень (більше одного), у цьому випадку програма обчислює, скількома способами можна розділити поверхню. Під різними способами поділу розуміється, що розподіл прямокутників, що розділяють, відрізняється розташуванням принаймні однієї граничної лінії.
Програма повинна перевірити правильність введених даних. Якщо у вхідних даних введено неправильні, безглузді або суперечливі значення, програма виявляє це, відображає повідомлення про помилку та завершує роботу. Формат повідомлення про помилку показаний у прикладі виконання нижче. Помилкою вважається:
- відсутній, неправильний або неповний кадр поля,
- вміст поля відрізняється від пробілу та цифр 1-99,
- відсутність позначення кутів коробки,
- масив більше 32 x 32,
- кількість заповнених полів більше 200.
Програма тестується в обмеженому середовищі. Він обмежений обсягом доступної пам'яті та часом виконання. Обидва обмеження можна побачити в журналі тестування розчину зразка. Загалом, завдання не потребує пам’яті. Однак він дуже вимогливий до процесорного часу. Якщо головоломка має кілька рішень, вивчення всіх варіантів може зайняти дуже багато часу. Необхідно розробити ефективний алгоритм, який дозволить не витрачати час на спроби, які не приводять до мети.
Робота оцінюється в конкурсному режимі. Це означає, що це складніше, ніж стандартні роботи. Це вимагає поєднання навичок програмування та алгоритмізації. Передбачається, що завдання будуть вирішувати студенти, які мають певні знання з програмування, тобто студенти, для яких стандартні завдання нудні. Оцінка складається з гарантованого набору балів (успіх у позаконкурсних тестах) і набору балів, отриманих за місце в конкурсі з іншими учнями (ці бали зараховуються після закінчення конкурсу).
Приклад програмної роботи:
Введіть загадку:
+--+--+--+--+--+
| 2 3 2|
+ + + + + +
| 2 3 |
+ + + + + +
| 3 |
+ + + + + +
| 2 |
+ + + + + +
| 2 3 3|
+--+--+--+--+--+
Одне рішення:
+--+--+--+--+--+
| 2| 3 | 2|
+ +--+--+--+ +
| | 2| 3| |
+--+--+--+ +--+
| 3 | | |
+--+--+--+ + +
| | 2| | |
+ +--+--+--+ +
| 2| 3| 3|
+--+--+--+--+--+
Введіть пазл:
+--+--+--+--+--+--+--+--+--+--+
| 4 2 |
+ + + + + + + + + + +
| 3 |
+ + + + + + + + + + +
| 2 3 8 |
+ + + + + + + + + + +
| 4 2 10 |
+ + + + + + + + + + +
| 2 2 3 |
+ + + + + + + + + + +
| 2 6|
+ + + + + + + + + + +
| 12 6 |
+ + + + + + + + + + +
| 2 4 4|
+ + + + + + + + + + +
| 10 3 |
+ + + + + + + + + + +
| 2 2 2 |
+--+--+--+--+--+--+--+--+--+--+
Одне рішення:
+--+--+--+--+--+--+--+--+--+--+
| 4| 2| | | | | | |
+ + + + + + + + + + +
| | | | 3| | | | |
+ +--+ + + + + + + + +
| | 2| | | 3| 8| | |
+ + + +--+--+ + + + + +
| | | 4| 2 | | 10| |
+--+--+--+--+--+--+--+ + + +
| 2| 2| 3 | | |
+--+--+--+--+--+--+--+--+--+ +
| | | 2| 6|
+ + + + + + + + + +--+
| 12| 6 | | |
+--+--+--+--+--+--+ + +--+ +
| 2 | 4 | | | 4|
+--+--+--+--+--+--+--+--+ + +
| | | | 10 | 3| |
+ + + + + + + + + + +
| 2| 2| 2| | | |
+--+--+--+--+--+--+--+--+--+--+
Введіть пазл:
+--+--+--+--+--+--+--+--+--+
| 2 3 2 |
+ + + + + + + + + +
| 3 2 2 1 |
+ + + + + + + + + +
| 7 |
+ + + + + + + + + +
| 7 3 |
+ + + + + + + + + +
| 4 4 3 3 7|
+ + + + + + + + + +
| 3 |
+ + + + + + + + + +
| 4 3 |
+--+--+--+--+--+--+--+--+--+
Одне рішення:
+--+--+--+--+--+--+--+--+--+
| 2| 3| | | 2 | |
+ +--+--+--+ + +--+--+ +
| | 3| 2| 2| 1| | |
+--+--+--+--+--+--+--+ + +
| 7 | | |
+--+--+--+--+--+--+--+ + +
| 7 | 3| |
+--+--+--+--+--+--+--+--+ +
| 4| 4| 3| 3 | 7|
+ + + + + +--+--+--+ +
| | | | 3 | |
+--+--+--+--+ +--+--+--+ +
| 4 | | 3 | |
+--+--+--+--+--+--+--+--+--+
Введіть загадку:
+--+--+--+--+
| 4 |
+ + + + +
| 4 |
+ + + + +
| 4 |
+ + + + +
| 4|
+--+--+--+--+
Усього розв’язків: 9
Введіть пазл:
+--+--+--+--+--+--+--+--+--+
| 3 3 |
+ + + + + + + + + +
| 4 4 3 2 2 3 |
+ + + + + + + + + +
| 2 |
+ + + + + + + + + +
| 4 2 3 |
+ + + + + + + + + +
| 3 6 |
+ + + + + + + + + +
| 2 2 2 |
+ + + + + + + + + +
| 2 2 2 8|
+ + + + + + + + + +
| 8 |
+--+--+--+--+--+--+--+--+--+
Всього розв’язків: 39
Введіть загадку:
+--+--+--+--+--+--+
| |
+ + + + + + +
| 12 |
+ + + + + + +
| 2 4 |
+ + + + + + +
| 4 |
+ + + + + + +
| 2 |
+ + + + + + +
| |
+ + + + + + +
| 2 8 |
+ + + + + + +
| 3 5 6|
+--+--+--+--+--+--+
Немає рішення.
Введіть загадку:
+--+--+--+--+--+
| 2 |
+ + + + + +
| 3 2 |
+ + + + + +
| 3 |
+ + + + + +
| |
+ + + + + +
| 2 2 7|
+ + + + + +
| 3 |
+ + + + + +
| 2 7 2 |
+--+--+--+--+--+
Поганий вхід.
