AIOC Banner

Problem: Leaf Blower

Want to try solving this problem? You can submit your code online if you log in or register.


Leaf Blower

Output Only Task

Input File: leaf.k.in
Output File: leaf.k.out

Input files available in zip file for Linux or for Windows.

Autumn has arrived, and the leaves are falling from the trees onto your tiled courtyard. Although the leaves are pretty, your courtyard is prettier, and so you decide to clean the leaves away.

Your courtyard is formed from a grid of tiles, as illustrated below; these tiles can be described by (x,y) coordinates. The leaves have fallen into n piles, each on a different tile.

You have a leaf blower that allows you to move these piles around. The leaf blower can move a pile of leaves horizontally or vertically from one tile to another. If any two piles meet, they combine to form a single (larger) pile, which you can continue to blow around as before.

You wish to combine the leaves into a single pile using as few pile movements as you can. One pile movement involves blowing a pile of leaves (of any size) to an adjacent tile.

As an example, consider the figure below. The leaves begin in four piles, located in tiles (1,2), (2,4), (3,5) and (5,3), as seen in the first diagram.

By following these steps, a total of 2+3+3=8 pile movements are used, which is the smallest number possible.

You are not required to find the best possible solution. Instead you must simply use as few pile movements as you can. Your solution will be compared against other solutions, and better solutions will score more points. See the Scoring section for details.

Input

You are given ten input files leaf.k.in (1 <= k <= 10).

The first line of each file contains the single integer n, giving the number of piles (2 <= n <= 500). Following this are n lines, each of the form x y, giving the coordinates of a single pile of leaves. All x and y coordinates are integers in the range 1 <= x,y <= 1000.

Output

For each input file leaf.k.in, you must produce an output file leaf.k.out that contains your solution.

Each solution file should contain one line for each pile movement, given in order from the first movement to the last. Each line should be of the form x y p q, which indicates that the pile at tile (x,y) is blown to the tile (p,q). These two tiles must be either horizontally or vertically adjacent, and all tile coordinates must remain in the range 1 <= x,y,p,q <= 1000.

Sample Input

4
1 2
2 4
3 5
5 3

Sample Output

3 5 3 4
2 4 3 4
3 4 3 3
5 3 4 3
4 3 3 3
3 3 2 3
2 3 1 3
1 3 1 2

Scoring

There is no "best solution" that you are required to achieve. Instead, your score for each input scenario will be determined relative to the other contestants whom you are competing against (as well as one of the judges' solutions).

For each input scenario, the contestant who finds a valid solution using the fewest pile movements will be identified. Suppose that this contestant uses p pile movements in total. Assuming your output also contains a valid solution, it will be scored as follows:

For example, consider an input scenario for which the best solution found by any contestant uses 100 pile movements. The scoring for a valid solution would be as follows:

Movements 100 102 104 106 108 110 140 170 200 300 900
Score 100% 90% 80% 70% 60% 50% 37% 23% 10% 10% 10%

A solution that makes an invalid movement (for instance, moving to a non-adjacent square, or moving outside the allowed coordinate range of 1..1000) will score zero. Likewise, a solution that does not combine all of the leaves into a single pile will score zero.

If a solution makes an otherwise legal movement from an empty tile (i.e., there are no leaves to blow from that tile), this irrelevant movement will be silently ignored (but will add to your total number of pile movements).

Submitting for an Output Only Task

To submit your output files, you must do the following:

The website will look inside the zip file and ensure that the output files are named correctly, although it will not check the formatting or layout of these files.

If you resubmit a different zip file, the old zip file will be deleted. For instance, suppose you submit a zip file with solutions to the first five scenarios, and later on you find a solution to the sixth. Your new submission must contain all six output files, since when you submit your new solutions the old ones will be thrown away.

Please contact the contact organisers at fario@fario.org if you have any questions about this procedure.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 15 November 2019,  6:39am AEDT