Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstring>
- #include <map>
- #include <deque>
- #include <queue>
- #include <stack>
- #include <sstream>
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- #include <math.h>
- #include <cstdlib>
- #include <ctime>
- #include <algorithm>
- #include <vector>
- #include <set>
- #include <list>
- #include <climits>
- #include <cctype>
- #include <bitset>
- #include <iostream>
- #include <iomanip>
- #include <complex>
- #include <sys/time.h>
- using namespace std;
- typedef stringstream ss;
- typedef long long ll;
- typedef pair<int, int> ii;
- typedef vector<ii> vii;
- typedef vector<vector<ii> > vvii;
- typedef vector<string> vs;
- typedef vector<int> vi;
- typedef vector<vector<int> > vvi;
- typedef vector<double> vd;
- typedef long double ld;
- typedef vector<vector<ll> > grix;
- typedef complex<double> point;
- typedef complex<long long> pointINT;
- int dx[] = { -1, 1, 0, 0, 0, 0 };
- int dy[] = { 0, 0, -1, 1, 0, 0 };
- int dz[] = { 0, 0, 0, 0, -1, 1 };
- int DX[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
- int DY[] = { 1, -1, 0, 0, 1, -1, -1, 1 };
- double PI = 3.1415926535897932384626433832795;
- const ll oo = 1e9 + 1;
- const double eps = 1e-6;
- const ll mod = 1234567;
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define sz(v) ((int)v.size())
- #define clr(v, d) memset(v, d, sizeof(v))
- #define polar(r,t) ((r)*exp(point(0,(t))))
- #define length(a) hypot((a).real(),(a).imag())
- #define angle(a) atan2((a).imag() , (a).real())
- #define vec(a,b) ((b)-(a))
- #define dot(a,b) ((conj(a)*(b)).real())
- #define cross(a,b) ((conj(a)*(b)).imag())
- #define lengthSqr(a) dot(a,a)
- #define rotate(v,t) ((v)*exp(point(0,t)))
- #define rotateAbout(v,t,a) (rotate(vec(a,v),t)+(a))
- #define reflect(v,m) (conj((v)/(m))*m)
- #define dist(a,b) (sqrt(pow((a).real()-(b).real(),2.0)+pow((a).imag()-(b).imag(),2.0)))
- #define distsqr(a,b) (pow((a).real()-(b).real(),2.0)+pow((a).imag()-(b).imag(),2.0))
- #define normalize(a) ((a)/length(a))
- #define ccw(a,b,c) (cross(vec((a),(b)),vec((a),(c)))>=0)
- #define collinear(a,b,c) (fabs(cross(vec((a),(b)),vec((a),(c))))<eps)
- #define LSOne(S) (S & (-S))
- ////////////////////////////////////////////////////////////////////////
- //freopen("in.txt","r",stdin);
- //freopen("out.txt","w",stdout);
- bool vis[5000001];
- int prime[5000001];
- int pal[5000001];
- bool ok(int num) {
- string s = "";
- while (num) {
- s += (num % 10);
- num /= 10;
- }
- for (int i = 0; i < sz(s) / 2; i++) {
- if (s[i] != s[sz(s) - 1 - i])
- return false;
- }
- return true;
- }
- int main() {
- struct timeval t1, t2;
- double elapsedTime;
- // start timer
- gettimeofday(&t1, NULL);
- freopen("in.txt", "r", stdin);
- int mx = 5000000;
- int prime_cnt = 0, pal_cnt = 0;
- vis[0] = vis[1] = true;
- for (int i = 2; i < mx; i++) {
- if (!vis[i]) {
- prime_cnt++;
- for (int j = i + i; j < mx; j += i)
- vis[j] = true;
- }
- prime[i] = prime_cnt;
- }
- for (int i = 1; i < mx; i++) {
- if (ok(i)) {
- pal_cnt++;
- }
- pal[i] = pal_cnt;
- }
- int p, q;
- scanf("%d %d", &p, &q);
- bool ok = false;
- for (int i = mx - 1; i > 0; i--) {
- if (1LL * q * prime[i] <= 1LL * p * pal[i]) {
- printf("%d\n", i);
- ok=true;
- break;
- }
- }
- if(!ok)
- printf("Palindromic tree is better than splay tree\n");
- // stop timer
- gettimeofday(&t2, NULL);
- // compute and print the elapsed time in millisec
- elapsedTime = (t2.tv_sec - t1.tv_sec) * 1000.0; // sec to ms
- elapsedTime += (t2.tv_usec - t1.tv_usec) / 1000.0; // us to ms
- cout << elapsedTime << " ms."<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement