Wednesday, May 02, 2012

[UVa] 729 - The Hamming Distance Problem


Method: Bruteforce, all combinations. Permutation. Backtracking.
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.

Connect Rapoo MT750S with Linux (Tested on Manjaro)

 I bought this obvious copy of MX Master 2S in hopes of having the device switching functionality along with a lightweight body because I ha...