fork download
  1. #include<bits/stdc++.h>
  2.  
  3. #pragma GCC optimize("O2")
  4. #pragma GCC optimize("O3")
  5. #pragma GCC optimize("Ofast")
  6.  
  7. #define int long long
  8.  
  9. #define pii pair<int,int>
  10. #define ii int,int
  11. #define fi first
  12. #define se second
  13. #define pb push_back
  14. #define lb lower_bound
  15. #define ub upper_bound
  16. #define umap unordered_map
  17. #define BIT(mask, i) ((mask >> i)&1)
  18. #define ALL(c) c.begin(), c.end()
  19.  
  20. using namespace std;
  21.  
  22. mt19937 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
  23. int rand(int l, int r){
  24. return l + rd()*rd()%(r-l+1);
  25. }
  26.  
  27. const int N = 1e6+7;
  28. const int M = 1e3+3;
  29. const int MOD = 1e9+7;
  30. const int inf = 3e18;
  31.  
  32. int n, f, visited[11], x[11];
  33.  
  34. // Sinh các hoán vị của 1, 2, 3, ... ,n
  35.  
  36. // mảng x có tác dụng là để lưu hoán vị
  37. // mảng visited có tác dụng để xét các số chưa xuất hiện trong hoán vị
  38.  
  39. void backtracking(int i){
  40. for(int j = 1; j <= n; j++){
  41. if(visited[j] == false){ // j chưa xuất hiện trong hoán vị
  42. visited[j] = true;
  43. x[i] = j;
  44. if(i == n){ // đã đủ 1 hoán vị
  45. // xét hoán vị có thỏa mãn đề hay không
  46. vector<int> v;
  47. for(int k = 1; k <= n; k++){
  48. v.push_back(x[k]);
  49. }
  50.  
  51. while(v.size() != 1){
  52. vector<int> u;
  53. for(int k = 1; k < v.size(); k++){
  54. u.push_back(v[k] + v[k-1]);
  55. }
  56. v = u;
  57. }
  58. if(v[0] == f){
  59. for(int k = 1; k <= n; k++){
  60. cout << x[k] << ' ';
  61. }
  62. return;
  63. }
  64. }
  65. else backtracking(i + 1); // i chưa đủ 1 hoán vị thì thêm 1 phần tử nữa
  66. // để đủ 1 hoán vị
  67. visited[j] = false;
  68. }
  69. }
  70.  
  71. }
  72.  
  73. signed main(){
  74. ios_base::sync_with_stdio(0);
  75. cin.tie(0);
  76. cout.tie(0);
  77. cin >> n >> f;
  78. backtracking(1);
  79. }
  80.  
Success #stdin #stdout 0s 5316KB
stdin
Standard input is empty
stdout
Standard output is empty