eolymp
bolt
Try our new interface for solving problems
Məsələlər

Triangular Tiling

Triangular Tiling

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Triangular domino is a rhombic figure composed of two equilateral triangles.

Similarly triangular trimino is a trapezoid composed of three equilateral triangles.

Consider a connected area on a triangular grid composed of unit triangles. You have to detect whether it is possible to tile the area with triangular dominoes and triminoes. Each triangle must be covered by exactly one tiling piece.

Giriş verilənləri

The first line of the input file contains n - the number of triangles in the area (1n500). The following n lines contain coordinates of the triangles. The coordinates are assigned to the triangles as shown on the following picture. Coordinates do not exceed 500 by their absolute values.

Çıxış verilənləri

If the tiling is impossible, output "No solution" at the first line of the output file. In the other case the first line of the output file must contain k - the number of pieces used. Let the pieces be numbered from 1 to k, the second line must contain n integer numbers, for each triangle of the given area output the number of the piece that it is covered by.

Nümunə

Giriş verilənləri #1
15
0 0
1 0
2 0
0 1
1 1
2 1
3 1
4 1
-1 2
0 2
1 2
2 2
-2 3
-3 3
-4 3
Çıxış verilənləri #1
6
1 1 1 2 2 3 3 3 4 4 5 5 6 6 6
Müəllif Andrew Stankevich
Mənbə Andrew Stankevich Contest 32, Petrozavodsk Summer Training Camp, Wednesday, September 3, 2008