Please help with this question backtracking

Правка en1, от om1429888, 2022-07-16 21:46:09

https://www.spoj.com/problems/BTCK/

//Jai shree Ganesh
//Jai shree Ram
//Har Har Mahadev
#include<iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fr(i,a,b) for(int i=a;i<b;i++)
#define loop(x,n) for(int x=0;x<n;x++)
#define mod 1e7
#define inf (1LL<<60)
#define all(x) (x).begin(),(x).end()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
void precal(){
}
vector<int>perm={0,1,2,3,4,5,6,7,8,9};
 vector<ll>input(10);
bool helper(ll k,ll index,ll sum){
if(sum>k)return false;
if(index==10){
  fr(i,0,10){
    cout<<perm[i]<<" ";
  }
  cout<<endl;
  return true;
}
for(int i=index;i<10;i++){
  swap(perm[index],perm[i]);
  bool check=helper(k,index+1,sum+input[index]*perm[index]);
  if(check){
    swap(perm[index],perm[i]);
    return true;
  }
  swap(perm[index],perm[i]);
}
return false;
}
void solve(){
  fr(i,0,10)cin>>input[i];
  ll k;
  cin>>k;
  bool check=helper(k,0,0);
  if(!check){
    cout<<-1<<endl;
  }
}
int main()
{
fast_io;
cout<<fixed;
cout<<setprecision(10);
precal();
int t=1;cin>>t;
for(int i=1;i<=t;i++)
{
//cout<<Case #<<i<<: ;
solve();
}
 return 0;
}

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский om1429888 2022-07-16 21:46:38 54
en1 Английский om1429888 2022-07-16 21:46:09 1489 here im trying to swap to generate permuations that are lexicographically smaller but this code is giving wrong answer (published)