729 - The Hamming Distance Problem

Moderator: Board moderators

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[i]=0;
k=15;
while(no>0)
{
str[k--]=no%2;
no/=2;
}
for(i=16-n;i<16;i++)
cout<<str[i];
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]
hsihsiwu
New poster

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

Multiple input.
broderic
New poster

Posts: 34
Joined: Thu Jun 06, 2002 4:35 am

#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[i]=0;
k=15;
while(no>0)
{
str[k--]=no%2;
no/=2;
}
for(i=16-n;i<16;i++)
cout<<str[i];
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;
}
hsihsiwu
New poster

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

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.
Ivor
Experienced poster

Posts: 147
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Thanks

I got it. Thank you very much......
hsihsiwu
New poster

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

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]
pobuhov
New poster

Posts: 1
Joined: Tue Oct 01, 2002 8:53 pm
Location: Ukraine,Odessa

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

cytse
Learning poster

Posts: 67
Joined: Mon Sep 16, 2002 2:47 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.
Eric
Learning poster

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

You use write(B[I]) 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[I]);
// Writeln;
setlength(line,n);
for i:=1 to n do line[i]:=chr(b[i]+ord('0'));
writeln(line);
Exit;
End
...[/pascal]
where line is a string.

Good luck.

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Thanks a lot~
These problems really teach me a lot.
Eric
Learning poster

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

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 ~!!
jayd
New poster

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

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...
afonsocsc
New poster

Posts: 34
Joined: Mon Mar 24, 2003 1:15 am
Location: Portugal, Lisbon

it should get a presentation error as you say

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

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

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[i]=='0')
if(carry==1){
input[i]='1';
carry=0;
}
else;
else if(carry==1)
input[i]='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[i]=='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;
}
boatfish
New poster

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

Next