EugenyB

ChernobylEagles.cpp

Jan 26th, 2012
229
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1. #include <cstdlib>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. int q[1001][11];
  7.  
  8. int f(int n, int k)
  9. {
  10.    if (n==0 || k==0) return 0; else
  11.    if (q[n][k]>0);  else
  12.    {
  13.       int min = 1000000000;
  14.       for (int i = 1; i <= n; i++)
  15.       {
  16.          int v1 = f(n-i,k);
  17.          int v2 = f(i-1,k-1);
  18.          int val = v1 > v2 ? v1 : v2;
  19.          if (val < min) min = val;
  20.       }
  21.       min++;
  22.       q[n][k] = min;
  23.    }
  24.    return q[n][k];
  25. }
  26.  
  27. void run()
  28. {
  29.    for (int i = 0; i < 1001; i++)
  30.    {
  31.        q[i][1] = i;
  32.    }
  33.    for (int i = 0; i < 11; i++)
  34.    {
  35.        q[1][i] = 1;
  36.    }
  37.    int k, n;    
  38.    for (;;)
  39.    {
  40.       cin >> k; if (k==0) return;
  41.       cin >> n;
  42.       if (k>10) k = 10;
  43.       cout << f(n,k) << "\n";
  44.    }
  45. }
  46.  
  47. int main(int argc, char *argv[])
  48. {
  49.     run();
  50.     return EXIT_SUCCESS;
  51. }
Advertisement
Add Comment
Please, Sign In to add comment