Codeforces Round 315 Div 2 C

#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

int lastprime = 2;
int lastprimei = 0;

int pi(int n) {
    while (lastprime <= n) {
        while (true) {
            lastprime++;
            bool isprime = true;
            for (int i = 2; i <= (int) ceil(sqrt(lastprime)); i++) {
                if (lastprime % i == 0) {
                    isprime = false;
                    break;
                }
            }
            if (isprime) break;
        }
        lastprimei++;
    }
    return lastprimei;
}

int palidromize(int n, bool even) {
    int result = n;
    if (!even) n /= 10;
    while (n) {
        result *= 10;
        result += n % 10;
        n /= 10;
    }
    return result;
}

int next_palindrome_head = 1;
int next_palindrome_n = 0;
bool next_palindrome_even = false;

int rub(int n) {
    while (true) {
        if (palidromize(next_palindrome_head, next_palindrome_even) > n) {
            return next_palindrome_n;
        }
        next_palindrome_head++;
        double next_palindrome_size = log10(next_palindrome_head);
        if (floor(next_palindrome_size) == next_palindrome_size) {
            if (next_palindrome_even) {
                next_palindrome_even = false;
            } else {
                next_palindrome_even = true;
                next_palindrome_head /= 10;
            }
        }
        next_palindrome_n++;
    }
}

int main() {
    int p, q;
    scanf("%d %d", &p, &q);
    double factor = ((double) p) / q;
    int n = 0;
    while (++n) {
        if (pi(n) > factor * rub(n)) {
            if (n == 1) {
                printf("Palindromic tree is better than splay tree\n");
                return 0;
            }
            printf("%d\n", n - 1);
            return 0;
        }
    }
    return 0;
}