Elephants: the grey area of the animal kingdom, and, according to the internet (although not to science), an area which thinks that we humans are rather cute. Time to solve assignments involving elephants!
Another myth about science is that the bigger they are, the smarter they are. This is, of course, not true, and your mission is to disprove this ridiculous claim. You consequently decide to analyze a collection of elephants to find the largest sequence of elephants whose weights are increasing, but whose IQ measurements are decreasing (never mind how one might even go about measuring an elephant's IQ...).
The input consists of a number of lines, each specifying a test case. Each test case is specified on a single line, starting with the number of elephants \(1 \leq n \leq 1000\), followed by \(n\) pairs of numbers \(1 \leq w_i, iq_i \leq 10000\) for each elephant \(1 \leq i \leq n\) that describe that elephant's weight and IQ value. A line with \(n = 0\) marks the end of the input.
For each input instance, output the length of the longest sequence of elephants such that their weight strictly increases and their IQ value strictly decreases.
The following sample input would be provided on two lines, but are split up here to increase readability. Each paragraph represents what would otherwise be specified on a single line.
9 6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900 0
Please log in to submit your solution.
|Average test runtime||0.39|
|Points (changes over time)||10|
|Tried by||5 users|
|Solved by||3 users|