In this problem many did binary search and calculated the value of the function and stored the values in doubles and compared the results.
Shouldn't there be precision errors? As you are multiplying something with like (1.99999)^100?
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 7 | cnnfls_csy | 3569 |
| 9 | ecnerwala | 3494 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | maomao90 | 160 |
| 3 | -is-this-fft- | 159 |
| 4 | atcoder_official | 158 |
| 4 | cry | 158 |
| 4 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | maroonrk | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 01.10.2024 22:31:11 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
Also why is the polynomial an increasing function? Because xy is greater than xy + 1 for x < 1.
At r=-1, the value of the polynomial is clearly positive, because cm is positive. And since there is only one root in the range -1<r<1, thus the polynomial has one root dividing the function into two parts. That is why you can do binary search.
what if the function has a double root
it's specified in the question that there is only one root in the range (-1,1)
But how can you guarantee the function is decreasing
If you directly try to find the value of (1.99999)^100 then it is not possible. So, what we can do is divide the whole equation by the highest power of (1+r) so that (1+r)^x for all x is in the denominator. Now we can define a variable denom = 1/(1+r) and if we do denom/=(1+r) for x times then it is equivalent to 1/((1+r)^x). We can use this value with the corresponding cost values.
okay, If u divide it with the highest power of (1+r) then the one which originally had power 0, now has power (1+r) ^ (-highest_power) . Now this value is very small! and again, shouldn't it cause precision errors?