Advertisement
veschii_nevstrui

brute force

Jan 13th, 2022
714
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. template <typename T>
  6. istream& operator >> (istream& in, vector <T> &a) {
  7.     for (T&i : a) {
  8.         in >> i;
  9.     }
  10.     return in;
  11. }
  12.  
  13.  
  14. template <typename T>
  15. ostream& operator << (ostream& out, vector <T> &a) {
  16.     for (T&i : a) {
  17.         out << i << " ";
  18.     }
  19.     return out;
  20. }
  21.  
  22. bool check(int a, int b) {
  23.     if (a == 0 || b == 0) {
  24.         return true;
  25.     }
  26.     return a % b == 0 || b % a == 0;
  27. }
  28.  
  29. bool operator > (const vector <int> &a, const vector <int> &b) {
  30.     if (a.size() != b.size()) {
  31.         return a.size() > b.size();
  32.     }
  33.     for (int i = 0; i < a.size(); ++i) {
  34.         if (a[i] != b[i]) {
  35.             return a[i] > b[i];
  36.         }
  37.     }
  38.     return false;
  39. }
  40.  
  41. vector <int> ans;
  42. int cnt = 0;
  43.  
  44. bool f(vector <int> &v, int i, int n, vector <int> &used) {
  45.     if (v > ans) {
  46.         ans = v;
  47.     }
  48.     if (i == n) {
  49.         cout << v << "\n";
  50.         return true;
  51.     }
  52.     for (int j = n - 1; j >= 0; --j) {
  53.         if (!used[j]) {
  54.             if (i == 0 || check(v[i - 1], j)) {
  55.                 v.push_back(j);
  56.                 used[j] = 1;
  57.                 if (f(v, i + 1, n, used)) {
  58.                     return true;
  59.                 }
  60.                 used[j] = 0;
  61.                 v.pop_back();
  62.             }
  63.         }
  64.     }
  65.     ++cnt;
  66.     return false;
  67.  
  68. }
  69.  
  70. int main() {
  71.     int t;
  72.     cin >> t;
  73.     for (int n = 2; n <= t; ++n) {
  74.         vector <int> v, used(n, 0);
  75.         cout << n << ":\n";
  76.         f(v, 0, n, used);
  77.         cout << ans << endl;
  78.         cout << cnt << endl;
  79.  
  80.         cnt = 0;
  81.         ans.clear();
  82.     }
  83. }
  84.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement