Блог пользователя txingml

Two ACs codes output different result
Автор txingml, история, 6 лет назад, По-английски

I found a very strange thing in Educational Codeforces Round 50 F. Relatively Prime Powers.

First, here is a AC code written by me. https://codeforces.com/contest/1036/submission/42680029

And If you add a line "assert(val != 999999999999999956LL);", then this code will fail on test 3. It means test 3 has a case that num = 999999999999999956. https://codeforces.com/contest/1036/submission/42680073

But This is another AC code written by @alonefight, https://codeforces.com/contest/1036/submission/42657108. I ran it in my local environment and compared with my code. The result is surprised.

I used the test case as follow. 1 999999999999999956

My result is 999999998998996625 But @alonefight's result is 999999998998996624

I submitted his code and it still passed all test case. https://codeforces.com/contest/1036/submission/42680102

FYI, my environment is macbook, clion, c++14.

Can anyone tell me why this strange thing happened?

  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by txingml (previous revision, new revision, compare).

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

In custom test his code gives 999999998998996625 with g++14 but in Clang++17 Diagnostics it gives 999999998998996624. I think it is smth like undefined behavior

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

This is really strange. I've tested his code in custom test under Clang++17 Diagnostics. And look at this pictures scrt(n) gives 999999999, but if i comment one line that doesn't influence to the output it outputs 1000000000! first, second

→ Ответить
»
6 лет назад, # |
← Rev. 6   Проголосовать: нравится +6 Проголосовать: не нравится

Thank you all for replying my question.

sqrt(999999999999999956LL) will get 1000000000.0000000000 in my environment, and sqrt((long double)999999999999999956) will get 999999999.9999999780.

So it seems that if we need to use sqrt() and trucate result into integer, we must do some check. Such as:

long long safe_sqrt(long long n) {
    long long res = sqrt((long double) n);
    if (res*res == n) return res;
    const long double eps = 1e-8;
    if ((long double)(res+1)*(res+1) < n + eps) return res+1;
    if ((long double)res*res + eps > n) return res-1;
    return res;
}
→ Ответить