All submissions for this problem are available.
You have been freelancing for the military building their software. Suddenly you are woken up early to be informed that accidently Missiles have been launched all over the area by your neighbouring country and they have informed you the exact heights at which they are flying so that you can take them down.
You are now required to reprogram the missile system to take down these missiles. However you remember that due to budget cuts the current missile system is designed such that the next missile can be fired at a height greater than the previous one only and not below it.
For e.g if missiles are flying at heights 1,6,2,3 and you counter the first missile at height 1 followed by the next missile at height 6, then you cannot fire missiles lower than height 6 and thus missiles 2 and 3 go uncountered.
Your task is to program a software which takes the altitutes and calculates the maximum number of missiles that can be countered for a given number of missiles flying at various heights in order of their strike time. You also need to provide the missile numbers that are to be countered in their serial order.
The input begins with an integer number of test cases followed by an empty line after which each new line is an integer representing the altitude of the missile. At the end of each case their should be a blank line.
The output for each test case comprises of an integer N in the first line which is the number of missiles that can be countered. This is followed by N number of lines each specifying the altitude at which the missile was shot down in sequence.
Input: 1 1 6 2 3 5 Output: 4 1 2 3 5
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions