## 729 - The Hamming Distance Problem

Moderator: Board moderators

It is a multiple input problem, indicated by a blue tick next to the problem number.

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

cytse
Learning poster

Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong

### RTE ?

#include<stdio.h>

void prnt(int n, int r)
{
int i, lim, t, j;
int nOnes;
char str[18];

lim = 1 << n;
for( i = 0; i < lim ; i++ ) {
memset(str, '0', n);
j = n;
str[j--] = '\0';
t = i;
nOnes = 0;
while( t ) {
str[j--] = t%2+'0';
if( t%2 )
nOnes++;
t >>= 1;
}
if( nOnes == r )
printf("%s\n", str);
}
}

int main()
{
int n, r;

while( scanf("%d %d", &n, &r) == 2 ) {
if( !n )
return 0;
prnt(n, r);
}
return 0;
}

Why am I getting RTE ???
HELP PLZ
Suman[/c][/code]
sumankar
A great helper

Posts: 288
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta

### 729 : Help Anyone..

Cannot figureout what is wrong.....Plz help I have taken care of multiple inputs
[cpp]
# include<iostream.h>

int n,h,a[100];
int nt;

int main()
{
cin>>nt;
while(nt--)
{
cin>>n>>h;
for(i=0;i<=n;i++)
{
if(i<h) a[i]=1; else a[i]=0;
}
while(1)
{
if(a[n]==1) break;
for(i=0;i<n;i++)
{
cout<<a[n-i-1];
}
cout<<"\n";
for(i=0;i<n;i++)
{
if(a[i]==1 && a[i+1]==0) {a[i+1]=1;a[i]=0;break;}
}
}
if(nt) cout<<"\n";
}
return 1;
}

[/cpp]
...I was born to code...
aakash_mandhar
New poster

Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

Consider the sample input, there should be six line of output

0011
0101
0110
1001
1010
1100

0011
0101
0110
1010
1100

shamim
A great helper

Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Dhaka

My program works correct but gets time limit
Plz tell me How can i optimize it

Code: Select all
[pascal]
program n729;
var
a : array[1..1000] of byte;
h,i,n : integer;
totalnumber : integer;
tot : extended;
qurrent : integer;
qual,quality : integer;
procedure getnext;
var
i,j : integer;
onesnumber : integer;
begin
onesnumber := 0;
i := n;
while a[i] = 0 do dec(i);
j := i;
while a[j]=1 do
begin
dec(j);
inc(onesnumber);
end;
a[j] := 1;
for i := j+1 to n do a[i] := 0;
for i := n-onesnumber + 2 to n do a[i] := 1;
inc(qurrent);
end;

begin
{assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);}
for qual := 1 to quality do
begin
qurrent := 1;
fillchar(a,sizeof(a),0);
for i := n downto n-h+1 do a[i] := 1;
totalnumber := 1;
tot := 1;
for i := h+1 to n do
begin
tot := tot * i;
tot := tot/(n-i+1);
end;
totalnumber := round(tot);
while qurrent < totalnumber do
begin
for i:= 1 to n do write(a[i]);
writeln;
getnext;
end;
for i:= 1 to n do write(a[i]);
writeln;
writeln;
end;
end.

[/pascal]
Best reguards
LeoST
New poster

Posts: 7
Joined: Thu Dec 25, 2003 5:10 pm
Location: Russia

### :)

Hi!
I also had this problem, but when I change
[pascal]
for i:= 1 to n do write(a[i]);
writeln;
writeln;
[/pascal]
to
[pascal]
var s: string;
...
s:='';
for i:=1 to n do s:=s+chr( a[i] + 48 );
writeln(s);
if qual<quality then writeln;[/pascal]
And I`ve got AC(not PE) in 1 sec
pavelph
Learning poster

Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

I get Output Limit Exceeded with following code:
[cpp]#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
long h, n;
long data[200];

int main(){
while(cin >> n >> h){
memset(data, 0, sizeof(data));
for(long i = n - h; i < n; i++) data[i] = 1;
do{
for(long i = 0; i < n; i++) cout << data[i];
cout << endl;
}while(next_permutation(data, data + n));
}
return 0;
}[/cpp]
Can anybody tell me what's wrong with my code?
minskcity
Experienced poster

Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

This is a Multiple Input problem.
Raiyan Kamal
Experienced poster

Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm

Raiyan Kamal wrote:This is a Multiple Input problem.
Thx, now I got AC
minskcity
Experienced poster

Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

I get output limit exceeded as well, I'm not sure why. I handle multiple input, and it seems to output the right output in the case N = 16, H = 8.

[cpp]
#include <cstdio>
#include <vector>

using namespace std;

//int cnt = 0;

void doit(int l, int h, vector<char>& start) {
if (l == 0) {
for(int i=0; i<start.size(); ++i)
printf("%c",start[i]);
printf("\n");
//cnt++;
return;
}

if (l > h && h > 0) {
start.push_back('0');
doit(l-1, h, start);
start.pop_back();
start.push_back('1');
doit(l-1, h-1, start);
start.pop_back();
} else if (l == h) {
start.push_back('1');
doit(l-1, h-1, start);
start.pop_back();
} else if (h == 0) {
start.push_back('0');
doit(l-1, h, start);
start.pop_back();
}
}

int main() {
int c = 1;
int l, h;
while(scanf(" %d %d", &l, &h) == 2) {
if (c++ > 1)
printf("\n");
vector<char> str;
doit(l, h, str);
//printf("%d\n", cnt);
}
}
[/cpp]
Kevin Waugh
New poster

Posts: 4
Joined: Sun Feb 01, 2004 12:44 pm

Judge wants you to read number of inputs first..

meaning not:
[cpp]while(cin >> in){....}[/cpp]
but:
[cpp]cin >> n;
while(n--) {..}[/cpp]
you'll get AC
minskcity
Experienced poster

Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Fixed it .. Thanks
Kevin Waugh
New poster

Posts: 4
Joined: Sun Feb 01, 2004 12:44 pm

### 729 hamming distance HELP ME , why i get wrong answer?

# include <stdio.h>
void proceso();
int recur(int x);
int N,H,t;
int mat[20],auxn;
void main()
{int i,j;
scanf("%d",&t);
j=0;
while(j<t)
{scanf("%d %d ",&N,&H);
//scanf("%d",&N);
//scanf("%d",&H);
if(H==N)
{for(i=0;i<N;i++)
{printf("1");
}
printf("\n\n");
}
else proceso();
j++;
}
}
void proceso()
{int i,j;
for(j=0;j<N;j++) mat[j]=0;
auxn=1;
for(i=0;i<=(N-H);i++)
{mat[i]=1;
if(N-H==1)
{for(j=N-1;j>=0;j--)
{printf("%d",mat[j]);
}
printf("\n");
}
else recur(i+1);
mat[i]=0;
}
printf("\n");
}
int recur(int x)
{int i,j;
for(i=x;i<=(N-H+auxn);i++)
{mat[i]=1;auxn++;
if(auxn>=H)
{for(j=N-1;j>=0;j--)
{printf("%d",mat[j]);
//fprintf(hf2,"%d",mat[j]);
}
printf("\n");
//fputs("\n",hf2);
}
else recur(i+1);
mat[i]=0;auxn--;
}
return(0);
}
gsfsfws
flonav
New poster

Posts: 2
Joined: Mon Oct 25, 2004 7:01 am
Location: mexico

TRY
16 7...

That is funny test
Remember Never Give Up
Miras
miras
Learning poster

Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

what's so funny about 16 7? my code gives right output for that too
Jalal : AIUB SPARKS

CodeMaker
Experienced poster

Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm