Street light bits
You are probably pretty familiar with easy high school tasks, such as:
You have 10 coins, each can fall either head or tails with the same probability. How many bits of information do you receive if you throw each one of them and see the result?
The answer is obviuos, 10 bits. This answer is based on assumption that we don't know anything about the likelihood of coin landing on heads or tails (fair coin).
But on "Pod gozdom" street, the situation is pretty different. There are N street lights and for each you know the probability of it being turned on. For example:
It is your task to determine how many bits of information do we get if we see the state of all N street lights, based on given probability percentages.
The test cases won't contain imposible cases (such as: the probabilitiy is 100% and the light is off).
3
1 30
0 80
1 60Output:
4.79586Hint: This task requires basical information theory knowledge. Bit can be defined as "factor of surprise". That means if something you didn't really expect happens, amount of received information is high. In the oposite side, if something highly expected happens, amount of received information is low, as you were almost sure it would happen.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.