Need help with this programming problem

[kimchiboy03]

Hello, I am currently working on this programming problem: https://train.nzoi.org.nz/problems/794

My code seems to be working on test cases where n < 10,000 except for one.

Here is my code.

#include <iostream>
#include <cmath>

using namespace std;

double calcB(double a)
{
	double count = 1;
	while (a != 0)
	{
		if (fmod(a, 2) == 0)
		{
			count++;
		}

		a /= 2;
		a = floor(a);
	}

	return count;
}

int main()
{
	double n, x;
	cin >> n >> x;

	double even = 0, odd = 0;
	for (double i = 0; i < n; i++)
	{
		even += calcB(x + i * 2);
		odd += calcB(x + 1 + i * 2);
	}

	if (even > odd)
	{
		cout << "YES" << '\n';
	}
	else
	{
		cout << "NO" << '\n';
	}

	return 0;
}

If you want more explanation about my code, I will do so. Thanks in advance.

[salem c]

Please edit your post to include code tags (the <> icon).

[kimchiboy03]

Thanks for your reply. I have done so.

[salem c]

The problem almost certainly calls for you to work in integer arithmetic.

doubles have a finite precision (about 15 decimal digits).
The upper bound of x in your problem needs 19 decimal digits to store accurately.

For your very large values of x, x+1 == x, because the +1 is so insignificant compared to x itself.

This will mess up your maths.

[dhayden]

Consider the non-zero even number X and the odd number X+1. When computing their beauty score, X gets 1 immediately because it is even. X+1, being odd, does not.

Now divide them both by 2 and round down. You get the same value. For example, if X=10 then floor(10/2)==5 and floor(11/2)==5. Since the second value is the same, the calculation for beauty will be the same for both numbers from that point on. In other words:
if X is even and X>0 then beauty(X) == 1+beauty(X+1).

So if X>0 the answer is always yes.

What about when X==0? If N==1 then the answer is no, beauty(0)==1 and beauty(1)==1.
If N==2 then we have beauty(0)+beauty(2) == 3 compared to beauty(1)+beauty(3) == 2 so the answer is yes. For any value of N larger than 2 the answer is still yes.

So by my logic, the only case where you output NO is when N==1 and X==0. Maybe someone else can prove me wrong. Otherwise your main program could simply be:

unsigned long long X,N;
cin >> N >> X;
cout << (X==0 && N==1 ? "NO" : "YES") << '\n';

This will still fail for the case where x == 2⁶⁴ because unsigned long long is usually 64 bits. I suspect that this is a mistake in the problem. It probably means to restrict x to values less than 2⁶⁴

[kimchiboy03]

Thanks you salem c for letting me know about doubles. I didn't know that doubles had a finite precision.

Also, thank you dhayden. Your logic seemed to be working. I managed to get the full solution with it!

Cheers

[anup30]

i agree with dhayden in most part. but that's not a mistake, what you mentioned.