Archive

Archive for June, 2015

[URI Online Judge] – 1290 – Very Special Boxes

June 24th, 2015 Comments off

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1290

 

Special Box Company (SBC) is a small family-owned and family-run business which produces decorated carton boxes for wrapping gifts. The boxes are hand-made, produced individually from fine materials. When accepting an order from a client, they always produce a few more boxes than needed, to keep a stock of boxes to be sold in the future, if needed. Over the years their stock has been growing, with boxes all over the place, and they decided they needed to organize it a bit more. They have therefore made a list registering the dimensions of every box in their stock.

SBC has just received an order from a client that must be delivered tomorrow, so there is no time to produce new boxes. The client wants a certain number N of boxes all of the same size; each box will be used to pack one item of dimensions X, Y and Z. As the carton used in the boxes is very thin, you may assume that a box of size (X, Y, Z) would fit perfectly the item the client wants to wrap. If there are not at least N boxes that fit perfectly, the client wants N boxes that fit the items as tightly as possible. The box size that fits the items as tightly as possible is the one which minimizes the empty space when the item is put inside the box. An item can be rotated in any direction to be accomodated inside a box; therefore, a box of size (X, Y, Z) is as good as a box of size (Y, Z, X), for example.

Can you help SBC finding whether they can fulfill the customer order?

Input

The input consists of several test cases. The first line of a test case contains two integers N and M, indicating respectively the number of boxes the client needs to buy (1 ≤ N ≤ 1500) and the number of boxes in the stock list (1 ≤ M ≤ 1500). The second line contains three integers X, Y and Z, representing the dimensions of the item the client wants to wrap (0 < X, Y, Z ≤ 50). Each of the next M lines contains three integers A, B and C representing the dimensions of a box in the stock list (0 < A, B, C ≤ 50). A test case with N = 0 indicates the end of the input.

Output

For each test case in the input your program must produce one line, containing either:

  • the single word ‘impossible’, in case it is not possible to fulfill the client’s order (because there are not at least N boxes of the same size in stock that can contain the item); or
  • one integer V , which specifies the volume of empty space left when one of the N items is packed in one of the boxes chosen.
Sample InputSample Output
1 1
2 4 3
2 3 4
2 6
3 1 3
7 4 7
10 8 2
2 8 10
6 2 9
7 7 4
6 2 9
1 1
3 3 3
1 1 1
0 0
0
99
impossible
solve:

 

 

[URI Online Judge] – 2248 – Internship

June 17th, 2015 Comments off

You got an internship to work as a programmer in the office of your school. As a first task, Dona Vilma, the coordinator, asked you to enhance a program that was developed by the former trainee. This program has as input a list of names and final average of students in a class, and provides the student with the highest average in the class. Dona Vilma want to use the program to reward the best student from each school class. The program developed by the former intern is on the following pages (Pascal program on page 5, C program on page 6, C ++ program on page 7).

As you can see, the program in its current form has a flaw: if there tied students with the best average in the class, it prints only the first student that appears in the list.

Dona Vilma wants you to change the program so that it produces a list of all students in the class who have obtained the highest average, and not just one. Can you help her in this task?

Input

The input consists of several test sets, representing several classes. The first line of a set of tests contains an integer number N (1 ≤ N ≤ 1000) indicating the total number of students in the class. The N following lines contain, each, a pair of integers C (1 ≤ C ≤ 20000) and M (0 ≤ M ≤ 100), respectively indicating the code and the average of a student. The end of input is indicated by a class with N = 0.

Output

For each entry in the class your program should produce three lines in the output. The first line should contain a test set identifier in the format “Turma n”, where n is numbered from 1. The second line should contain the codes of the students who obtained the highest average in the class. The students of codes must appear in the same order of entry, and each must be followed by a blank space. The third line should be left blank. The format shown in no  the sample output below should be followed strictly.

Input SampleOutput Sample
3

1 85

2 91

3 73

5

12300 81

12601 99

15023 76

10111 99

212 99

0

Turma 1

2

Turma 2

12601 10111 212

 

solve: