Advertisement
perchuts

Untitled

Mar 17th, 2023
772
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. bool mark[105];
  6.  
  7. vector<pair<int,int>> ans, best;
  8.  
  9. int n, sz = 15;
  10.  
  11. void solve() {
  12.     if (ans.size() >= sz) return;
  13.     int me = ans.back().first;
  14.     if (me == n) {
  15.         best = ans, sz = ans.size();
  16.         return;
  17.     }
  18.     for (int i = 0; i < ans.size(); ++i) {
  19.         int tenta = ans[i].first + me;
  20.         if (tenta > n || mark[tenta]) continue;
  21.         ans.push_back({tenta, ans[i].first}), mark[tenta] = 1;
  22.         solve();
  23.         ans.pop_back(), mark[tenta] = 0;
  24.     }
  25. }
  26.  
  27. int main() {
  28.     int m; cin >> m >> n;
  29.     if (m != 1) cout << '*' << endl;
  30.     else {
  31.         mark[1] = 1;
  32.         ans.push_back({1, 0});
  33.         solve();
  34.         for (auto [x, y] : best) {
  35.             if (y == 0) continue;
  36.             cout << 1 << ' ' << x - y << endl;
  37.             cout << 1 << ' ' << y << endl;
  38.         }
  39.     }
  40. }
  41.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement