Question

Given a sequence a1, a2, ..... an, of positive integers, a subsequence b1, b2, ...bm of it is said to be a ski sequence if there is a number kbk+1...bm. Thus, bk is the maximum number, and must not be in either end (there must an increasing part up to k and a decreasing part after k). For example, in the sequence 1, 2, 10, 3, 7 , 4, two ski sequences are 1,10,3 and 1,2,7,4. The longest ski subsequence is 1,2,10,7,4 The Input consists of N sets of two positive integers each. From these sets, a derived sequence is formed using the following rule Rule for forming derived sequence If both the integers given are odd, the maximum of this is taken in the derived sequence. If one of them is odd and one of them is even, the even number is taken in the derived sequence. If both are even, the minimum of the two numbers will be taken in to the derived sequence. The objective is to find the length of the longest Ski subsequence of the derived sequence. Input The first line of the input has a positive integer N which is the number of sets of integers in the input. Each of the next N lines consists of two (not necessarily distinct) comma separated positive integers. Output The output is the length of the longest Ski subsequence of the derived sequence. If no ski subsequence exists, the output should be the word Impossible. Constraints N<=50 Integers in sets<=10000

Answer 1

of positive integers, a subsequence b1, b2, ...bm of it is said to be a ski sequence if there is a number kbk+1...bm. Thus, bk is the maximum number, and must not be in either end (there must an increasing part up to k and a decreasing part after k). For example, in the sequence 1, 2, 10, 3, 7 , 4, two ski sequences are 1,10,3 and 1,2,7,4. The longest ski subsequence is 1,2,10,7,4 The Input consists of N sets of two positive integers each. From these sets, a derived sequence is formed using the following rule Rule for forming derived sequence If both the integers given are odd, the maximum of this is taken in the derived sequence. If one of them is odd and one of them is even, the even number is taken in the derived sequence. If both are even, the minimum of the two numbers will be taken in to the derived sequence. The objective is to find the length of the longest Ski subsequence of the derived sequence. Input The first line of the input has a positive integer N which is the number of sets of integers in the input. Each of the next N lines consists of two (not necessarily distinct) comma separated positive integers. Output The output is the length of the longest Ski subsequence of the derived sequence. If no ski subsequence exists, the output should be the word Impossible. Constraints N<=50 Integers in