Advertisement
mickypinata

USACO-T016: Arithmetic Progressions

Nov 28th, 2021
427
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ID: mickyta1
  3. TASK: ariprog
  4. LANG: C++
  5. */
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. typedef pair<int, int> pii;
  11.  
  12. const int N = 125000 + 5;
  13.  
  14. vector<pii> ans;
  15. vector<int> bisq;
  16. bool isBisq[N];
  17.  
  18. bool comp(const pii &lhs, const pii &rhs){
  19.     if(lhs.second != rhs.second){
  20.         return lhs.second < rhs.second;
  21.     }
  22.     return lhs.first < rhs.first;
  23. }
  24.  
  25. int main(){
  26.     freopen("ariprog.in", "r", stdin);
  27.     freopen("ariprog.out", "w", stdout);
  28.  
  29.     int n, limBisq;
  30.     scanf("%d%d", &n, &limBisq);
  31.     for(int i = 0; i <= limBisq; ++i){
  32.         for(int j = i; j <= limBisq; ++j){
  33.             int x = i * i + j * j;
  34.             bisq.push_back(x);
  35.             isBisq[x] = true;
  36.         }
  37.     }
  38.     sort(bisq.begin(), bisq.end());
  39.     bisq.resize(unique(bisq.begin(), bisq.end()) - bisq.begin());
  40.     for(int i = 0; i < (int)bisq.size() - 1; ++i){
  41.         for(int j = i + 1; j < bisq.size(); ++j){
  42.             int a = bisq[i];
  43.             int d = bisq[j] - bisq[i];
  44.             if(a + (n - 1) * d > bisq.back()){
  45.                 break;
  46.             }
  47.             bool ok = true;
  48.             for(int k = 1; k <= n; ++k){
  49.                 if(!isBisq[a + (k - 1) * d]){
  50.                     ok = false;
  51.                     break;
  52.                 }
  53.             }
  54.             if(ok){
  55.                 ans.emplace_back(a, d);
  56.             }
  57.         }
  58.     }
  59.     sort(ans.begin(), ans.end(), comp);
  60.     if(ans.empty()){
  61.         cout << "NONE\n";
  62.     }
  63.     for(pii p : ans){
  64.         cout << p.first << ' ' << p.second << '\n';
  65.     }
  66.  
  67.     fclose(stdin);
  68.     fclose(stdout);
  69.     return 0;
  70. }
  71.  
Advertisement
RAW Paste Data Copied
Advertisement