eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Кубик-змейка

Кубик-змейка

Кубик-змейка - это механическая головоломка, состоящая из \textbf{n^3} кубиков \textbf{1}×\textbf{1}×\textbf{1}, через которые проходит эластичный шнур. Соседние кубики на шнуре касаются одной гранью и могут свободно вращаться друг относительно друга по оси, перпендикулярной этой грани. Каждые три идущих подряд кубика образуют либо прямую линию, либо угол в \textbf{90} градусов. Согнуть прямой отрезок змейки в угол или распрямить угол в прямой отрезок нельзя; можно лишь при помощи поворотов выбрать, в какую из четырёх сторон змейка поворачивает на каждом углу. Цель - собрать из этой змейки большой куб \textbf{n}×\textbf{n}×\textbf{n}. Пример змейки показан на рисунке. \includegraphics{https://static.e-olymp.com/content/fa/fa5c225e2e380f3eaa74c66cf84d79a5f48bb238.jpg} Конечно, не из любой змейки можно собрать куб - для этого необходимо, как минимум, чтобы все прямые куски змейки состояли не более чем из \textbf{n} кубиков. Будем задавать змейку последовательностью длин её прямых кусков, точнее, последовательностью расстояний между центрами первого и последнего кубиков в каждом прямом куске. Например, змейка, показанная на рисунке, задаётся слева направо следующим образом: \textbf{2 1 1 2 1 2 1 1 2 2 1 1 1 2 2 2 2}. В этой задаче предлагается решить обобщённую версию этой головоломки. Дана змейка из \textbf{l}×\textbf{w}×\textbf{h} клеток. Уложите её в прямоугольный параллелепипед размера \textbf{l}×\textbf{w}×\textbf{h} клеток или выясните, что это невозможно. \InputFile В первой строке входного файла записаны через пробел четыре целых числа - \textbf{l}, \textbf{w}, \textbf{h} и \textbf{m} (\textbf{1} ≤ \textbf{l}, \textbf{w}, \textbf{h} ≤ \textbf{4}; \textbf{0 }≤ \textbf{m }< \textbf{lwh}); здесь \textbf{l}, \textbf{w} и \textbf{h} - это длина, ширина и высота параллелепипеда, соответственно, а \textbf{m} - количество звеньев в змейке. Во второй строке записаны \textbf{m} целых чисел через пробел - последовательность положительных длин прямых кусков змейки. Гарантируется, что данная змейка содержит ровно \textbf{l}×\textbf{w}×\textbf{h} кубиков. \OutputFile Если данную змейку в параллелепипед уложить невозможно, выведите "\textbf{Bit}" в первой строке выходного файла. В противном случае в первой строке входного файла выведите "\textbf{Baba}", а в следующих \textbf{l}×\textbf{w}×\textbf{h} строках - координаты кубиков змейки, по три числа на строке. Змейку следует выводить с того же конца, с которого она начинается во входном файле. Числа \textbf{x_i}, \textbf{y_i} и \textbf{z_i} в \textbf{(i+1)}-й строке должны удовлетворять неравенствам \textbf{0} ≤ \textbf{x_i} < \textbf{l}, \textbf{0} ≤ \textbf{y_i} < \textbf{w} и \textbf{0 }≤ \textbf{z_\{i \}}< \textbf{h}. Кроме того, все кубики параллелепипеда \textbf{l}×\textbf{w}×\textbf{h} должны встретиться в выходном файле по одному разу, в соседних строках должны быть соседние кубики, а повороты должны в точности соответствовать поворотам змейки. Змейка может начинаться и заканчиваться в любом кубике параллелепипеда. Если решений несколько, разрешается выводить любое из них.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
3 3 3 17
2 1 1 2 1 2 1 1 2 2 1 1 1 2 2 2 2
Выходные данные #1
Baba
0 0 0
1 0 0
2 0 0
2 1 0
1 1 0
1 1 1
1 1 2
1 2 2
1 2 1
1 2 0
2 2 0
2 2 1
2 1 1
2 0 1
1 0 1
0 0 1
0 1 1
0 1 0
0 2 0
0 2 1
0 2 2
0 1 2
0 0 2
1 0 2
2 0 2
2 1 2
2 2 2
Автор Ivan Kazmenko