<ПРЕД Задача:
СЛЕД>
Задачу решили 536 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Коробки

Time limit: 5 секунд

У Пети накопилось много картонных коробок. Они ему еще послужат службу в будущем, но сейчас он хотел бы от них избавиться -- сдать в камеру хранения. В камере хранения за каждое место берут деньги. Помогите Пете уложить коробки друг в друга так, чтобы плата за их хранения была минимальна.

Известно, что никакие две коробки не поместятся ни в какую другую, если их поставить рядом. Коробка со сторонами x1, x2, x3, x1 >= x2 >= x3, помещается в коробку со сторонами y1, y2, y3, y1 >= y2 >= y3, если

x1 < y1, x2 < y2, x3 < y3.

Вход. Вход начинается с числа коробок N <= 500 , затем следует N строчек, содержащих параметры каждой коробки -- длины её трёх сторон -- три натуральных числа меньше 2 000 000.

Выход. Минимальное число коробок, в которые все остальные можно поместить.

ВХОД #1:
2
1 2 3
4 3 2
ВЫХОД #1:
1
ВХОД #2:
2
1 2 3
2 3 3
ВЫХОД #2:
2
ВХОД #3:
4
3 3 3
4 4 4
5 5 5
2 3 4
ВЫХОД #3:
2

Автор:
Ворожцов Артем

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 3.228.11.9