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

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

729 - The Hamming Distance Problem

Post by hsihsiwu »

I got Wrong Answer....Please Help Me....
#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
Location: Canada

Post by broderic »

Multiple input.

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

I still got Wrong Answer

Post by hsihsiwu »

I still got Wrong Answer...What's going on...I have checked all possible input on my computer, and all answers are right..... Please help me...!
#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

Post by Ivor »

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

Post by hsihsiwu »

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?

Post by pobuhov »

[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
ReadLn(Size,Count);
s:='';
For X:=1 to Size do S:=s+'0';
Find(1,Count);
Until EOF(Input);
end.[/pascal]

User avatar
cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

Post by cytse »

It is a "multiple input" problem, denoted by a blue tick next to the problem number in the problem list.

Read this for further information:
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

Post by Eric »

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

Post by Eric »

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

Post by little joey »

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.
I made the following change:
[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

Post by Eric »

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??

Post by jayd »

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

Post by afonsocsc »

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

Post by jayd »

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

Post by boatfish »

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;
}

Post Reply

Return to “Volume 7 (700-799)”