codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

568A.md (1889B)


      1 Source: https://codeforces.com/problemset/problem/568/A
      2 
      3 A. Primes or Palindromes?
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Rikhail Mubinchik believes that the current definition of prime numbers is obsolete as they are too complex and unpredictable. A palindromic number is another matter. It is aesthetically pleasing, and it has a number of remarkable properties. Help Rikhail to convince the scientific community in this!
     22 
     23 Let us remind you that a number is called prime if it is integer larger than one, and is not divisible by any positive integer other than itself and one.
     24 
     25 Rikhail calls a number a palindromic if it is integer, positive, and its decimal representation without leading zeros is a palindrome, i.e. reads the same from left to right and right to left.
     26 
     27 One problem with prime numbers is that there are too many of them. Let's introduce the following notation: π(*n*) — the number of primes no larger than *n*, *rub*(*n*) — the number of palindromic numbers no larger than *n*. Rikhail wants to prove that there are a lot more primes than palindromic ones.
     28 
     29 He asked you to solve the following problem: for a given value of the coefficient *A* find the maximum *n*, such that π(*n*) ≤ *A*·*rub*(*n*).
     30 
     31 Input
     32 
     33 The input consists of two positive integers *p*, *q*, the numerator and denominator of the fraction that is the value of *A* (![](https://espresso.codeforces.com/041bd986f782f4473b6391bc9e8fd014d9ba53f8.png), ![](https://espresso.codeforces.com/33b89d29647f62d25a0dad09f24bb0db3ba22b17.png)).
     34 
     35 Output
     36 
     37 If such maximum number exists, then print it. Otherwise, print "Palindromic tree is better than splay tree" (without the quotes).
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 1 1
     45 ```
     46 
     47 Output
     48 
     49 ```
     50 40
     51 ```
     52 
     53 Input
     54 
     55 ```
     56 1 42
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 1
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 6 4
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 172
     75 ```