Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 12thIOI第二天试题三
发信站: 哈工大紫丁香 (2001年06月14日15:38:49 星期四), 站内信件

i
Building with Blocks
PROBLEM
A unit cube is a 1x1x1 cube, whose corners have integer x, y, and z coordinat
es. Two unit cubes are connected when they share a face. A 3-dimensional soli
d object (solid, for short) is a non-empty connected set of unit cubes (see F
igure 1). The volume
of a solid is the number of unit cubes it contains. A block is a solid with v
olume at most 4. Two blocks have the same type when one can be obtained from
the other by translations and rotations (not reflections). There are exactly
12 block types (see
Figure 2). The colors in the figures only help to clarify the structure of th
e solids; they have no other meaning.
A set D of blocks is a decomposition of a solid S when the union of all block
s in D equals S, and no two distinct blocks in D have a unit cube in common.
Your task is to write a program that, given a description of the block types
and a solid S, determines a smallest set of blocks into which S can be decomp
osed. It only needs to report the types of these blocks as often as they occu
r in the
decomposition.
INPUT
In the input files, we identify a unit cube by a line with three integers x,
y, and z, being the coordinate triple of its corner that minimizes x + y + z.
The input file describing the block types is named TYPES.IN. The contents of
this file are listed below and are the same for all evaluation runs. It conta
ins the descriptions of the 12 block types in Figure 2, sorted on type number
. Each block type is
described by a group of consecutive lines. The first line contains the intege
r I identifying the block type (1 ≤ I ≤ 12). The second line contains the v
olume V of the block type (1 ≤ V ≤ 4). The remaining V lines contain three
integers x, y and z,
each being one unit cube of the block type (1 ≤ x, y, z ≤ 4).
The input file describing the solid is named BLOCK.IN. The first line contain
s the volume V of the solid (1 ≤ V ≤ 50). The remaining V lines contain thr
ee integers x, y, z, each being one unit cube of the solid (1 ≤ x, y, z ≤ 7
).
OUTPUT
The output file is named BLOCK.OUT. The first line must contain one integer M
, being the smallest number of blocks into which the input solid can be decom
posed. The second line lists M type identifiers of the block types into which
 the input solid can
be decomposed. There may be several solutions for each input file, and your p
rogram needs to output only one of them.
EXAMPLE INPUT AND OUTPUT
        TYPES.IN                                BLOCK.IN

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]