729 - The Hamming Distance Problem

[Leithian]

Hi all!

Could anyone give me some sample input and output on this one?

Chris

[rubendv]

I tested my program with a lot of examples, I have read the code and I don't see where the problem may be. Please, give it a look and help me out. Thanks!

#include <stdio.h>

#define MAXLENGTH (16)

char sequence[MAXLENGTH + 1];

int flag;

int done(int h){
int i, counter = 0;
for (i = 0; i < MAXLENGTH; i++)
if (sequence == '1')
counter++;
if (counter == h)
return 1;
else
return 0;
}

void nextSequence(int n, int h){
int i;
do{
for (i = MAXLENGTH - 1; i >= MAXLENGTH - n; i--){
if (sequence == '0'){
sequence = '1';
break;
} else{
sequence = '0';
while ((i > MAXLENGTH - n + 1) && (sequence == '1')){
sequence = '0';
i--;
}
if (sequence == '0')
sequence = '1';
else
flag = 1;
break;
}
}
} while(done(h) == 0);
}

int main(void){
int testCases, n, h, i;
sequence[MAXLENGTH] = '\0';
scanf("%d",&testCases);
for (; testCases > 0; testCases--){
scanf("%d%d",&n,&h);
flag = 0;
for (i = 0; i < MAXLENGTH; i++)
sequence = '0';
nextSequence(n,h);
while (flag == 0){
printf("%s\n",sequence + (MAXLENGTH - n));
nextSequence(n,h);
}
if (testCases > 1)
printf("\n");
}
scanf("%*c");
}

[Sedefcho]

1) This is a multiple input problem.

2) I will give you some test cases. I hope they will be useful.
See below.

3) By the way I have an "Accepted ( P.E. )" on this problem
and not a clean "Accepted". Just for your information.


4) If these test cases are not enough I can email you some
more, but I won't post them here as the output is just too large.

Code: Select all

The input/output is incorrect so it has been removed.

Please see https://www.udebug.com/UVa/729 instead.

[Sedefcho]

By the way read this thread too:
http://online-judge.uva.es/board/viewtopic.php?t=1069

It could be useful to you.

[rubendv]

Sedefcho, thank you very much for your input example.
I found the error.
Thanks a lot.

[Sedefcho]

Leithian, here you can find some test cases:

http://online-judge.uva.es/board/viewtopic.php?t=7570

Good Luck !

[adnan2nd]

Flonav,
Your program takes sevarel test cases and gives the output of the 1st case. This is wrong.when the 1st input is, suppose 5 2, after pressing Enter
just after 2 the output should be in the standard output. May be you have tested with file.

[sunnycare]

i want to know why i got P.E.

it seems if i submit a multiple input problem , i will got P.E.

need some sample ouput ......
(maybe i lose one blank line somewhere,i think) ..

[stubbscroll]

There should be a blank line between every test case in the output. Or, said in another way, there should be a blank line after each test case except the last one.

Here's one way to do it:

Code: Select all

scanf("%d",&cases); /* (or gets()/sscanf() or similar when needed) */
while(cases--) {
   /* read, process and output test case */
   if(cases) printf("\n");
}

[stubbscroll]

Some actual sample output for 729:

input:

Code: Select all

2

4 2

4 2

output:

Code: Select all

0011
0101
0110
1001
1010
1100
--> blank line
0011
0101
0110
1001
1010
1100 <- last line of input

[sunnycare]

thanks

i always add a blank line after the last output..

[infancy]

i complied it with vc++6.0 and g++, it was right, but when i submitted it, i got complie error.why?

#include <iostream>
#include <vector>

using namespace std;

void print_vector(vector<int> str)
{
while(!str.empty())
{
cout << str.back();
str.pop_back();
}
cout << endl;

}

void generate(vector<int>& str, int n, int h)
{
int i;
if(h == 0)
{
for(i = 0; i < n; i++)
str.insert(str.begin(), 0);
print_vector(str);
}
else if(n == h)
{
for(i = 0; i < n; i++)
str.insert(str.begin(), 1);
print_vector(str);
}
else
{
vector<int> tmp(str);
str.insert(str.begin(), 0);
generate(str, n - 1, h);
tmp.swap(str);
str.insert(str.begin(), 1);
generate(str, n - 1, h - 1);
}
}

int main()
{
vector<int> str;
int n, h, nCase;
cin >> nCase;
while(nCase--)
{
cin >> n >> h;
generate(str, n, h);
if(nCase > 0)puts("");
}
return 0;
}

[shamim]

I compiled your code in Linux, and it is fine. I guess yours is one of those rare compile errors. You better check the reply they send to your mail.

[infancy]

i complied it with vc++6.0 and g++, it was right, but when i submitted it, i got complie error.why?

#include <iostream>
#include <vector>

using namespace std;

void print_vector(vector<int> str)
{
while(!str.empty())
{
cout << str.back();
str.pop_back();
}
cout << endl;

}

void generate(vector<int>& str, int n, int h)
{
int i;
if(h == 0)
{
for(i = 0; i < n; i++)
str.insert(str.begin(), 0);
print_vector(str);
}
else if(n == h)
{
for(i = 0; i < n; i++)
str.insert(str.begin(), 1);
print_vector(str);
}
else
{
vector<int> tmp(str);
str.insert(str.begin(), 0);
generate(str, n - 1, h);
tmp.swap(str);
str.insert(str.begin(), 1);
generate(str, n - 1, h - 1);
}
}

int main()
{
vector<int> str;
int n, h, nCase;
cin >> nCase;
while(nCase--)
{
cin >> n >> h;
generate(str, n, h);
if(nCase > 0)puts("");
}
return 0;
}

[chunyi81]

I compiled your code using g++ 2.95 and I got the following compile error:
p729.cpp: In function `int main()':
p729.cpp:52: implicit declaration of function `int puts(...)'

I think you have to #include <cstdio>