IOI '97 - Cape Town, South Africa

Map Labelling

You are a cartographer's assistant, and have been given the difficult task of writing the names of cities onto a new map.

The map is a grid of 1000×1000 cells. Grid cells coordinates are labelled from 0 to 999 inclusive in the horizontal and vertical direction respectively. Each city occupies a single cell on the map. City names are to be placed on the map in rectangular boxes of cells. Such boxes are called labels.

Figure 1: a city with the four possible positions of its label

The placement of labels must satisfy the following constraints:

1. A city's label must appear in one of four positions with respect to the city as illustrated in figure 1.
2. Labels must not overlap each other.
3. Labels must not overlap cities.
4. Labels must completely fit on the map.

Each label contains all the letters in a city name plus a single space. For each city name the width and height of its letters will be given; the single space has the same size.

Figure 2: a section of a labelled map

The leftmost column of the map has horizontal index 0 and the top row has vertical index 0. Figure 2 shows the top left section of a map for the cities Langa at (0,3), Ceres at (6,1) and Paarl at (7,3). All the labels are validly placed, but this is not the only valid placement.

Your program must read the locations of the cities on the map, followed by their letter dimensions and names. The program must then place as many labels on the map as it can without violating the constraints above, and output the locations of the labels that have been placed.

Input Format

The input starts with a line containing an integer N giving the number of cities on the map. For each city there is an input line with

• the city's horizontal index X,
• the city's vertical index Y,
• the integer width W for each character of the city name,
• the integer height H for each character of the city name, and
• the city name itself, which consists only of uppercase and lowercase characters from A to Z.

City names are all single words. The number of cities is at most 1000. No city name will be longer than 200 letters.

Output Format

Your program must output N lines. Each line must contain the horizontal index followed by the vertical index of the top left cell of the city's label, separated by a single space. If your program is unable to place a label for a city, it must output "-1 -1" (without quotes) for that city. These lines should be printed in the same order as the cities are given in the input.

Sample Input

Input

Explanation

3
0 3 1 1 Langa
6 1 1 1 Ceres
7 3 1 2 Paarl

N = 3
X = 0, Y = 3, W = 1, H = 1
X = 6, Y = 1, W = 1, H = 1
X = 7, Y = 3, W = 1, H = 2

Sample Output

Output

Explanation

1 4
0 0
8 1

Langa's label is at (1,4)
Ceres's label is at (0,0)
Paarl's label is at (8,1)

Scoring

For each test case:

• Your score will be given as the percentage of city names placed by your program with respect to an excellent solution of the IOI organisers, rounded to the nearest integer percent.
• The minimum score is 0% and the maximum score is 100%.
• If any label violates the constraints, your program will score 0.
• If labels do not match the cities given, your program will score 0.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 32M
Added: Dec 26, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)