Rearranging DigitsProblem code: ARRANGE2 |
All submissions for this problem are available.
A number X is called Permut number if X and 2X ( both without leading zeroes ) have same number of digits and are permutations of each other. Given A and B, find the number of Permut numbers >= A and <= B.
Note : X is called permutation of Y if every digit ( 0 - 9 ) occurs same number of times in both the numbers ( maybe at different positions ).
Input :
The first line contains the number of test cases T. T lines follow, containing two integers A and B.
Output :
Output T lines, one for each test case containing the desired answer for the corresponding test case.
Sample Input : 2 1 100 499875921 499875921
Sample Output : 0 1
Constraints : 1 <= T <= 10000 1 <= A <= B <= 10000000000 (10^10)
| Author: | syco |
| Date Added: | 5-05-2010 |
| Time Limit: | 1 sec |
| Source Limit: | 5000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
how are 1 and 100 permut
how are 1 and 100 permut numbers?
read the statement carefully.
read the statement carefully.
499875921 499875921 how is
499875921 499875921
how is it possible to have a permut number between two equal numbers
if x is 499875921 then 2x=999751842 is out of the range
how is this possible
@ Naruto read the statement
@ Naruto
read the statement carefully.
"Given A and B, find the number of Permut numbers >= A and <= B."
The problem is to calculate
The problem is to calculate the number of permute numbers between A and B "Inclusive of A and B"
and X has to be in that range. 2*X need not be in that range, If you read the definition carefully you will realise taht.
what us unit of source limit?
what us unit of source limit? bytes, loc, kloc, or KB?
btw ... 999751842 IS in
btw ... 999751842 IS in range. (range is 10^10 ... greater than what a normal int can hold)
"Your solution is too long
"Your solution is too long for this problem, the limit is 5000 bytes!"
My program is about 6K , don't save any calculated data.
What a pity!
i got time limit exceeded,
i got time limit exceeded, does that mean that my code worked correctly too much time ??
Condition for permutation
Condition for permutation should be checked including leading zeros or excluding leading zeros ........?
@karthik time limit exceeded
@karthik
time limit exceeded doesn't mean ur code worked correctly.
Have you browsed through the FAQ ?
@Atul read the first line carefully
hey i am using java n i am
hey i am using java n i am getting the same compilation error every time that the main function does not exist when it does..i have checked it a hundred times..i am not getting how to remove this error..can someone help me..
@sumeet : check if you have
@sumeet : check if you have used any package in your program, if yes remove the package, you wont get the compilation error. The error you are getting now is because your main() is not visible to the compiler.
is the time limit given here
is the time limit given here is for compilation or execution?
@Karteek its for execution
@Karteek its for execution
No one is able to submit it
No one is able to submit it in java.
@ admin, is there anything wrong...does java also has time limit of 1s ???????????
@sumeet and all other JAVA
@sumeet and all other JAVA users. NAME YOUR PROGRAM AS "Main".
Name is 'Main' only.
Name is 'Main' only.
Java has a time limit of 2
Java has a time limit of 2 seconds.
Finally!!! Got thru the time
Finally!!! Got thru the time limit :D
Why am I getting compilation
Why am I getting compilation error full of a page when I submit?It work fine in my computer.Something's screwed up.
FAQ
FAQ
Time limit is too strict , my
Time limit is too strict , my program is running in 1.2 sec for 10000 cases :(
phew.. got ACpted finally.
phew.. got ACpted finally.
please post the
please post the editorials....
I submitted different
I submitted different solutions to this problem atleast 100 times but every time I got TLE.
My program in C took 0.9s for the test case 1 10000000(ie. 10^7).
How can I get my program to work under 1s for the test case 1 10^10(ie. the worst case)?
Can anyone plz help.
eagerly waiting for the
eagerly waiting for the editorials.... in the meanwhile itd be very nice if someone could give some hints about this problem..
you can pre-generate all the
you can pre-generate all the possible numbers between 1 - 10^10 using optimized brute force (450972 all possible numbers) then use binary search for each test case to find number of entries between a given range....this gave me TLE many times but with different optimizations I finally managed to get it AC. :).
the time limit 4 this problem
the time limit 4 this problem was very harsh ... my 1st implementation was using stl set to store the pre-generated permut numbers .... that timed out.... finally had to resort to plain old arrays,quicksort and binary search :)
^ for me even that failed , i
^ for me even that failed , i must've been using wrong way to move through the permutations.
Since the contest editorial doesn't seem to say anything about that , i wonder what permutation technique should we have used once we knew the digits we want to permute.
here's the closest i could get to a solution : http://pastebin.com/tL2UT0w9