Krzysztof Diks, Marcin Kubica

Tłumaczenie

Building with Blocks

Zadanie

Sześcian jednostkowy (lub krócej sześcian) to sześcian o wymiarach , którego wierzchołki mają całkowite współrzędne. Dwa sześciany są połączone, jeśli mają wspólną ścianę. Trójwymiarowa bryła (lub krócej bryła), to niepusty zbiór sześcianów połączonych ze sobą (patrz rys. 1) Objętość bryły, to liczba tworzących ją sześcianów. Klocek, to bryła o objętości co najwyżej 4. Danych jest dokładnie 12 kształtów klocków (patrz rys. 2). Kolory klocków na rysunku nie mają żadnego znaczenia - mają jedynie polepszyć czytelność rysunku.

Zbiór klocków D nazywamy rozkładem bryły S, jeśli klocki należące do D tworzą w sumie bryłę S oraz żadne dwa klocki należące do D nie mają wspólnego sześcianu.

Napisz program który na podstawie opisów kształtów klocków oraz bryły S, wyznaczy najmniej liczny zbiór klocków będący rozkładem S. Twój program musi wypisać jedynie kształty klocków występujących w rozkładzie - każdy ksztatł tyle razy, ile klocków tego kształtu należy do rozkładu.

Wejście

W plikach wejściowych opisujemy sześciany za pomoca trójek liczb całkowitych x, y i z, będących współrzędnymi wierzchołka sześcianu o najmniejszej sumie współrzędnych x+y+z.

Kształty klocków są opisywane w pliku TYPES.IN. Treść tego pliku jest taka sama dla wszystkich testów i zawiera ona opisy 12 klocków przedstawionych na rys. 2 (w kolejności ich numeracji). Każdy klocek jest opisany w kolejnych wierszach w pliku. Pierwszy wiersz zestawu zawiera jedną liczbę całkowitą I, reprezentującą numer kształtu klocka (). Drugi wiersz zawiera objętość V klocka danego kształtu (). Pozostałe V wierszy zawiera po trzy liczby całkowite x, y, z, reprezentujące sześciany tworzące klocek danego kształtu ().

Bryła S jest opisana w pliku BLOCK.IN. Pierwszy wiersz tego pliku zawiera objętość V bryły S (). Pozostałe V wierszy zawiera po trzy liczby całkowite x, y, z, reprezentujące sześciany tworzące bryłę ().

Wyjście

Plik wyjściowy nazywa się BLOCK.OUT. Pierwszy wiersz tego pliku powinien zawierać jedną liczbę całkowitą M, będącą minimalną liczbą klocków, na które można rozłożyć zadaną bryłę. Drugi wiersz powinien zawierać M numerów kształtów klocków, na które można daną bryłę rozłożyć. Jeśli możliwych jest wiele odpowiedzi, Twój program powinien wypisać dowolną z nich.

Przykład

1
1
1 1 1 
2
2
1 1 1 
1 2 1 
3
3
1 1 1 
1 2 1 
1 3 1
4
3
1 1 1 
1 2 1
1 1 2
5
4
1 1 1 
1 2 1 
1 3 1
1 4 1 
6
4
1 1 1
1 2 1 
1 1 2
1 2 2
7
4
1 1 1 
1 2 1 
1 1 2
1 1 3
8
4
1 1 1
1 2 1
1 3 1
1 2 2
9
4

1 2 1 
1 3 1
1 1 2 
1 2 2 
10
4
2 1 1
1 2 1
2 2 1
2 1 2
11
4
1 1 1 
1 2 1
2 2 1
1 1 2
12
4
2 2 1
2 1 2
1 2 2 
2 2 2

18
2 1 1 
4 1 1 
2 3 1
4 3 1
2 1 2
3 1 2
4 1 2
1 2 2
2 2 2
3 2 2 
4 2 2 
2 3 2 
3 3 2
4 3 2
4 2 3
4 2 4
4 2 5
5 2 5

BLOCK.OUT:

5
7 10 2 10 12

Uwaga Powyższe pliki opisują bryłę ``konia'' przedstawioną na rys. 1.