{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\"text/css\"\u003e\r\nh1,h2,h3,h4,h5,h6{margin-bottom:0;}div.textBG p{margin: 0 0 0.0001pt;}\u003c/style\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\r\n\tSome people think that the bigger an elephant is, the smarter it is. To disprove this, you want to take the data on a collection of elephants and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the IQ\u0026#39;s are decreasing.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThe input will consist of data for a bunch of elephants, one elephant per line, terminated by the end-of-file. The data for a particular elephant will consist of a pair of integers: the first representing its size in kilograms and the second representing its IQ in hundredths of IQ points. Both integers are between 1 and 10000. The data will contain information for at most 1000 elephants. Two elephants may have the same weight, the same IQ, or even the same weight and IQ.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tSay that the numbers on the \u003cspan data-scayt_word\u003d\"i-th\" data-scaytid\u003d\"1\"\u003ei-th\u003c/span\u003e data line are \u003ctt\u003eW[i]\u003c/tt\u003e and \u003ctt\u003eS[i]\u003c/tt\u003e. Your program should output a sequence of lines of data; the first line should contain a number \u003ctt\u003en\u003c/tt\u003e; the remaining \u003ctt\u003en\u003c/tt\u003e lines should each contain a single positive integer (each one representing an elephant). If these \u003ctt\u003en\u003c/tt\u003e integers are \u003ctt\u003ea[1]\u003c/tt\u003e, \u003ctt\u003ea[2]\u003c/tt\u003e,..., \u003ctt\u003ea[n]\u003c/tt\u003e then it must be the case that\u003c/p\u003e\r\n\u003cpre\u003e\r\nW[a[1]] \u0026lt; W[a[2]] \u0026lt; ... \u0026lt; W[a[n]]\r\n\u003c/pre\u003e\r\n\u003cp\u003e\r\n\tand\u003c/p\u003e\r\n\u003cpre\u003e\r\nS[a[1]] \u0026gt; S[a[2]] \u0026gt; ... \u0026gt; S[a[n]]\r\n\u003c/pre\u003e\r\n\u003cp\u003e\r\n\tIn order for the answer to be correct, \u003ctt\u003en\u003c/tt\u003e should be as large as possible. All inequalities are strict: weights must be strictly increasing, and IQs must be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one.\u003c/p\u003e\r\n\u003cp\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003ch2\u003e\r\n\tSample Input\u003c/h2\u003e\r\n\u003cpre\u003e\r\n6008 1300\r\n6000 2100\r\n500 2000\r\n1000 4000\r\n1100 3000\r\n6000 2000\r\n8000 1400\r\n6000 1200\r\n2000 1900\r\n\u003c/pre\u003e\r\n\u003ch2\u003e\r\n\tSample Output\u003c/h2\u003e\r\n\u003cpre\u003e\r\n4\r\n4\r\n5\r\n9\r\n7\r\n\u003c/pre\u003e"}}]}