π(n) ≤ A·rub(n) = π(n) ≤ (p/q)·rub(n)

now given , 1/42 <= A <= 42/1 or , 1/42 <= p/q <= 42/1

so , if we set A = 42/1 ( largest input value ) , than we will find the upper bound for n .

now A = 42/1 or , p/q = 42 /1 so , p = 42 , q = 1

now , let you think 1st n = 10^7 . than run your code by giving input p = 42 , q = 1 . If you find that answer is equal n , than you need to increase the value of n . Next n = 3*10^7 . If you find that this time answer is not equal n , so you can decrease the value of n , Like binary search .

Another thing , don't use double for A . You can calculate value by q.π(n) ≤ p.rub(n) . For calculation use long long .

Thanks .

Your task: q*pi(n)<=p*rub(n). But, at maximum example: pi(n)<=42*rub(n).

If a number is palindrome, first half must be equal to second half, which means that we divide numbers in two parts and check them. Every number has it unique mirror inverse (i.e. 562 -> 265). This means that for every number we can easily calculate how many palindrome numbers less than our number exist.

Take look at number 10000000=10^7, but at first better to look at 10^6. 10^6 has odd number of digits.

100 | 0 | 000, 999 | 9 | 999.

Since there are 999 numbers that are palindrome, and digit in middle doesn't have impact on other digits, we can take every digit in the middle.

99 | 8 | 99, 99 | 7 | 99... 85 | X | 58... 1 | X | 1, where X stands for digit.

So for every palindromic number (99 of them smaller than 100), we have to multiply with 10 (10 possible digits in the middle), and add one digit numbers (1, 2, ... 9) and two digits numbers (11, 22, ... 99). So rub(10^6)=99*10+18=1017.

Then get back to our number 10^7; 1000 | 0000 It obviously isn't palindrome. So we take smaller number. We can take 999

999 | 999, 998 | 899, 997 | 799... 3 | 3, 2 | 2, 1 | 1.

And one more thing, since 10^6 is less than 10^7 we can take all palindromic numbers less than it, so we include rub(10^6) for our rub(10^7).

And get back to starting formula: pi(10^7)<=42*rub(10^7). Which obviously isn't, so 10^7 is high bound, we must decrease it. But it is enough.

It was just my logic. There is no need to calculate all of that. Just bruteforce all 10^7 numbers and if it is palindrome (simple check) add 1 to rub, and if it is a prime, add 1 to pi. Better option is to precalc prime numbers with sieve.

http://mirror.codeforces.com/contest/569/submission/12532350