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

AtCoder ABC 223 Doukasen
Автор zarkdavor, история, 3 года назад, По-английски

Does anyone has a proof of the formula for problem C, the time T that the two flames meet is expressed as follows:

$$$ T = \frac{1}{2} \sum_{i=1}^{N} \frac{A_i}{B_i} $$$

Thanks

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

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

Assume that left and right flame meet at point x , and the time in which left flame reaches the point x is the same time right flame takes . T[l] = T[r] = t , and total time it will take to burn complete system is T* which is summation of A[i] / B[i] , and now 2*t = T = > t = T/2

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

The main idea is that we can change the burning speed of all the fuses equal to 1. By doing this the new length of any ith fuse becomes (Ai/Bi) that is its length/speed.

suppose we call new length as upgraded length.

Now the problem reduces to a simpler problem that all the fuses has burning speed 1 and length equal to (Ai/Bi). Due to equal burning speed the two flames will meet at half of the total upgraded distance.

Hence , the given equation is proved.

I have tried my best to explain it :)

If u want u can cheak my submission too https://atcoder.jp/contests/abc223/submissions/26645120

→ Ответить