ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Junior Contest, October 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Coat Transportation

Time limit: 1.0 second
Memory limit: 64 MB
The famous fraud Vovan decided to steal some fur coats for the winter. He went to the nearest winter clothes shop and saw that there were N mink coats on sale. Vovan liked all of them so much that he decided to steal them all. To avoid any suspicion, he decided to put on the fur coats and then carry them out of the shop. Furthermore, Vovan noticed he could carry out more than one fur coat at a time by putting on several coats one over another. A larger coat can be put on over a smaller one if the size of the larger coat exceeds the size of the smaller coat by more than R. Usually Vovan wears a T-shirt, so he can put on a fur coat of any size as the first one. Vovan wants to carry out all the coats in a minimal number of trips to the shop. You are to help Vovan with his evil plan.


The first line contains the integers N and R separated by a space (1 ≤ N ≤ 105; 0 ≤ R ≤ 109). The second line contains N non-negative integers representing the sizes of the coats in the shop. The sizes are given in non-decreasing order. The numbers are separated by spaces and don't exceed 109.


In the first line output the minimal number of trips to the shop K. Each of the next K lines should contain the description of a trip: the number of coats Vovan should carry out during this trip, followed by the numbers of these coats in increasing order. The coats are numbered from 1 to N in the same order they are given in the input. Separate numbers by a single space. If there are many solutions, you may output any one of them.


8 3
1 2 3 5 7 10 12 13
2 3 6
3 1 4 7
3 2 5 8
Problem Author: Alexander Kokovin
Problem Source: USU Junior Contest, October 2007
To submit the solution for this problem go to the Problem set: 1579. Coat Transportation