Chimney Service

Time limit: 1.8s Memory limit: 256MB Input: Output:

Giorgio is always on the lookout for new business opportunities. Today, he acquired a bankrupt company that used to deal with industrial construction material. As soon as he made the purchase, he went into the warehouse and noticed that there were NN perfectly preserved “chimney parts”. A chimney part is, essentially, a pipe (or tube) made of concrete that is characterized by two diameters, AA and BB, one for each open side of the pipe, and a length LL.

By combining these chimney parts, Giorgio can build and sell chimneys to nearby industries. As you might know, in order to build a functional chimney, the structure should be getting progressively narrower towards the top. This is essential in order for the steam or smoke to naturally flow upward, instead of creating air pockets and stagnating. Furthermore, two chimney parts can be combined together only if they perfectly match: the larger diameter of a part should be exactly equal to the smaller diameter of the next part, otherwise they would leave openings for the smoke. The total length of a chimney is given by the sum of the LL values of its parts.

Giorgio wants to get rid of all the chimney parts. Thus, he decided to build several different chimneys, while ensuring that all of them are high enough so that they can all be of interest to some possible buyers. In more practical terms, Giorgio wants to combine the chimney parts into a set of chimneys (no matter how many) such that the shortest chimney is as long as possible.

Input data

The first line contains the only integer NN, the number of chimney parts. The next NN lines contain three integers each that describe the ii-th chimney part: AiA_i, BiB_i, and LiL_i.

Output data

The first line of the output should contain an integer CC: the number of chimneys you have assembled. Then, 2C2 \cdot C lines should follow. Two consecutives lines describe how a chimney is formed: the first one should contain an integer kk representing the number of chimney parts used for assembling that chimney, and the second one should contain kk integers, the indexes of the parts used.

Constraints and clarifications

  • 1N10 0001 \leq N \leq 10 \ 000.
  • 1Ai<Bi100 0001 \leq A_i < B_i \leq 100 \ 000 for each i=0N1i = 0 \dots N - 1.
  • 1Li1091 \leq L_i \leq 10^9 for each i=0N1i = 0 \dots N - 1.
  • Note that a single chimney part is already by itself a valid chimney
  • The description of chimneys in the output should follow the assembling order (increasing order of diameters): the first index refers to the part on top of the chimney, and so on.

Scoring

Your program will be tested against several test cases grouped in subtasks. Your score on a subtask will be equal to the minimum score for one of its testcases multiplied by the value of the subtask. Your score on a test case will be zero if the output does not represent a valid set of chimneys, using exactly once every chimney part in the input. If the output is a valid set of chimneys, let SoutS_{out} be the minimum length of a chimney among them, and SrefS_{ref} be the minimum chimney length in a reference solution (not necessarily optimal). Your score on a test case will be 11 if SoutSrefS_{out} \geq S_{ref}, or SoutSref\frac{S_{out}}{S_{ref}} otherwise.

# Score Constraints
1 0 Examples
2 7 All the values of AA are distinct. All the values of BB are distinct.
3 18 All the values of BB are distinct.
4 27 N15N \leq 15
5 16 Li=1L_i = 1 for each i=0N1i = 0 \dots N - 1.
6 32 No additional limitations.

Example 1

stdin

2
4 5 4
3 4 7

stdout

1
2
1 0

Explanation

In the first sample case, represented in the following picture, we can assemble the two parts to form one chimney placing the one at index 11 at the bottom, and the one at index 00 at the top.

Example 2

stdin

3
4 5 4
3 4 7
1 4 10

stdout

2
2
1 0
1
2

Explanation

In the second sample case we have the same two parts as in the first example and an extra one. Unfortunately, the last one cannot be combined with the others, which means that we need to create a smaller chimney just with it.

Log in or sign up to be able to send submissions!