SPOJ.com - Problem MAX

MAX_NUM - finding maximum possible number

no tags

Given a number n, Find out what max possible number you can make by deleting exactly k digits.

T : number of test cases <= 10^3.

1 <= number of digits in n <= 10^5. (n might contain leading zeros.)

0 <= k <= n

if value of n is equal to k. then just print a new line.

Input

T: number of test cases.

T lines follow each with n and k.

Output

max possible number.

Example

Input:
2
1223 2
8756 2

Output:
23
87

Explanation

Note that left to right order should be maintained. As in the example given answer is 23 not 32.

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 Next >

	praveen123: 2013-05-02 06:48:14 I have updated the problem statement to make it more cleaner, I have also modified the test cases. Three solutions have been accepted. Please give your opinion on the quality of problem and also on the issue of time limit.
	praveen123: 2013-05-02 06:48:14 hi all, First of thank you Alex Anderson for giving me test cases for checking input - output. I had a small bug in the code. when some two digits coincided. So I am changing input and output file now and rejudging all the submission. @:D , if you feel that judge data seems to be correct or may be want to suggest some improvements for the problem, I will really appreciate that. Please make problem visible when all the conflicts are over. Last edit: 2013-02-10 03:13:36
	:D: 2013-05-02 06:48:14 Re praveen123: Pretty much what Robert said. For test cases here my solutions coincide. Could you print some small case where any of us fails?
	Robert Gerbicz: 2013-05-02 06:48:14 My code prints the same answers for that two input. But you can see our code as (here) you are the problem setter. Say n has got L digits; after deleting k digits in every case you have got the same length=L-k. It means that if you want the maximal number you have to start with 9 (if in the number there is a 9 and you can complete the number to have L-k digits), in the 2nd place you will see again 9 in general etc. so for me it is not surprising that you see a lot of consecutive 9's.
	praveen123: 2013-05-02 06:48:14 :D , you are printing out a huge streak of 9's as in the case of Robert. Could tell me your understanding of the problem so that I could see that something is incorrect at logic side or implementation side
	Robert Gerbicz: 2013-05-02 06:48:14 I feel that we are talking about different problem. What is the answer for: 313 1 ? My current code prints 33.

Submit solution!

Added by:	praveen123
Date:	2013-02-09
Time limit:	0.407s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	general