Find the least number for which Proportion of Neutral Numbers is at least n/m
Increasing, Decreasing & Neutral Numbers
An increasing number is a number in which values of digits increase when we go from left to right; for example,123455 .
Similarly a decreasing number is a number in which values of digits decrease when we go from left to right; for example,54110 .
We shall call a positive integer that is neither increasing nor decreasing a “neutral” number; for example, 151212 .
The count of Neutral numbers increases and by the time we reach 21780 the proportion of neutral numbers >= 90%.
Find the least number for which the proportion of neutral numbers is at least n/m .
Explanation
Input Format
First line contains an integer denoting the number of test cases.
Each of the following lines contain two integers.
Constraints
1<=T<10^4
1<=n<m<=10^5
Output Format
For each of T test cases print one line containing a single integer – the answer to a problem.
Sample Input
2
1 2
90 100
Sample Output
538
21780
Time Limit:3.0 sec(s) for each input file.
Memory Limit:256 MB
Source Limit:1024 KB
SOURCE CODE : :
import itertools def compute(a,b): count = 0 for i in itertools.count(1): s = str(i) t = "".join(sorted(s)) if s != t and s[::-1] != t: count += 1 # i is neutral if count * b == a * i: return str(i) for i in range(0,input(),1): a=map(int,raw_input().strip(' ').split()) print(compute(a[0],a[1]))
OUTPUT : :
2 1 5 175 80 100 4770