Codeforces Round #185

A. Whose sentence is it?

http://codeforces.com/contest/312/problem/A

You got the chat record of two of your friends Freda and Rainbow, by mere curiosity you want to classified the sentences by the following categories: (1) Written by Freda, (2) Written by Rainbow or (3) You don't know who is the writer.

To do that you know that Freda always says "lala." (without quotes) at the end of the sentence. Rainbow in the other hand, always says "miao." (without quotes)  at the beginning of the sentence.

This is an implementation problem. There are just 3 cases to consider:

(1) If the sentence begins with prefix "miao." and don't end with the suffix "lala.", then it was written by Rainbow.
(2) If the sentence ends with suffix  "lala." and don't begin with the prefix "miao.", then it was written by Freda.
(3) Otherwise, you don't know who is the writer of the sentence.

B. Archer

http://codeforces.com/contest/312/problem/B

There is a match of archery between SmallR and Zanoes, they try to shoot a certain target in turns, and SmallR shoots first. The probability that SmallR hits the target is of \(\frac{a}{b}\) while for Zanoes is \(\frac{c}{d}\). Given 4 integers \(a\), \(b\), \(c\), \(d\), return the probability of SmallR will win the match.

Let's first define some notation:

\(P(A) = \frac{a}{b}\) probability of SmallR hit the target
\(P(B) = \frac{c}{d}\) probability of Zanoes hit the target
\(1 - P(A)\) probability of SmallR don't hit the target
\(1 - P(B)\) probability of Zanoes don't hit the target
\(P(W)\)  probability of SmallR winning the archery match

Before writing any math, let's get some intuition about what is happening on each turn. There are 2 players shooting the target, that's give us 4 possibles outcomes:

(1) SmallR hits the target and Zanoes hits the target
(2) SmallR hits the target and Zanoes miss the target
(3) SmallR miss the target and Zanoes hit the target
(4) SmallR miss the target and Zanoes miss the target

Now because SmallR shoots first the probability of him winning in the first turn is equal to \(P(A) = \frac{a}{b}\).  If neither players win the match, or in other words, if SmallR and Zanoes both miss in the first turn, then, the probability that SmallR win in the second turn is \((1 - P(A)) \cdot (1 - P(B)) \cdot P(A)\).

Generalizing from the previous idea, we have that the probability that SmallR win in the \(k\)-th turn is: \( ((1 - P(A))(1 - P(B)))^{k-1} \cdot P(A)\)

This means that our answer, the probability of SmallR winning is given by the expression:
$$P(W) = \sum_{k=1}^{\infty } ((1 - P(A))(1 - P(B)))^{k-1} \cdot P(A)$$ If we look carefully this turn out to be an Infinite geometric series, so we can reduce the infinite series to the expression: $$\\ \sum_{k=0}^\infty ar^k = \frac{a}{1-r} \\ a = P(A) \\ r = (1 - P(A))(1 - P(B)) \\ \\ P(W) = \frac{P(A)}{1 - (1 - P(A))(1 - P(B))}$$