fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <queue>
  6. using namespace std;
  7.  
  8. #define DEBUG(x) cerr << #x << " = " << x << endl
  9.  
  10. const int MAX_M = 1000000;
  11.  
  12. bool prime[MAX_M + 1];
  13. int field[2000][2000];
  14. int dp[2000][2000];
  15. int dp2[2000][2000];
  16.  
  17. struct Node {
  18.     int y, x, val;
  19.     Node(int Y, int X, int V) : y(Y), x(X), val(V) { }
  20. };
  21.  
  22. int main() {
  23.     memset(prime, -1, sizeof(prime));
  24.     prime[0] = prime[1] = false;
  25.     for(int i = 2; i * i <= MAX_M; i++) {
  26.         if(prime[i])
  27.             for(int j = 2 * i; j <= MAX_M; j += i) prime[j] = false;
  28.     }
  29.  
  30.     for(int m, n; cin >> m >> n, m || n; ) {
  31.  
  32.     memset(field, 0, sizeof(field));
  33.  
  34.     int x = 1000, y = 1000;
  35.     int k = 1;
  36.     int cur = 1;
  37.     field[y][x] = 1;
  38.     while(true) {
  39.         if(k % 2 == 1) {
  40.             bool f = true;
  41.             for(int i = 0; i < k; i++) {
  42.                 x++;
  43.                 cur++;
  44.                 field[y][x] = cur;
  45.                 if(cur >= m) {
  46.                     f = false;
  47.                     break;
  48.                 }
  49.             }
  50.             if(f == false) break;
  51.             for(int i = 0; i < k; i++) {
  52.                 y--;
  53.                 cur++;
  54.                 field[y][x] = cur;
  55.                 if(cur >= m) {
  56.                     f = false;
  57.                     break;
  58.                 }
  59.             }
  60.             if(f == false) {
  61.                 break;
  62.             }
  63.         }
  64.         else {
  65.             bool f = true;
  66.             for(int i = 0; i < k; i++) {
  67.                 x--;
  68.                 cur++;
  69.                 field[y][x] = cur;
  70.                 if(cur >= m) {
  71.                     f = false;
  72.                     break;
  73.                 }
  74.             }
  75.             if(f == false) break;
  76.             for(int i = 0; i < k; i++) {
  77.                 y++;
  78.                 cur++;
  79.                 field[y][x] = cur;
  80.                 if(cur >= m) {
  81.                     f = false;
  82.                     break;
  83.                 }
  84.             }
  85.             if(f == false) break;
  86.         }
  87.         k++;
  88.     }
  89. #if 0
  90.     for(int y = 500 - m/4; y <= 500+m/4; y++) {
  91.         for(int x = 500-m/4; x <= 500+m/4; x++) {
  92.             printf("%2d ", field[y][x]);
  93.         }
  94.         printf("\n");
  95.     }
  96. #endif
  97.  
  98.     for(int i = 0; i < 2000; i++) {
  99.         for(int j = 0; j < 2000; j++) {
  100.             if(field[i][j] == n) {
  101.                 y = i;
  102.                 x = j;
  103.             }
  104.         }
  105.     }
  106.  
  107. #if 0
  108.     for(int y = 1490; y <= 1510; y++) {
  109.         for(int x = 1020; x <= 1040; x++) {
  110.             printf("%6d ", field[y][x]);
  111.         }
  112.         printf("\n");
  113.     }
  114. #endif
  115.  
  116.     int resNum = 0;
  117.     int resPos = 0;
  118.  
  119.     queue<Node> Q;
  120.     if(prime[field[y][x]]) Q.push(Node(y,x,field[y][x]));
  121.     else Q.push(Node(y,x,0));
  122.  
  123.     memset(dp, 0, sizeof(dp));
  124.     dp[y][x] = (prime[field[y][x]] ? 1 : 0);
  125.  
  126.     memset(dp2, 0, sizeof(dp2));
  127.  
  128.     dp2[y][x] = (prime[field[y][x]] ? field[y][x] : 0);
  129.  
  130.     while(!Q.empty()) {
  131.         Node p = Q.front(); Q.pop();
  132.         x = p.x, y = p.y;
  133. #if 0
  134.         // cerr << "(" << y << "," << x << ")" << endl;
  135.         if(field[y][x] == 993541) {
  136.             DEBUG(993541);
  137.             DEBUG(x);
  138.             DEBUG(y);
  139.         }
  140.  
  141.         if(field[y][x] == 997533) {
  142.             DEBUG(997533);
  143.             DEBUG(x);
  144.             DEBUG(y);
  145.         }
  146. #endif
  147.  
  148.         if(field[y+1][x] == 0) {
  149.             if(resNum < dp[y][x] ) {
  150.                 resNum = dp[y][x];
  151.                 resPos = dp2[y][x];
  152.             }
  153.  
  154.             if(resNum == dp[y][x] && resPos < dp2[y][x]) {
  155.                 resNum = dp[y][x];
  156.                 resPos = dp2[y][x];
  157.             }
  158.         }
  159.  
  160.         for(int i = -1; i <= 1; i++) {
  161.             if(field[y+1][x+i] == 0) continue;
  162.             // DEBUG(y+1); DEBUG(x+i);
  163.             int tmp = 0;
  164.             if(prime[field[y+1][x+i]]) tmp = 1;
  165.  
  166.             int newValue = dp[y][x] + tmp;
  167.  
  168.             int np = dp2[y][x];
  169.             if(tmp) np = field[y+1][x+i];
  170.  
  171.             if(dp[y+1][x+i] == 0) {
  172.                 dp[y+1][x+i] = newValue;
  173.                 Q.push(Node(y+1,x+i,np));
  174.                 dp2[y+1][x+i] = np;
  175.             }
  176.  
  177.             if(dp[y+1][x+i] == newValue && dp2[y+1][x+i] < np) {
  178.                 dp[y+1][x+i] = newValue;
  179.                 Q.push(Node(y+1,x+i,np));
  180.                 dp2[y+1][x+i] = np;
  181.             }
  182.  
  183.             if(dp[y+1][x+i] < newValue) {
  184.                 dp[y+1][x+i] = newValue;
  185.                 Q.push(Node(y+1,x+i,np));
  186.                 dp2[y+1][x+i] = np;
  187.             }
  188.         }
  189.     }
  190.  
  191. #if 0
  192.     for(int y = 500 - m/4; y <= 500+m/4; y++) {
  193.         for(int x = 500-m/4; x <= 500+m/4; x++) {
  194.             printf("%2d ", dp[y][x]);
  195.         }
  196.         printf("\n");
  197.     }
  198. #endif
  199.  
  200.     if(resNum == 0) {
  201.         cout << "0 0" << endl;
  202.     }
  203.     else {
  204.         cout << resNum << ' ' << resPos << endl;
  205.     }
  206.     }
  207. }
  208.  
Success #stdin #stdout 0.24s 50848KB
comments (?)
stdin
copy 
49 22
46 37
42 23
945 561
1081 681
1056 452
1042 862
973 677
1000000 1000000
0 0
stdout
copy 
0 0
6 43
1 23
20 829
18 947
10 947
13 947
23 947
534 993541
https://ideone.com/0ac5NF
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!