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

Leithian
New poster
Posts: 2
Joined: Sat May 08, 2004 2:34 pm

Post by Leithian »

Hi all!

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

Chris

rubendv
New poster
Posts: 9
Joined: Mon Mar 15, 2004 10:23 pm

729 - Why Wrong Answer?

Post by 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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by 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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by 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
New poster
Posts: 9
Joined: Mon Mar 15, 2004 10:23 pm

THANKS!!!

Post by rubendv »

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

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

Leithian, here you can find some test cases:

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

Good Luck !

adnan2nd
New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Location: bangladesh,ctg
Contact:

Post by 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.
sobhani

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

729 Accepted but P.E

Post by 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
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by 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
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by 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
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

Post by sunnycare »

thanks

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

infancy
New poster
Posts: 4
Joined: Thu Oct 09, 2003 1:55 pm

729 why complie error

Post by 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
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by 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
New poster
Posts: 4
Joined: Thu Oct 09, 2003 1:55 pm

compile error: 729

Post by 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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by 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>

Post Reply

Return to “Volume 7 (700-799)”