729 - The Hamming Distance Problem

[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[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]

[broderic]

Multiple input.

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

[Ivor]

You see the blue checkmark near the problem name?? It is a multiple input problem.

Ivor

[hsihsiwu]

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

[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]

[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]

How can I shorten the time?

[Eric]

I have changed the algorithm but still got TLE. Can anyone help me?
Is it the problem of handling the multiple inputs?

[little joey]

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

[Eric]

Thanks a lot~
These problems really teach me a lot.

[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]

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]

it should get a presentation error as you say

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

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