729 - The Hamming Distance Problem

[infancy]

i fixed the problem thanks

[kenneth]

Just would like to let you know that in the actual competition, the last line in the output does not matter. You will still get accepted.

[Rinoaheartilly]

I got Wrong Answer too. I try all the input in this thread and I got the right output(I think).
Help please

Code: Select all

# include<iostream>
using namespace std;
int Calculate(int length, int H);
int Factorial(int x);
void MarkZero(int number[], int &pos, int &count0, int length, int H, int solution);
int main(){
   int dataset, length, H, count0, count1, pos, solution;
   count0 = count1 = solution = 0;
   pos = -1;
   cin>>dataset;
   int number[16];
   for(int i=0; i<dataset; i++){
      cin>>length>>H;
      int k = Calculate(length,H);
      while(solution<k){
         if(pos<length-1){
            if(solution==0){
               MarkZero(number,pos,count0,length,H,solution);
               while(pos<length-1){
                  number[++pos] = 1;
               }
            }else{
               number[pos] = 1;
               MarkZero(number,pos,count0,length,H,solution);
               for(int i=0; i<=pos; i++){
                  if(number[i]==1){
                     count1++;
                  }
               }
               while(count1<H){
                  number[++pos]=1;
                  count1++;
               }
               
            }
            if(pos==length-1){
               for(int i=0; i<length; i++){
                  cout<<number[i];
               }
               cout<<endl;
               count0 = 0;
               count1 = 0;
               solution++;
            }
         }else{//Backtracking
            for(int i=length-1; i>=0; i--){
               if(number[i]==1){
                  pos = i;
                  break;
               }
            }
            pos--;
            while(number[pos]==1 && pos>=0){
               pos--;
            }

         }
      
      }
      if(i!=dataset-1)
         cout<<endl;
      pos = -1;
      solution = count1 = count0 = 0;

   }

}
int Factorial(int n,int x){
   int fac = n+1;
   for(int i=n+2; i<=x; i++){
      fac = fac*i;
   }
   return fac;

}
void MarkZero(int number[], int &pos, int &count0, int length, int H, int solution){
   for(int i=0; i<pos; i++){
      if(number[i]==0)
         count0++;
   }
   while(count0<length-H){
      number[++pos] = 0;
      count0++;
   }
}
int Calculate(int length, int H){
   int n, bottom;
   if(length-H>=H){
      n = length-H;
      bottom = H;
   }else{
      n = H;
      bottom = length-H;
   }
   return Factorial(n,length)/Factorial(0,bottom);
}

This is my input

Code: Select all

7
4 2
1 0 
1 1
2 0
2 1
5 2
5 3

This is the output

Code: Select all

0011
0101
0110
1001
1010
1100

0

1

00

01
10

00011
00101
00110
01001
01010
01100
10001
10010
10100
11000

00111
01011
01101
01110
10011
10101
10110
11001
11010
11100

[Rinoaheartilly]

I got it accepted. Thanks

[unaben]

I am getting WA with this code I tried the input that I found on the board but I still cannot find where the mistake is . Can someone plz help.

Here is my code

#include<iostream>
#include<string>
#include<algorithm>
#include<map>

using namespace std;
bool first = true;

void handle()
{
if(first == false)
cout<<endl;
int N, H;
map<string, int>counter;
string num="";
cin>>N>>H;
if((N!=0 and H==0))
{
for(int h=0; h<N; h++)
cout<<"0";
cout<<endl;
}
else if(N==H)
{
for(int t=0; t<N; t++)
cout<<"1";
cout<<endl;
}
else
{
for(int i = 0; i<N-H; i++)
num+="0";
for(int j=0; j<H; j++)
num+="1";

for(int e=0; e<num.size(); e++)
{
for(int m = 1; m<num.size(); m++)
{
if(num[m-1]!=num[m])
{
swap(num[m-1], num[m]);
counter[num]++;
}
}
}

for(map<string, int>::const_iterator iter = counter.begin(); iter!= counter.end(); iter++)
cout<<iter->first<<endl;
}
first = false;
}

int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
handle();
}

Thanx!

[candide]

Hi !
I spend many hours trying to find bug in my code but it seems correct.
I can't find an input not giving the correct answer, I did many tries.
Why I got WA ?

Here the C code followed by input/output sample :

Code: Select all

/* ---------- 729 - The Hamming Distance Problem -------------*/
#include <stdio.h>

#define N_MAX 17

void swap(int tab[], int i, int j)
{
  int temp;

  temp = tab[i];
  tab[i] = tab[j];
  tab[j] = temp;
}

int *next(int *p, int n)
{
  int i, j = n - 1, k = n - 1;

  while (k > 0 && p[k - 1] >= p[k])
    k--;

  if (k != 0)
    {
      while (p[j] <= p[k - 1])
        j--;
      swap(p, k - 1, j);
      for (i = k, j = n - 1; i < j; i++, j--)
        swap(p, i, j);
    }

  if (k == 0)
    return NULL;
  else
    return p;
}
void print(int *t, int n)
{
  int i;

  for (i = 0; i < n; i++)
    printf("%d", t[i]);
}
void generate(int t[], int n, int p)
{
  int i, j;

  for (i = 0; i < n; i++)
    t[i] = 0;

  i = n - 1;
  for (j = 0; j < p; j++)
    {
      t[i] = 1;
      i--;
    }
  while (1)
    {
      if (t != NULL)
        {
          print(t, n);
        }
      else
        break;
      if ((t = next(t, n)) != NULL)
        printf("\n");
    }
}

int main(void)
{
  int n, p, N, k;
  int t[N_MAX] = { 0 };

  scanf("%d", &N);
  for (k = 0; k < N; k++)
    {
      scanf("%d", &n);
      scanf("%d", &p);
      generate(t, n, p);
      if (k < N - 1)
        printf("\n\n");
    }

  return 0;
}
/* ---------- End of code  -------------*/

input file :

Code: Select all

6
5 0
5 1
5 2
5 3
5 4
5 5

and the corresponding output file :

Code: Select all

00000

00001
00010
00100
01000
10000

00011
00101
00110
01001
01010
01100
10001
10010
10100
11000

00111
01011
01101
01110
10011
10101
10110
11001
11010
11100

01111
10111
11011
11101
11110

11111

Thanks for checking my code.

[candide]

up please

[candide]

Problem fixed. The core code is correct. The problem cause was a bad blank line formatting.

[skdls]

why i get WA all of my output is right can anyone help me??????????????????

Code: Select all

#include<stdio.h>
#include<math.h>
#include<string.h>
char str[1000];
bool used[1000];
char per[4000];
long L,t=0;

bool Issolution(long p)
{
	if(p==L)
		return true;
	return false;
}

long con_can(long p,char can[])
{
   long cn,i;
   bool flag[1000]={false};
   cn=0;
   //printf("p=%ld\n",p);
   for(i=0;i<L;i++)
   {
	   
	   if((used[i]==false)&&flag[str[i]]==false)
	   { 
		 
		   can[cn++]=i;
		   flag[str[i]]=true;
	   }

   }
//printf("cn=%ld\n",cn);
return cn;
}

void permute(long p)
{
	long cn,i;
	
	if(Issolution(p))
	{
	   t++;
	   per[L]=NULL;
	   printf("%s\n",per);
	   return;
	}
   char can[10000];
   cn=con_can(p,can);
   for(i=0;i<cn;i++)
   {
	   used[can[i]]=true;
	   per[p]=str[can[i]];
	   
	   permute(p+1);
	   used[can[i]]=false; 
   }
   
   return;
}

int main()
{
	long i,j,k,n,m;
	while(scanf("%ld",&k)>0)
	{
		
		
		for(j=0;j<k;j++)
		{
			printf("\n");
	scanf("%ld %ld",&m,&n);
	printf("\n");
	for(i=0;i<m-n;i++)
	{
		str[i]='0';
	}
	for(i=m-n;i<m;i++)
		str[i]='1';
	str[m]='\0';
	L=strlen(str);	
	permute(0);

		}
	}
}

[qwerty]

why i get WA all of my output is right can anyone help me??????????????????

check blank line formatting.there should be a blank line after each case except the last.