Float vs Int mystics

general
, , , ,
1

Hi guys,

I’ve encountered a strange bug.
For the problem “Johnny and the Beanstalk” (or A2), this code is graded as “correct”

#include <iostream>
#include <stdio.h>

using namespace std;

inline void read(int *input)
{
	char ch = 0;

	while(ch<33){
		ch = getchar();
	}
	*input = 0;

	while(ch > 33)	{
		*input = *input * 10 + ch - '0';
		ch = getchar();
	}
}

int main()
{
	int case_num;
	read(&case_num);

	while(case_num){
		case_num--;

		int level_num;
		read(&level_num);
		
		float curr_stem_number = 1;

		for (int i = 0; i < level_num; i++){
			int leaf_num;
			read(&leaf_num);
			curr_stem_number = (curr_stem_number - leaf_num) * 2;
		}
		
		if (curr_stem_number == 0){
			cout << "Yes" << endl;
		}
		else{
			cout << "No" << endl;
		}
	}
}

The strange thing is, if I change the line 32 from
“float curr_stem_number = 1;” to “int curr_stem_number = 1;”,
the code is graded as “wrong answer”. This seems quite strange to me, since the curr_stem_number variable is initialized as an integer value 1, and the only actions applied to it are subtraction of another integer and multiplication by 2. Can anybody tell me what’s going on??

The code after the change:

#include <iostream>
#include <stdio.h>

using namespace std;

inline void read(int *input)
{
	char ch = 0;

	while(ch<33){
		ch = getchar();
	}
	*input = 0;

	while(ch > 33)	{
		*input = *input * 10 + ch - '0';
		ch = getchar();
	}
}

int main()
{
	int case_num;
	read(&case_num);

	while(case_num){
		case_num--;

		int level_num;
		read(&level_num);
		
		int curr_stem_number = 1;

		for (int i = 0; i < level_num; i++){
			int leaf_num;
			read(&leaf_num);
			curr_stem_number = (curr_stem_number - leaf_num) * 2;
		}
		
		if (curr_stem_number == 0){
			cout << "Yes" << endl;
		}
		else{
			cout << "No" << endl;
		}
	}
}
2

Hello,

This might be related with the compiler defined sizes of built-in types…

In fact, changing the variable type to the double floating point data type gets AC, which might mean that the sizes are not what you might expect…

After doing some research online, it seems that according to this answer, the maximum integer value which is admissible to be represented as integer is of about 223, which is less that the admissible value represented by the int data type and A LOT less than the double data type.

Hope this helps,

Bruno

3

Hi again,

I’ve checked it, and it seems that int would not overflow here.
This code:

#include <iostream>
#include <stdio.h>

using namespace std;

inline void read(int *input)
{
	char ch = 0;

	while(ch<33){
		ch = getchar();
	}
	*input = 0;

	while(ch > 33)	{
		*input = *input * 10 + ch - '0';
		ch = getchar();
	}
}

int main()
{
	int case_num;
	read(&case_num);

	while(case_num){
		case_num--;

		int level_num;
		read(&level_num);
		
		float curr_stem_number = 1;

		for (int i = 0; i < level_num; i++){
			int leaf_num;
			read(&leaf_num);
			curr_stem_number = (curr_stem_number - leaf_num) * 2;
			if (curr_stem_number > 2000000){
				curr_stem_number = 0;
				curr_stem_number /= 0;
			}
		}
		
		if (curr_stem_number == 0){
			cout << "Yes" << endl;
		}
		else{
			cout << "No" << endl;
		}
	}
}

still gives AC, which proves that the curr_stem_number value is never greater than 2 millions.
I still don’t see why integer doesn’t work…

4

Maybe you should check for negative overflow?