Thanks to Clive Fraser for creating this problem! Preface for it could be found in the forum.
In the land of Erewhon the people are excited because it is Election Day. There are only two political parties in the Land. One is the Technology Party whose main aim is to improve the country through the development of advanced technology. The other party is the Environmental Party whose main aim is to care for the environment and to develop sustainable systems. While the parties have many aims in common they also have significant differences, particularly in the methods by which they seek to achieve their aims.
The Land is divided into a number of large towns. For electoral purposes the region around each large town is
regarded as part of that town. Every part of the country is linked to one of these towns. Voting takes place
separately in each town. A simple majority of votes within that town determines the party which will represent
the town. In the case of a dead heat the representation passes to the party which does not currently represent
the town. However, the likelihood of a dead heat is so small that it has never yet occurred in the Land of
Erewhon. So we can safely neglect it! The town is given a number of seats in the Erewhon Parliament. Each seat
will be given to a member of the Party which won the Election in the town. The number of seats for the town is
proportional to the population of the town. The town of Beauville has 12 seats in the Erewhon Parliament.
At the last Election the Technology Party won in Beauville so Beauville sends 12 Technology Representatives
to the Parliament. The Party which forms the government of the country is the party with the most seats
(or Representatives) in the Parliament. The total number of seats is an odd number so it is not possible for
this part of the process to be a dead heat. However, a Party with a majority of 1 single seat will find it
almost impossible to govern the country. It is widely regarded that a working majority is a minimum of 20
seats. As the majority gets progressively smaller than this it gets more and more difficult to pass legislation.
So, for a working majority we need the winning Party to have at least 20 more seats than the losing Party.
On the day of the Election, when voting closes, the votes in each town are counted using a manual system.
This takes several hours to complete. The first results are ready about 2 hours after voting closes.
Several more hours elapse before most of the results are declared. The people of Erewhon are very excited to
know the result of the Election, so much so that many stay awake all night to listen to the results for each
town as they are announced. To provide all of this information, the TV company runs a special programme from
the moment that voting closes to the time when all of the results are declared. During the day of the Election
teams of statisticians are sent to each town to carry out an exit poll. Random people from the town are asked
how they voted. From this information the statisticians can use a clever algorithm to calculate the
probabilities that each of the two Parties will win the election in the town. Note that, since one of the two
Parties must win, the two probabilities must add to 100%.
The television programme which starts after voting has closed is able to use all of the results from these statistical calculations. While the viewers are waiting for the actual Election results to start coming in, they are given all of the predictions. Apart from the predictions for the individual towns the television programme is able to give predictions for the outcome of the entire Election. Among these predictions are the expected number of seats to be won by each party and the probability of each party winning the Election. As it is so important to have a working majority the viewers are also given the probabilities of each party having a working majority.
Your task is to carry out these calculations for the Technology Party. You are asked to find the expected number
of seats won by the technology Party, the probability that the Technology Party wins the Election and the
probability that the Technology Party wins the Election with a working majority. The example given below is a
very small version of the full problem. It has only 4 towns, which should make it easy to test out your ideas.
The full problem is likely to have slightly more than 100 towns.
Input/Output description: The first line of the input data will be a single integer N for the number of
towns in Erewhon. The next line consists of N space-separated integers. These are the numbers of
Parliamentary seats allocated to each of the towns. The third and final line of data consists of N
space-separated integers. These are the probabilities (given as a percentage) that the Technology Party will be
the winners in the corresponding town. (The order of the probabilities matches the order of the towns given in
the previous list) Your answer will consist of 3 numbers, separated by spaces, within a single string.
The first number is the expected number of Parliamentary seats won by the Technology Party (rounded to 2
decimal places). The second is the probability that the Technology Party wins the Election (given as a
percentage and rounded to 4 decimal places). The third is the probability that the Technology Party wins the
Election with a working majority (given as a percentage and rounded to 4 decimal places).
Example:
input:
4
78 74 86 73
79 47 75 29
answer:
182.07 71.7652 41.7929