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

Require Help in Binary Search ( Problem C :-Fly)[Codeforces Round 499]
Автор sameer_hack, история, 6 лет назад, По-английски

I tried to solve this question using Binary Search. And I am not able to understand why one of my solutions is giving me the wrong answer while other got accepted.
Problem Link
Submission 1 (Wrong)
Submission 2 (Accepted)
Submission 3 (Accepted)

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

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

if(r>1000000000) ===> Can return the wrong result if you compare 1000000000.0 to 1000000000 due to floating point error

writing if(r>1000000000+0.000001) should be enough

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

WNG has already given the answer to your question, but I would like to add one more thing here. Although, I did the same mistake for this problem and got WA, after reading the editorial I came to know that the test actually was not needed at all. This is what the editorialist did: If any of the a[i]s or b[i]s is 1, then at that planet, with k units of fuel, and m (> 0) total mass, k units of fuel will never be able to lift m + k (> k) units of total mass of rocket, and in that situation the answer will be -1. In any other case (a[i] > 1 and b[i] > 1), we can find some amount k that can lift or land the total mass of rocket. So, in conclusion, if any of the a[i]s or b[i]s is 1, the answer is -1, else the answer exists and we don't need to check for the condition that involves comparison of floating point numbers, so we can directly output l or r.

→ Ответить