For debugging the question

simple or palindromes.cpp

// https://codeforces.com/contest/569/problem/C
/*
on test case 6 4, the value inside if() is false still it is executed, leading to wrong answer. 
can be verified by un-commenting line 44. fails when low=152, high = 182
*/


#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define eb emplace_back
const int N=1e6+3;
#define deb(x) cout << '>' << #x << ':' << x << " ";

vector<ll> v(N,0),vi;
static int numPalindrome(int num);
static int constructPalindrome(int palPrefix, int numLength);


void seieve(){
    for(int i=2;i<N;i++){
        if(v[i]==0){
            for(int j=i+i;j<N;j+=i)
                v[j]=1;
            vi.eb(i);
        }
    }
}


int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll i,j,k,p,q,n,m,ans=0,a,b;
cin>>p>>q; seieve();
ll low=0,high=N;
while(low<high){
    ll mid=(low+high+1)/2;
    ll pi=upper_bound(vi.begin(), vi.end(),mid)-vi.begin();
    ll rub=numPalindrome(mid)-numPalindrome(0);
/*    if((q*pi)<=(p*rub))   low=mid;
    else high=mid-1;*/
    if(q*pi>p*rub)  high=mid-1;
    else low=mid;
    // cout<<low<<" "<<high<<" : "<<pi<<" "<<rub<<" - "<<(q*pi>p*rub)<<"\n";
    // deb(low);   deb(high);  deb(pi);    deb(rub);   cout<<endl;
}
cout<<low<<"\n";
    return 0;
}


static int numPalindrome(int num){
    int numLength = 0;
    int palLength = 0;
    int palPrefix = 0;
    int temp      = 0;
    int i         = 0;

    for (numLength=0, temp = num; temp != 0; temp /= 10)
        numLength++;

    palLength = (numLength+1) / 2;
    palPrefix = num;
    for (i=0; i < numLength - palLength; i++)
        palPrefix /= 10;

    if (constructPalindrome(palPrefix, numLength) > num)
        palPrefix--;

    palPrefix *= 2;
    if (numLength & 1) {
        int adjustment = 1;
        for (i=1;i<palLength;i++)
            adjustment *= 10;
        palPrefix -= (palPrefix/2 - adjustment + 1);
    } else {

        int adjustment = 1;
        for (i=0;i<palLength;i++)
            adjustment *= 10;
        palPrefix += (adjustment - 1 - palPrefix/2);
    }
    return palPrefix;
}


static int constructPalindrome(int palPrefix, int numLength){
    int front = palPrefix; 
    int back  = 0;        

    if (numLength & 1)
        palPrefix /= 10;

    while (palPrefix != 0) {
        int digit = palPrefix % 10;

        palPrefix /= 10;
        back       = back * 10 + digit;
        front     *= 10;
    }
    return front + back;
}