729 - The Hamming Distance Problem

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

infancy
New poster
Posts: 4
Joined: Thu Oct 09, 2003 1:55 pm

Post by infancy »

i fixed the problem thanks
kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

Post by 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
New poster
Posts: 9
Joined: Thu Oct 14, 2004 6:37 am
Location: North Carolina

Post by 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
New poster
Posts: 9
Joined: Thu Oct 14, 2004 6:37 am
Location: North Carolina

Post by Rinoaheartilly »

I got it accepted. Thanks
unaben
New poster
Posts: 12
Joined: Mon Jul 10, 2006 10:47 pm

729 - WA

Post by 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 :o . 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
New poster
Posts: 3
Joined: Wed Nov 12, 2008 5:17 pm

Wrong answer

Post by 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
New poster
Posts: 3
Joined: Wed Nov 12, 2008 5:17 pm

Re: 729 - The Hamming Distance Problem

Post by candide »

up please
candide
New poster
Posts: 3
Joined: Wed Nov 12, 2008 5:17 pm

Re: 729 - The Hamming Distance Problem

Post by candide »

Problem fixed. The core code is correct. The problem cause was a bad blank line formatting.
skdls
New poster
Posts: 1
Joined: Tue Aug 04, 2009 11:10 am

729 - The Hamming Distance Problem

Post by 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
New poster
Posts: 21
Joined: Sun Feb 08, 2009 5:26 pm
Location: Mumbai,India

Re: 729 - The Hamming Distance Problem

Post by qwerty »

skdls wrote:
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.
Post Reply

Return to “Volume 7 (700-799)”