On the third sample input, I'm getting output 1 in my IDE. However, when I submit my solution, I get 2. https://codeforces.com/problemset/problem/1036/A

Why does this happen?

Code: https://codeforces.com/contest/1036/submission/108317612

# | User | Rating |
---|---|---|

1 | tourist | 3748 |

2 | Benq | 3540 |

3 | Petr | 3470 |

4 | Radewoosh | 3355 |

5 | ecnerwala | 3347 |

6 | maroonrk | 3345 |

7 | jiangly | 3324 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 200 |

2 | Errichto | 196 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

4 | awoo | 186 |

6 | Um_nik | 182 |

7 | vovuh | 179 |

8 | Ashishgup | 176 |

9 | -is-this-fft- | 173 |

9 | maroonrk | 173 |

On the third sample input, I'm getting output 1 in my IDE. However, when I submit my solution, I get 2. https://codeforces.com/problemset/problem/1036/A

Why does this happen?

Code: https://codeforces.com/contest/1036/submission/108317612

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/02/2021 20:07:05 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Huge floating-point numbers are very imprecise (and hardware-dependent?), don't use them. The correct way to take $$$\left\lceil {k \over n} \right\rceil$$$ is

`(k + n - 1) / n`

, where the division is in integers.This is true as far as it goes, but even knowing what I do about floating-point and numerical analysis, this particular wrong answer comes as a surprise to me. (Though of course I would expect other test cases on this problem to cause precision-related wrong answers from this code.)

The two numbers in the failing input "should" round to the same nearest double, which is exactly $$$10^{18}$$$. Even if excess precision is used, the division should not yield a result greater than $$$1$$$. The only explanation I can think of is that g++ may be rounding

`k`

to the nearest double at an intermediate step, but rounding`n`

directly to the nearest long double and performing (excess-precision) long double division, which seems shockingly inconsistent if true. (It continues to do this even for`k / double(n)`

, so the intermediate`*1.0`

is not causing the problem.) Either way, this is another good reminder that 32-bit g++ really demands its users fear the floating-point boogeyman.