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 : :

0 0 votes

Article Rating