Problem G
Tall Towers

Highly aesthetic tower of height 5

You are very well aware of the saying “When life gives you blocks, make towers!”. So, you decide to do exactly that.

You have $n$ blocks of size $l_ i \times w_ i \times 1$ (that is, the height of each block is 1 unit). You want to completely use up all these blocks such that the average height of towers is as high as possible. Towers are made in the usual way: by stacking up blocks one on top of the other.

Of course, you have an eye for beauty, so just any random stack of blocks does not count as a tower for you. For every block in a tower (except the bottom-most block), you wish to ensure that it is “just the right amount” smaller than the block below it. More precisely, you can put block j on top of block k if and only if $x \cdot l_ k \leq l_ j \leq y \cdot l_ k$ and $x \cdot w_ k \leq w_ j \leq y \cdot w_ k$. You are guaranteed that $ 0 < x \leq y < 1 $.


The first line of the input contains three space separated positive integers: the number of blocks $n$ ($1\leq n \leq 200 $), $x\prime $ ($1\leq x\prime < 10^6 $), and $y\prime $ ($1\leq y\prime < 10^6 $) where $x = \frac{x\prime }{10^6}$ and $y = \frac{y\prime }{10^6}$. You are guaranteed that $ x \leq y $. Then follow $n$ lines, each describing a block. The $i^{th}$ line contains two space separated positive integers $l_ i$ and $w_ i$ corresponding to the length and width of the $i^{th}$ block. You are guaranteed that $ 1 \leq l_ i, w_ i \leq 10^9$.


Print a single integer, the number of towers in an arrangement of blocks that maximizes the average height of the towers. It can be proven that the answer is unique.

Sample Input 1 Sample Output 1
2 1 999999
5 4
1 3
Sample Input 2 Sample Output 2
8 1 999999
1 16
2 15
3 14
4 13
5 12
6 11
7 10
8 9
Sample Input 3 Sample Output 3
8 500000 500000
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
CPU Time limit 1 second
Memory limit 1024 MB
Nikil Selvam
Source CodeSprint LA 2021
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in