Advertisement
Guest User

Untitled

a guest
May 6th, 2016
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.48 KB | None | 0 0
  1. #include <cstring>
  2. #include <map>
  3. #include <deque>
  4. #include <queue>
  5. #include <stack>
  6. #include <sstream>
  7. #include <iostream>
  8. #include <cstdio>
  9. #include <cmath>
  10. #include <math.h>
  11. #include <cstdlib>
  12. #include <ctime>
  13. #include <algorithm>
  14. #include <vector>
  15. #include <set>
  16. #include <list>
  17. #include <climits>
  18. #include <cctype>
  19. #include <bitset>
  20. #include <iostream>
  21. #include <iomanip>
  22. #include <complex>
  23. #include <sys/time.h>
  24.  
  25.  
  26. using namespace std;
  27.  
  28. typedef stringstream ss;
  29. typedef long long ll;
  30. typedef pair<int, int> ii;
  31. typedef vector<ii> vii;
  32. typedef vector<vector<ii> > vvii;
  33. typedef vector<string> vs;
  34. typedef vector<int> vi;
  35. typedef vector<vector<int> > vvi;
  36. typedef vector<double> vd;
  37. typedef long double ld;
  38. typedef vector<vector<ll> > grix;
  39. typedef complex<double> point;
  40. typedef complex<long long> pointINT;
  41.  
  42. int dx[] = { -1, 1, 0, 0, 0, 0 };
  43. int dy[] = { 0, 0, -1, 1, 0, 0 };
  44. int dz[] = { 0, 0, 0, 0, -1, 1 };
  45.  
  46. int DX[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
  47. int DY[] = { 1, -1, 0, 0, 1, -1, -1, 1 };
  48.  
  49. double PI = 3.1415926535897932384626433832795;
  50.  
  51. const ll oo = 1e9 + 1;
  52. const double eps = 1e-6;
  53. const ll mod = 1234567;
  54.  
  55. #define all(v) v.begin(), v.end()
  56. #define rall(v) v.rbegin(), v.rend()
  57. #define sz(v) ((int)v.size())
  58. #define clr(v, d) memset(v, d, sizeof(v))
  59. #define polar(r,t) ((r)*exp(point(0,(t))))
  60. #define length(a) hypot((a).real(),(a).imag())
  61. #define angle(a) atan2((a).imag() , (a).real())
  62. #define vec(a,b) ((b)-(a))
  63. #define dot(a,b) ((conj(a)*(b)).real())
  64. #define cross(a,b) ((conj(a)*(b)).imag())
  65. #define lengthSqr(a) dot(a,a)
  66. #define rotate(v,t) ((v)*exp(point(0,t)))
  67. #define rotateAbout(v,t,a) (rotate(vec(a,v),t)+(a))
  68. #define reflect(v,m) (conj((v)/(m))*m)
  69. #define dist(a,b) (sqrt(pow((a).real()-(b).real(),2.0)+pow((a).imag()-(b).imag(),2.0)))
  70. #define distsqr(a,b) (pow((a).real()-(b).real(),2.0)+pow((a).imag()-(b).imag(),2.0))
  71. #define normalize(a) ((a)/length(a))
  72. #define ccw(a,b,c) (cross(vec((a),(b)),vec((a),(c)))>=0)
  73. #define collinear(a,b,c) (fabs(cross(vec((a),(b)),vec((a),(c))))<eps)
  74. #define LSOne(S) (S & (-S))
  75. ////////////////////////////////////////////////////////////////////////
  76.  
  77. //freopen("in.txt","r",stdin);
  78. //freopen("out.txt","w",stdout);
  79.  
  80. bool vis[5000001];
  81. int prime[5000001];
  82. int pal[5000001];
  83.  
  84. bool ok(int num) {
  85. string s = "";
  86. while (num) {
  87. s += (num % 10);
  88. num /= 10;
  89. }
  90. for (int i = 0; i < sz(s) / 2; i++) {
  91. if (s[i] != s[sz(s) - 1 - i])
  92. return false;
  93. }
  94. return true;
  95. }
  96.  
  97. int main() {
  98. struct timeval t1, t2;
  99. double elapsedTime;
  100.  
  101. // start timer
  102. gettimeofday(&t1, NULL);
  103. freopen("in.txt", "r", stdin);
  104. int mx = 5000000;
  105. int prime_cnt = 0, pal_cnt = 0;
  106. vis[0] = vis[1] = true;
  107.  
  108. for (int i = 2; i < mx; i++) {
  109. if (!vis[i]) {
  110. prime_cnt++;
  111. for (int j = i + i; j < mx; j += i)
  112. vis[j] = true;
  113. }
  114. prime[i] = prime_cnt;
  115. }
  116.  
  117. for (int i = 1; i < mx; i++) {
  118. if (ok(i)) {
  119. pal_cnt++;
  120. }
  121. pal[i] = pal_cnt;
  122. }
  123. int p, q;
  124. scanf("%d %d", &p, &q);
  125. bool ok = false;
  126. for (int i = mx - 1; i > 0; i--) {
  127. if (1LL * q * prime[i] <= 1LL * p * pal[i]) {
  128. printf("%d\n", i);
  129. ok=true;
  130. break;
  131. }
  132. }
  133. if(!ok)
  134. printf("Palindromic tree is better than splay tree\n");
  135. // stop timer
  136. gettimeofday(&t2, NULL);
  137.  
  138. // compute and print the elapsed time in millisec
  139. elapsedTime = (t2.tv_sec - t1.tv_sec) * 1000.0; // sec to ms
  140. elapsedTime += (t2.tv_usec - t1.tv_usec) / 1000.0; // us to ms
  141. cout << elapsedTime << " ms."<<endl;
  142. return 0;
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement