Posted By

Nursoltan on 06/30/11


Tagged

USACO


Versions (?)

ch1 : Arithmetic Progressions


 / Published in: C++
 

  1. /*
  2.   NAME : Nursoltan
  3.   PROB : ariprog
  4.   LANG : C++
  5.   DATE : 30/06/11 01:01
  6. */
  7. #include <algorithm>
  8. #include <bitset>
  9. #include <cctype>
  10. #include <cmath>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <cstring>
  14. #include <ctime>
  15. #include <sstream>
  16. #include <iostream>
  17. #include <map>
  18. #include <set>
  19. #include <stack>
  20. #include <utility>
  21. #include <queue>
  22.  
  23. using namespace std;
  24.  
  25. #define MAX 100
  26. #define INF INT_MAX
  27. #define eps (1e-9)
  28.  
  29. #define FOR(_i,_k,_n) for(int (_i)=(_k); (_i)<(_n); (_i)++)
  30. #define FORR(_i,_k,_n) for(int (_i)=(_k); (_i)>=(_n); (_i)--)
  31. #define CLR(_x) memset((_x),0,sizeof(_x))
  32. #define SQR(_x) ((_x)*(_x))
  33. #define all(_x) _x.begin(),_x.end()
  34. #define sz(_x) sizeof(_x)
  35.  
  36. #define vc vector<int>
  37. #define pb push_back
  38. #define mp make_pair
  39. #define iss istringstream
  40. #define oss ostringstream
  41. #define px first
  42. #define py second
  43.  
  44. typedef long long ll;
  45. typedef pair <int,int> point;
  46. int ABS(int _x){ return _x>0?_x:-_x; }
  47.  
  48. int main()
  49. {
  50. freopen("ariprog.in","r",stdin);
  51. freopen("ariprog.out","w",stdout);
  52.  
  53. int N,M;
  54. bool Map[125001]={0};
  55. int a[31640],lna=0;
  56. point ret[1000001];
  57. int lnret=0;
  58.  
  59. cin>>N>>M;
  60.  
  61. FOR(p,0,M+1) FOR(q,p,M+1) a[lna++]=p*p+q*q,Map[p*p+q*q]=true;
  62. sort(a,a+lna);
  63.  
  64. FOR(i,0,lna) FOR(d,1,3000){
  65. bool ok=1;
  66. int a1=a[i];
  67. if(a1>=100000) break;
  68. FOR(k,0,N){ if(!ok || a1+d*k>125001) break; if(Map[a1+d*k]==false) ok=0; }
  69. if(ok && d>0) ret[lnret++]=(mp(d,a1));
  70. }
  71. sort(ret,ret+lnret);
  72. if(lnret==0){ cout<<"NONE\n"; goto GOTOHELL; }
  73. cout<<ret[0].py<<" "<<ret[0].px<<endl;
  74. FOR(i,1,lnret){
  75. if(ret[i].px==ret[i-1].px && ret[i].py==ret[i-1].py) continue;
  76. cout<<ret[i].py<<" "<<ret[i].px<<endl;
  77. }
  78.  
  79. GOTOHELL :
  80.  
  81. //system("pause");
  82. return 0;
  83. }

Report this snippet  

You need to login to post a comment.