### Need help with this programming problem

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.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445`` ``````#include #include 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.
Last edited on
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.
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:
 ``123`` ``````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 == 264 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 264

Last edited on
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
i agree with dhayden in most part. but that's not a mistake, what you mentioned.
Topic archived. No new replies allowed.