Raslboyy

3004

Sep 5th, 2019
133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.87 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <unordered_map>
  4.  
  5. using namespace std;
  6.  
  7. typedef pair<int, int> pr;
  8.  
  9. struct pair_hash {
  10.     template <typename T1, typename T2>
  11.     size_t operator () (const pair<T1, T2>& p) const {
  12.         auto h1 = hash<T1>{}(p.first);
  13.         auto h2 = hash<T2>{}(p.second);
  14.         return h1 ^ h2;
  15.     }
  16. };
  17.  
  18. unordered_map<pr, int, pair_hash> us;
  19.  
  20. int foo(int n, int k) {
  21.     if (n == k && n > 0) return 1;
  22.     else if (n > 0 && k == 1) return 1;
  23.     else if (k > n) return 0;
  24.     else {
  25.         pr a = make_pair(n - 1, k - 1);
  26.         pr b = make_pair(n - k, k);
  27.         if (us.count(a) == 0) us[a] = foo(a.first, a.second);
  28.         if (us.count(b) == 0) us[b] = foo(b.first, b.second);
  29.         return us[a] + us[b];
  30.     }
  31. }
  32.  
  33. int main() {
  34.     ifstream fin("input.txt");
  35.     ofstream fout("output.txt");
  36.  
  37.     int n, k;
  38.     fin >> n >> k;
  39.     fout << foo(n, k);
  40.  
  41.     fin.close();
  42.     fout.close();
  43.     return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment