API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 31st, 2014
155
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 17.75 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <vector>
  3. #include <math.h>
  4. using namespace std;
  5.  
  6. vector<int> people, combination;
  7. int n, mi = 100000000;
  8. void pretty_print(const vector<int>& v)
  9. {
  10.     static int count = 0;
  11.     int sum =0;
  12.     for (int i = 0; i < v.size(); ++i)
  13.         sum+=v[i]*v[i];
  14.     if (sum==n&&v[v.size()-1]<mi)
  15.         mi = v[v.size()-1];
  16. }
  17.  
  18. void go(int offset, int k)
  19. {
  20.     if (k == 0)
  21.     {
  22.         pretty_print(combination);
  23.         return;
  24.     }
  25.     for (int i = offset; i <= people.size() - k; i++)
  26.     {
  27.         combination.push_back(people[i]);
  28.         go(i+1, k-1);
  29.         combination.pop_back();
  30.     }
  31. }
  32.  
  33. int main()
  34. {
  35.     bool tab[2825]={false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,
  36.     true,true,true,false,false,true,true,false,false,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,false,false,true,true,true,false,false,true,true,
  37.     false,false,true,true,true,false,false,true,true,false,false,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,true,true,false,false,true,true,false,
  38.     false,false,false,false,false,false,false,false,true,true,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,true,false,false,true,true,false,false,true,
  39.     true,true,false,false,true,true,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,true,false,false,true,true,false,false,false,false,
  40.     false,false,false,false,false,true,true,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,true,false,false,true,true,false,false,true,true,true,false,
  41.     false,true,true,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,true,false,false,false,false,false,false,true,false,false,false,false,false,false,false,
  42.     false,false,false,false,true,true,false,false,true,true,false,false,false,false,false,false,false,false,false,true,true,true,false,false,true,true,false,false,true,true,true,false,false,true,
  43.     true,false,false,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,
  44.     false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,true,false,false,false,false,false,false,true,false,false,false,false,false,false,false,
  45.     false,false,false,false,true,true,false,false,true,true,false,false,false,false,false,false,false,false,false,true,true,true,false,false,true,true,false,false,true,true,true,false,false,
  46.     true,true,false,false,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,
  47.     false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,
  48.     false,false,false,true,false,false,false,false,true,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,true,false,false,true,
  49.     true,false,false,false,false,false,false,false,false,false,true,true,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,true,false,false,true,true,false,
  50.     false,true,true,true,false,false,true,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,
  51.     false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,
  52.     false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,true,false,false,false,false,false,false,true,false,false,
  53.     false,false,false,false,false,false,false,false,false,true,true,false,false,true,true,false,false,false,false,false,false,false,false,false,true,true,true,false,false,true,true,false,false,
  54.     true,true,true,false,false,true,true,false,false,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,false,false,false,false,false,false,false,false,
  55.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  56.     false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,
  57.     false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,true,false,
  58.     false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,true,false,false,true,true,false,false,false,false,false,false,false,false,false,
  59.     true,true,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,
  60.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  61.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  62.     false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,
  63.     false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,
  64.     false,false,true,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,true,false,false,true,true,false,false,false,false,false,
  65.     false,false,false,false,true,true,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,true,false,false,true,true,false,false,true,true,true,false,false,
  66.     true,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  67.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  68.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  69.     false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,
  70.     false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,
  71.     false,false,false,false,true,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,true,false,false,true,true,false,false,false,
  72.     false,false,false,false,false,false,true,true,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,true,false,false,true,true,false,false,true,true,
  73.     true,false,false,true,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  74.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  75.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  76.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  77.     false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,
  78.     false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  79.     true,false,false,false,true,false,false,false,false,true,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,true,false,false,
  80.     true,true,false,false,false,false,false,false,false,false,false,true,true,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,true,false,false,true,
  81.     true,false,false,true,true,true,false,false,true,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  82.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  83.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  84.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  85.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  86.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  87.     false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,
  88.     false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,true,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,
  89.     false,false,false,true,true,false,false,true,true,false,false,false,false,false,false,false,false,false,true,true,true,false,false,true,true,false,false,true,true,true,false,false,true,
  90.     true,false,false,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  91.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  92.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  93.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  94.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  95.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  96.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,
  97.     false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,false,false,
  98.     false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,true,false,false,false,false,
  99.     false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,true,false,false,true,true,false,false,false,false,false,false,false,false,false,true,true,true,
  100.     false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,false,false,
  101.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  102.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  103.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  104.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  105.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  106.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  107.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  108.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,
  109.     false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,
  110.     false,false,false,false,true,false,false,false,true,false,false,false,false,true,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,
  111.     false,true,true,false,false,true,true,false,false,false,false,false,false,false,false,false,true,true,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,
  112.     false,true,false,false,true,true,false,false,true,true,true,false,false,true,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  113.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  114.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  115.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  116.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  117.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  118.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  119.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  120.     false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,
  121.     false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,
  122.     false,false,false,false,false,false,false,false,false,true,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,
  123.     false,false,true,false,false,false,false,true,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,true,true,false};
  124.  
  125.     cin>>n;
  126.     for (int i = 1; i <= 20; i++)
  127.         people.push_back(i);
  128.  
  129.     int suma_kwadratow=1, j=1, licznik=0;
  130.  
  131.     while (suma_kwadratow<=n)
  132.     {
  133.         go(0, j);
  134.         j++;
  135.         suma_kwadratow+=(j*j);
  136.     }
  137.  
  138.     for (int i=1; i<=n; i++)
  139.     {
  140.         if (tab[i])
  141.             licznik++;
  142.     }
  143.     if(mi<1000)
  144.         cout<<mi<<" "<<licznik<<endl;
  145.     else
  146.         cout<<"- "<<licznik<<endl;
  147.     return 0;
  148. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!