SRM493 - div2 - level two

srm493_div2_level2.py

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

"""SRM493 - div2 - level two

Romeo and his friend Strangelet are playing a game. 
There are N stones in a row, all of which are black 
except for the M-th one, which is white (all positions 
in this problem are 1-based). The players alternate turns, 
and Romeo plays first. On each turn, a player must 
choose exactly K consecutive stones, one of which must 
be white, and reverse their order. The winner is 
the first player who puts the white stone in 
the L-th position. Return "Romeo" if Romeo can win 
regardless of how Strangelet plays, and return "Strangelet" 
if Strangelet can win regardless of Romeo's strategy. 
Otherwise, return "Draw" since neither player can win 
if both players play optimally. All quotes are for 
clarity only.

Definition:
    Class: StonesGame
    Method: winner
    Parameters: int, int, int, int
    Returns: String
    Method signature: String winner(int N, int M, int K, int L)
"""

class StonesGame(object):
    """StonesGame

    Constraints:
        - N will be between 2 and 1,000,000, inclusive.
        - M, K and L will each be between 1 and N, inclusive.
        - M and L will be different.

    >>> game = StonesGame()
    >>> print game.winner(3, 1, 1, 2)
    Draw
    >>> print game.winner(5, 1, 2, 2)
    Romeo
    >>> print game.winner(5, 5, 2, 3)
    Strangelet
    >>> print game.winner(5, 5, 2, 2)
    Draw
    >>> print game.winner(1000000, 804588, 705444, 292263)
    Romeo
    >>> print game.winner(1000000, 100000, 500000, 600000)
    Strangelet
    """

    def __init__(self):
        pass

    def winner(self, N, M, K, L):
        def turn(N, M, K, L):
            if M > L:
                M = N - M + 1
                L = N - L + 1

            if L - M >= K \
                    or (L - M + 1) % 2 != K % 2:
                return False

            if K % 2:
                return 1 <= (M + L) / 2 - K / 2 \
                        and (M + L) / 2 + K / 2 <= N

            return 1 <= (M + L + 1) / 2 - K / 2 \
                    and (M + L) / 2 + K / 2 <= N

        if turn(N, M, K, L):
            return "Romeo"

        draw = False
        for i in range(N):
            if i + K -1 < M:
                continue
            if i > M or i + K - 1 > N:
                break
            if not turn(N, 2 * i + K - M - 1, K, L):
                draw = True
        return draw and "Draw" or "Strangelet"

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