ZOJ Problem Set - 3301
The game "Stand on a Piece of Paper" is to ask a group of people to stand on a small piece of paper. They are considered standing steadily if they can stand on the paper without touching anything else for 5 seconds. Once they succeed, the area of paper will be halved and the game will continue until they fail. The group that can stand steadily on the smallest piece of paper is the winner.
In order to win in this game, the leader of your group thought out a good idea. For there was even number of people in your group, he wanted each two people to make a small group. The two persons in a small group must stand in the opposite position hand in hand with their toes touching the paper. This strategy asked the difference of weights of the two people of each small group to be as small as possible. He wanted to minimize the total differences of weights of each each small group. However, he didn't know how to divide the group to achieve this goal. So he ask you for help.
For each test case, the first line contains an even integer n not exceeding 10000, indicating the number of people in your group. Then n integers in the range of [1, 10000] follow, indicating the weight of each people.
Output n/2 lines for each test case. Each line contains two integer seperated by one space, telling which two people to make a small group. The people are numbered from 1 to n in the input order. If there are more than one ways to minimize the total differences, output any one. Seperate two test cases with an empty line.
4 3 8 7 8 8 2 6 7 4 5 3 6 9
1 3 2 4 1 6 2 7 3 8 4 5
Author: GUAN, Yao
Source: ZOJ Monthly, February 2010