SRM490 - div2 - level two

srm490_div2_level2.py

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

"""SRM490 - div2 - level two

A new starport has just started working. Starting from some 
moment of time (call it minute 0), a new spaceship arrives 
at the starport every M minutes. In other words, spaceships 
arrive at the starport at minutes 0, M, 2*M, 3*M and so on.

Similarly, starting from minute 0 and repeating each N minutes, 
all arrived spaceships that are still placed at the port are 
teleported to the shed. If a spaceship arrives at the exact 
same minute when such a teleportation happens, it will be 
teleported immediately. Otherwise it will need to wait until 
the next teleportation happens.

Let the waiting time of a spaceship be the time between its 
arrival and its teleportation to the shed. Return the average 
waiting time of a spaceship in minutes. See notes for an exact 
definition. 

Definition:
    Class: Starport
    Method: getExpectedTime
    Parameters: int, int
    Returns: double
    Method signature: double getExpectedTime(int N, int M)

Notes:
    - Let W(i) be the waiting time for the spaceship that 
      arrives at minute M * i. The average waiting time 
      can be defined as the limit of 
      (W(0) + W(1) + ... + W(P - 1)) / P when P tends to 
      positive infinity. This limit will always exist.
    - The returned value must have an absolute or relative 
      error less than 1e-9.
"""

class Starport(object):
    """Star port

    Constraints:
        - N and M will each be between 1 and 1,000,000,000, 
          inclusive.

    >>> starport = Starport()
    >>> print starport.getExpectedTime(4, 2)
    1.0
    >>> print starport.getExpectedTime(5, 3)
    2.0
    >>> print starport.getExpectedTime(6, 1)
    2.5
    >>> print starport.getExpectedTime(12345, 2345)
    6170.0
    """

    def __init__(self):
        pass

    def getExpectedTime(self, N, M):
        def gcd(a, b):
            return b == 0 and a or gcd(b, a % b)
        return (N - gcd(N, M)) * 1.0 / 2

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