SRM482 - div2 - level two

srm482_div2_level2.py

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

"""SRM482 - div2 - level two

A hallway is filled with lockers numbered 1 through N, 
initially all closed. Out of boredom, Dave and Earl 
decide to open all the lockers. They make multiple 
passes through the hallway, each beginning at locker 1. 
On the first pass, they open the first unopened locker, 
and every second unopened locker thereafter. On the 
second pass, they open the first unopened locker, 
and every third unopened locker thereafter. In general, 
on the nth pass, they open the first unopened locker, 
and every (n+1)th unopened locker thereafter.

For example, with 9 lockers, on the first pass they 
open 1, 3, 5, 7, and 9, leaving 2, 4, 6, and 8. On 
the second pass they open 2 and 8, leaving 4 and 6. 
On the third pass they open locker 4, and on the 
final pass locker 6.

You will be given N, the number of lockers. Return 
the number of the locker opened last.

Definition:
    Class: LockersDivTwo
    Method: lastOpened
    Parameters: int
    Returns: int
    Method signature: int lastOpened(int N)
"""

class LockersDivTwo(object):
    """Lockers Div Two

    Constraints:
        - N will be between 1 and 10000, inclusive.

    >>> lockers = LockersDivTwo()
    >>> print lockers.lastOpened(9)
    6
    >>> print lockers.lastOpened(42)
    42
    >>> print lockers.lastOpened(314)
    282
    """

    def __init__(self):
        pass

    def lastOpened(self, N):
        ret = 1
        for i in range(N):
            j = 1
            for k in [i-k for k in range(1,i)]:
                j = (j + k - 1) / k * k
            if j > N:
                break
            ret = j
        return ret

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