The Reversed WorldProblem code: REVERSED |
All submissions for this problem are available.
Given three numbers A, B and C all having N digits, little Johnny needs to write a program to permute the digits of the number C so that the new number is greater than both A and B.
This problem would be so easy if Johnny's teacher didn't require that Johnny's program must be correct in both the real world and the reversed world. What happens once the world is reversed? One thing Johnny knows for sure is that all the numbers are also reversed. The second thing, the "greater than" relation becomes the "smaller than" relation.
For the sake of clarity, we will use aR to denote the number a in the reversed world (for instance, 113R = 311).
Thus Johnny task is now permute the digits of C so that the new number is greater than both A and B. In additional, the reverse of the new number should be smaller than both AR and BR. If there are multiple possible solutions, Johnny needs to find the smallest one.
As usual, please help Little Johnny with his task!
Input
The first line contains a number T (about 10) which is the number of the test cases. Each test case has the following form.
The first line contains N (1 <= N <= 1000000).
The second line contains the number A.
The third line contains the number B.
The fourth line contains the number C.
Each test case's input is separated by a blank line.
Output
For each test case, print the solution in a single line. If there is no solution, print the number -1.
Example
Input: 2 2 12 23 32 3 124 324 335 Output: -1 353
| Date: | 2010-03-11 |
| Time limit: | 3s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
@admin what is N here????
@admin
what is N here????
If you read the problem
If you read the problem carefully, note that the first line says "Given three numbers A, B and C all having N digits" : )
" Johnny needs to find the
" Johnny needs to find the smallest one."
Is that means smallest in the "real world"?
Yes.
Yes.
Can the number begin or end
Can the number begin or end in 0?
same old problem of TLE!
same old problem of TLE!
Are the values of A and B
Are the values of A and B unique? Can they be ever same?
A and B can be any N digit
A and B can be any N digit numbers. There aren't any other restrictions placed on them in the problem statement.
sorry I mean values of A, B
sorry I mean values of A, B and C
Well clearly there aren't any
Well clearly there aren't any restrictions on C either..
Yes, there's no restriction.
Yes, there's no restriction. Numbers can begin or end with 0.
wts TLE?
wts TLE?
TLE means Time limit
TLE means Time limit Exceeded.
can the new C be equal to
can the new C be equal to C??
for example, in the sample i/o, 335 IS greater than 124 and 324 and less than 421 and 423!
The sample output is correct.
The sample output is correct. You have misunderstood the problem, read it again.
I asserted for testcase<=15
I asserted for testcase<=15 and still the assert is false ..So may I am wrong or test cases are > 15
Is number of test cases > 15 ?
There is no exact limit on
There is no exact limit on the number of test cases given here "(about 10)". So I guess it means that on average there are 10 test cases, but some files may contain more than 10 (and even more than 15).
Yes, the average of the
Yes, the average of the number of test cases is about 10, but there's one file that have more than 15 test cases : )
"greater than relation
"greater than relation becomes the smaller than relation". What does this mean? Does it mean 5>6 in the reversed world?
It just means the reverse of
It just means the reverse of your output must be smaller than the reverse of the input numbers (as opposed to greater than).
Thanks Stephen, that sentence
Thanks Stephen, that sentence puzzled me a bit. Finally got it working.
The output should be -1 if
The output should be -1 if A,B,C all are same, isn't it?
The output should be -1 if
The output should be -1 if A,B,C all are same, isn't it?
Hey , the output should be -1
Hey , the output should be -1 if A, B, C all are same , isn't it?
The output should be -1 if
The output should be -1 if A,B,C all are same, isn't it?
Please figure it out yourself
Please figure it out yourself as it is part of solving the problem.
My program gives the correct
My program gives the correct output , but the judge still shows WA. Is the judge output correct ?
The judge output is correct.
The judge output is correct. Yours is not.
Question All numbers (even if
Question
All numbers (even if they start with zero) will have "N" digits. So if N = 4, "21" will be represented as "0021"? Also, this is true for the output? If "21" is the best answer for C, I output "0021"?
You have to output a
You have to output a permutation of the digits given you to in C. If C is 2010, then 0021 is a permutation of those digits. It doesn't make sense to say 'if 21 is the best answer', since 21 is not a permutation of those digits.
made it .... just about a day
made it .... just about a day late :P