729 - The Hamming Distance Problem

[cytse]

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

For more details about the input format of multiple input problem, please read this:
http://acm.uva.es/problemset/minput.html

[sumankar]

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

[aakash_mandhar]

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

int n,h,a[100];
int i,head;
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;
}
head=h-1;
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]

[shamim]

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

0011
0101
0110
1001
1010
1100

your code gives only five

0011
0101
0110
1010
1100

[LeoST]

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);}
  read(quality);
for qual := 1 to quality do
begin
  read(n,h);
  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]

[pavelph]

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

[minskcity]

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?

[Raiyan Kamal]

This is a Multiple Input problem.

[minskcity]

This is a Multiple Input problem.

Thx, now I got AC

[Kevin Waugh]

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]

[minskcity]

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

[Kevin Waugh]

Fixed it .. Thanks

[flonav]

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

[miras]

TRY
16 7...


That is funny test

[CodeMaker]

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