kutije
In a toy factory, toys are packed into cylindrical boxes that come in different sizes. The size of the box is described by its height and the radius of its base in millimeters. A shopkeeper who works in storage is pretty bored, but then he remembers his one source of entertainment. His entertainment is based on packing smaller boxes into larger ones. A box which contains smallers boxes can be placed in another larger box. One box can be put into another one only if the radius and the height of the first box are smaller than those of the second box. The shopkeeper finds his job very boring, so he decides to play soccer with his colleagues. To be able to play soccer, he must, as much as possible, decrease the number of boxes in the storage room. He will, for the last time, use his old entertainment (box in box). After packing, the minimum number of boxes should occupy space in the storage room.
In order to check his result, the shopkeeper asks you to find the minimal number of boxes in the end, if you know the sizes of all the boxes.
5
20 30
30 20
40 40
10 30
15 15
Output:2Explanation: There are 5 boxes: the first with radius 20 and height 30, the second with radius 30 and height 20, the third with radius 40 and height 40, the fourth with radius 10 and height 30, and the fifth with radius 15 and height 15. Then it is possible to put the fourth box into the first, then the first into the third, and the fifth into the second. Only 2 visible boxes remain after packing: the second and the third.
However, it's impossible to put all the boxes into one box, so 2 is the result here.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.