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

Автор ToujoursAffame, история, 8 лет назад, По-английски

I saw this question on Hackerearth in a recent college contest .Link is here.(Editorial is not available).Can someone please help me here. I think this is related to linearity of expectation values ,But How do we model this problem in that way??? Please share your approach to this problem :) Thanks in advance ...

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

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

I'd think you solve it like this: First note that every single coin has the same probability of being head/tails (H and 1-H). You have heads[i] which is the probability of getting heads.

heads[0]=1.0

heads[i]=heads[i-1]*probability of not choosing this coin+(1-heads[i-1])*probability of choosing this coin

The answer would simply be n*heads[k]

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

    Thanks for the reply tfg but Can you elaborate about heads[i] here ??? What does it means ??

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

      The probability of the coin being heads after turning a[1], a[2], ..., a[i]. So 1-heads[i] is the probability of it being tails.