Trick: Finding all the results is pretty easy using any Basic Backtracking code but you have to sort them. So? Don't work with 1s work with 0s. Or just use next_permutation( ) from STL, your choice. Optimizations: Pregenerating all combinations might give you a better runtime, didn't try it.
Sample Input:
1 16 7
Sample Output:
Please find it using UVA Toolkit (www.uvatoolkit.com)
/* Faith-M */ //Headers #include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <climits> #include <clocale> //Defines #define pow2(i) (1<<i) #define bit(i) (1<<i) #define isOdd(i) (i&1) #define isEven(i) (!(i&1)) #define isPrime(i) ((i==2) || ((i&1) && !pTest[i])) //pTest has to be the bool array's name #define sz(i) i.size() #define vec(type,name) vector< type > name #define rep(i,a,b) for(int i=a ; i<=b ; i++) #define swap(type,a,b) {type t=a; a=b; b=t;} #define sum(a,n) ( (n*(n+1)/2) - (a-1)*a/2 ) #define iscap(i) (i>='A'&&i<='Z') #define issmall(i) (i>='a'&&i<='z') #define isnum(i) (i>='0'&&i<='9') #define issymbol(i) (!(i>='a'&&i<='z') && !(i>='A'&&i<='Z') && !(i>='0'&&i<='9')) #define mk(i,j) make_pair(i,j) #define ERROR 1e-11 //Type Defs typedef long long lint; typedef unsigned long long ulint; typedef long double ldouble; using namespace std; int st[20]; void func(int n, int h, int cnt, int x) { if (cnt >= h) { for (int j=1 ; j<=n ; j++) { printf("%d",st[j]); } printf("\n"); return; } for (int i=x ; i<=n ; i++) { if (st[i] == 1) { st[i] = 0; func(n,h,cnt+1,i+1); st[i] = 1; } } return; } int main() { //freopen("input.txt","r+",stdin); //freopen("output.txt","w+",stdout);/**/ // TEST CASE // int kase=1, kounter=1;/**/ int n, h; bool blnk = false; scanf("%d",&kase); while ( kase-- ) { if (blnk) printf("\n"); else blnk = true; for (int i=1 ; i<=20 ; i++) { st[i] = 1; } scanf("%d %d",&n,&h); func(n,n-h,0,1); } return 0; }
No comments:
Post a Comment
Post your comment here. If you want to say something about programming problems, scripts, software etc, please try to be as descriptive as possible.