SRM500 - div2 - level two

srm500_div2_level2.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-

"""SRM500 - div2 - level two

N friends (numbered from 0 to N-1) play a game called Mafia. 
The exact rules of the game are not important for this problem. 
What's important is that at some point in the game they will 
need to choose one player who will lose and leave the game.

It is known that some players have a definite opinion on who 
should lose. Their opinions are given in the int[] decisions, 
where each element corresponds to a single opinion and is the 
number of a player who should lose according to that opinion. 
All opinions in decisions belong to different players. If 
decisions contains less than N elements, then all other 
players do not have a definite opinion on who should lose.

In order to determine who will lose, one or more rounds of 
voting will be conducted. In each round, there's a set of 
players for whom the players are allowed to vote. The players 
in this set are called "vulnerable". It's impossible to vote 
for players not in this set. Before the first round of voting, 
all N players are included in this set.

All N players will vote in each round. The voting is held 
according to the following scheme:

    * First, each player who has a definite opinion on who 
      should lose is allowed to vote if the player he thinks 
      should lose is "vulnerable" in this round. All of these 
      players will vote according to their opinions.
    * Then all other players vote, in order. Each of them votes 
      for the "vulnerable" player who currently has the smallest 
      number of votes (only considering the votes in the current 
      round). If there are several such players, he/she chooses 
      one of them uniformly at random and votes for the chosen 
      player.
    * Once all players have voted, if there is only one player 
      who has the largest number of votes in the current round, 
      this player loses and leaves the game. In this case there 
      will be no more rounds of voting. Otherwise, the set of 
      "vulnerable" players in the next round is set to all 
      players who have the largest number of votes in the 
      current round.

If it is possible that an infinite number of voting rounds will 
be held, then return 0. Otherwise, consider an array containing 
exactly N elements, where the i-th element (0-based) is equal 
to the probability that the i-th player will lose. Return the 
maximum value among all elements of this array.

Definition:
    Class: MafiaGame
    Method: probabilityToLose
    Parameters: int, int[]
    Returns: double
    Method signature: double probabilityToLose(
        int N, int[] decisions)

Notes
    - The exact numbers of people to whom the opinions in 
      decisions belong are not relevant in this problem.
    - It is possible that a player will decide to vote against 
      himself (see example 0). It is also possible that a player 
      will have to vote against himself (if he is one of 
      "vulnerable" players who have the smallest number of votes 
      in the current round).
    - The returned value must have an absolute or relative error 
      less than 1e-9.
"""

class MafiaGame(object):
    """Chicken Oracle

    Constraints:
        - N will be between 2 and 500, inclusive.
        - decisions will contain between 1 and min(N, 50) elements, 
          inclusive.
        - Each element of decisions will be between 0 and N-1, 
          inclusive.

    >>> mafiagame = MafiaGame()
    >>> print mafiagame.probabilityToLose(3, [1, 1, 1, ])
    1.0
    >>> print mafiagame.probabilityToLose(5, [1, 2, 3, ])
    0.0
    >>> print mafiagame.probabilityToLose(20, 
    ...     [1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7, 18, 19, 0, ])
    0.0
    >>> print mafiagame.probabilityToLose(23, 
    ...     [17, 10, 3, 14, 22, 5, 11, 10, 22, 3, 14, 5, 11, 17, ])
    0.142857142857
    """

    def __init__(self):
        pass

    def probabilityToLose(self, N, decisions):
        votes = {}
        for d in decisions:
            if not votes.has_key(d):
                votes[d] = 0
            votes[d] += 1

        m = max(votes.values())
        if m==1: return 0.0

        c = len([k for k, v in votes.items() if v == m])

        s = c
        while s > 1:
            s = N % s
        if s==0: return 0.0

        return 1.0 / c

if __name__ == '__main__':
    import doctest
    doctest.testmod()