fork download
copy 
  1. #include<iostream>
  2. #include<fstream>
  3. #include<algorithm>
  4. #include<vector>
  5. #include<set>
  6. #include<map>
  7. #include<cstdio>
  8. #include<cstring>
  9. #include<string>
  10. #include<cstdlib>
  11. #include<iomanip>
  12. #include<queue>
  13. #include<stack>
  14. #include<cmath>
  15. #include<utility>
  16. using namespace std;
  17.  
  18.  
  19. int a[125005] = {0};
  20. int n,m;
  21. struct prog {
  22.        int a;
  23.        int d;
  24. };
  25.  
  26. bool func(int n) {
  27.                   if(n > 2*m*m) return false;
  28.                   if(a[n] == 0) return false;
  29.                   return true;
  30. }
  31.  
  32. bool myfunc(prog i, prog j) {
  33.                  if(i.d < j.d) return true;
  34.                  if(i.d == j.d && i.a < j.a) return true;
  35.                  return false;
  36. }
  37.  
  38. int main() {
  39.            //ifstream fin("ariprog.in");
  40.            //ofstream fout("ariprog.out");
  41.            cin >> n >> m;
  42.            vector<int> bis;
  43.            bis.push_back(0);
  44.            for(int i = 0;i <= m;i++) {
  45.                    for(int j = i;j <= m;j++) {
  46.                            if(i == j && i == 0) continue;
  47.                            a[i*i+j*j] = 1;
  48.                    }
  49.            }
  50.            for(int i = 0;i < 125005;i++) {
  51.                    if(a[i] == 1) bis.push_back(i);
  52.            }
  53.            sort(bis.begin(),bis.end());
  54.            int k = bis.size();
  55.            vector<prog> ans;
  56.            cout << bis.size() << endl;     // **Checking the number of elements in 'bis'**
  57.            //They came out to be ~21000 when m=250.
  58.            int iterations = 0;         //To check how many iterations were done
  59.            for(int i = 0;i < k;i++) {
  60.                    for(int j = i+1;j < k;j++) {
  61.                            int d = bis[j]-bis[i];
  62.                            int temp = bis[j];
  63.                            bool check = true;
  64.                            for(int ctr = 1;ctr < n-1;ctr++) {
  65.                                    iterations++;   //Checking iterations
  66.                                    temp += d;
  67.                                    if(!func(temp)) {
  68.                                               check = false;
  69.                                               break;
  70.                                    }
  71.                            }
  72.                            if(check == true) {
  73.                                     prog temp2;
  74.                                     temp2.a = bis[i];
  75.                                     temp2.d = d;
  76.                                     ans.push_back(temp2);
  77.                            }
  78.                    }
  79.            }
  80.            sort(ans.begin(),ans.end(),myfunc);
  81.            //if(ans.size() == 0) fout << "NONE" << endl;
  82.            //for(int i = 0;i < ans.size();i++)
  83.                   // fout << ans[i].a << " " << ans[i].d << endl;
  84.            cout << iterations << endl;        //Came out to be around ~10^10
  85.            //system("PAUSE");
  86.            return 0;
  87. }
Success #stdin #stdout 2.31s 3924KB
comments (?)
stdin
copy 
25 250
stdout
copy 
21047
250866459
https://ideone.com/vpAUig
language:
C++ (gcc 8.3)
created:
9 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!