## 729 - The Hamming Distance Problem

Moderator: Board moderators

hsihsiwu
New poster
Posts: 9
Joined: Fri Apr 12, 2002 2:27 am

### 729 - The Hamming Distance Problem

#include <stdio.h>
#include <iostream.h>
#include <math.h>

void pri(int no,int n)
{
int str[16];
int i,k;
for(i=0;i<16;i++)
str=0;
k=15;
while(no>0)
{
str[k--]=no%2;
no/=2;
}
for(i=16-n;i<16;i++)
cout<<str;
cout<<endl;
}
int dis(int no)
{
int i;
i=0;
while(no>0)
{
if(no%2==1)
i++;
no/=2;
}
return i;
}
int main(int argc, char* argv[])
{
int n,h,no,max;
scanf("%d %d\n",&n,&h);
no=1;
max=pow(2,n);
while(no<max)
{
if(dis(no)==h)
pri(no,n);
no++;
}
return 0;
}
[cpp][/cpp]

broderic
New poster
Posts: 34
Joined: Thu Jun 06, 2002 4:35 am
Multiple input.

hsihsiwu
New poster
Posts: 9
Joined: Fri Apr 12, 2002 2:27 am

### I still got Wrong Answer

#include <stdio.h>
#include <iostream.h>
#include <math.h>

void pri(int no,int n)
{
int str[16];
int i,k;
for(i=0;i<16;i++)
str=0;
k=15;
while(no>0)
{
str[k--]=no%2;
no/=2;
}
for(i=16-n;i<16;i++)
cout<<str;
cout<<endl;
}
int dis(int no)
{
int i;
i=0;
while(no>0)
{
if(no%2==1)
i++;
no/=2;
}
return i;
}
int main(int argc, char* argv[])
{
int n,h,no,max;
while(scanf("%d %d\n",&n,&h)==2)
{
no=1;
max=pow(2,n);
while(no<max)
{
if(dis(no)==h)
pri(no,n);
no++;
}
}
return 0;
}

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
You see the blue checkmark near the problem name?? It is a multiple input problem.

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

hsihsiwu
New poster
Posts: 9
Joined: Fri Apr 12, 2002 2:27 am

### Thanks

I got it. Thank you very much......

pobuhov
New poster
Posts: 1
Joined: Tue Oct 01, 2002 8:53 pm
Location: Ukraine,Odessa
Contact:

### 729 - Why output limit?

[pascal]
Var
X,Size,Count: Word;
S: String;

Procedure Find(Pos, Count: Word);
begin
If Pos=Size+1 then
WriteLn(S) else
begin
if size-pos>=count then
begin
s[pos]:='0';
Find(Pos+1,Count);
end;

if Count>0 then
begin
S[pos]:='1';
Find(Pos+1,count-1);
end;
end;
end;

begin
Repeat
s:='';
For X:=1 to Size do S:=s+'0';
Find(1,Count);
Until EOF(Input);
end.[/pascal]

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
It is a "multiple input" problem, denoted by a blue tick next to the problem number in the problem list.

http://acm.uva.es/problemset/minput.html

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

### 729 Time exceed

How can I shorten the time?
Last edited by Eric on Thu Mar 27, 2003 2:45 pm, edited 1 time in total.

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
I have changed the algorithm but still got TLE. Can anyone help me?
Is it the problem of handling the multiple inputs?
Last edited by Eric on Thu Mar 27, 2003 2:44 pm, edited 1 time in total.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
You use write(B) to print the individual digits of the answer. The problem with output-intensive problems like this one is that the time required to print one character (using write()) is about the same as the time required to print a complete line (using writeln()).

So first assemble the number you want to print into a string, and then print that string in one move using writeln.

I tested this with your code, and your program then gives Accepted (P.E.) in 1.066 sec.
[pascal]...
If J > N Then
Begin
// For I := 1 to N Do
// Write(B);
// Writeln;
setlength(line,n);
for i:=1 to n do line:=chr(b+ord('0'));
writeln(line);
Exit;
End
...[/pascal]
where line is a string.

Good luck.

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
Thanks a lot~
These problems really teach me a lot.

jayd
New poster
Posts: 2
Joined: Wed Mar 05, 2003 1:23 pm

### 729 why I got a wrong answer??

this is my code
[/cpp]

#include <stdio.h>
#include <algorithm>
#include <string>
using namespace std;
void main(void)
{
string a = "";
char input[80] = "";
int total = 0, one = 0, i=0,j=0,loop=0;
//fgets(input, 80, stdin);
//loop = atol(input);
scanf("%d", &loop);
for(j=0;j<loop;j++){
a.resize(0);
scanf("%d %d", &total, &one);
for(i=0;i<total-one;i++) a.append("0");
for(i=0;i<one;i++) a.append("1");
sort(a.begin(),a.end());
printf("%s\n", a.begin());
while(next_permutation(a.begin(), a.end()))
printf("%s\n", a.begin());
printf("\n");
}
}

I don't know why I got a wrong answer??

someone help me ~!!

afonsocsc
New poster
Posts: 34
Joined: Mon Mar 24, 2003 1:15 am
Location: Portugal, Lisbon
I got ac and I have tested your prog's output with mine, the only difference is that your prog prints an extra line at the end of all the output...

jayd
New poster
Posts: 2
Joined: Wed Mar 05, 2003 1:23 pm
it should get a presentation error as you say

but I get a wrong answer >< i don't know why

boatfish
New poster
Posts: 18
Joined: Thu May 08, 2003 11:46 am

### 729 wa

I have tried all inputs that I can think of & all are right
why still wa?

#include<iostream>
#include<string>
using namespace std;

int c(int n,int h){
int result=n,i;
for(i=1;i<h;i++)
result=result*(n-i);
for(i=1;i<=h;i++)
result=result/i;
return result;
}

string binaryplus(string input){
int length=input.length();
int carry=1;
for(int i=length-1;i>=0;i--){
if(input=='0')
if(carry==1){
input='1';
carry=0;
}
else;
else if(carry==1)
input='0';
}
return input;
}

string next(string start,int h){
for(start=binaryplus(start);;start=binaryplus(start)){
int length=start.length(),k=0;
for(int i=0;i<length;i++)
if(start=='1')
k++;
if(k==h)
return start;
}
}

int main(){
int n,h,i;
while(cin>>n>>h){
if(n==0 || h==0)
continue;
string start;
for(i=1;i<=h;i++)
start=start+'1';
for(i=n-h;i>=1;i--)
start='0'+start;

for(i=c(n,h);i>=1;i--,start=next(start,h))
cout<<start<<endl;
}
return 0;
}