JMK no matter what

스몰은 무조건 쉽게 짜보고 하드는 다시 짜는 전략으로. 쉬운 문제 세개였다.

Snapper Chain

시뮬레이션 해보면 켜져있다 = 1, 꺼져있다 = 0 으로 두면 0 부터 2^n-1 까지를 순환한다는 것을 알 수 있다. 스몰은 그냥 시뮬레이션으로 내고 라지는 다시 짜서 냄. ㅋ

스몰

lang:py
import sys
rl = lambda: sys.stdin.readline().strip()

t = int(rl())
for cc in range(t):
    n, k = map(int, rl().split())
    is_on = [False] * n
    for i in range(k):
        j = 0
        while j < n and (j == 0 or is_on[j-1] == True):
            j += 1
        for k in range(j):
            is_on[k] = not is_on[k]
        print is_on
    print "Case #%d: %s" % (cc+1, "ON" if all(is_on) else "OFF")

라지

lang:py
import sys
rl = lambda: sys.stdin.readline().strip()

t = int(rl())
for cc in range(t):
    n, k = map(int, rl().split())
    print "Case #%d: %s" % (cc+1, "ON" if (k+1) % (2**n) == 0 else "OFF")

Fair Warning

a+x 와 b+x 의 최대 공배수가 y 라고 하자. 그러면 (b+x)-(a+x)=b-a 도 y 의 배수여야 한다. 따라서 답이 되는 T 는 숫자들 차이간의 gcd 임이 당연. 만약 x년이 지나서 a 가 T의 배수가 되었다면, T는 주어진 숫자간 차이들의 공약수이므로 모두 T의 배수가 된다.

fractions.gcd 있다는걸 깜박하고 직접 코딩함 ㅡ,.ㅡ

lang:py
import sys
rl = lambda: sys.stdin.readline().strip()

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)

cases = int(rl())
for cc in range(cases):
    t = map(int, rl().split())[1:]
    t.sort()

    deltas = [a-b for a, b in zip(t[1:], t)]
    z = reduce(gcd, deltas)
    sol = max(z - (v % z) if v % z > 0 else 0 for v in t)

    print "Case #%d: %d" % (cc+1, sol)

Theme Park

시뮬레이션

lang:py
import sys
rl = lambda: sys.stdin.readline().strip()

t = int(rl())
for cc in range(t):
    r, k, n = map(int, rl().split())
    g = map(int, rl().split())
    sol = 0
    for i in range(r):
        sum = 0
        ride = 0
        while ride < n and sum+g[ride] <= k:
            sum += g[ride]
            ride += 1
        sol += sum
        g = g[ride:] + g[:ride]
    print "Case #%d: %d" % (cc+1, sol)

사이클 디텍션

lang:py
import sys
rl = lambda: sys.stdin.readline().strip()

t = int(rl())
for cc in range(t):
    r, k, n = map(int, rl().split())
    g = map(int, rl().split())

    lastSeen = [-1] * n
    rodeSoFar = [-1] * n

    beginWith = 0
    rides = r
    moneyEarned = 0
    while rides > 0:
        if lastSeen[beginWith] != -1:
            cycleLength = lastSeen[beginWith] - rides
            if rides >= cycleLength:
                cycleSize = moneyEarned - rodeSoFar[beginWith]
                cycles = rides / cycleLength
                """
                print "Cycle found: beginwith %d seen before" % beginWith
                print "cycleLength %d rides, cycle size %d" % (cycleLength,
                                                               cycleSize)
                print "%d rides remaining => %d cycles" % (rides, cycles)
                """
                moneyEarned += cycleSize * cycles
                rides -= cycleLength * cycles
                continue
        else:
            lastSeen[beginWith] = rides
            rodeSoFar[beginWith] = moneyEarned
        rideThisTime = 0
        rideUpto = beginWith-1
        groups = 0
        while groups < n and rideThisTime + g[(rideUpto+1) % n] <= k:
            rideUpto = (rideUpto+1) % n
            rideThisTime += g[rideUpto]
            groups += 1
        moneyEarned += rideThisTime
        """
        print ("starting from %d, %d people ride, next begin %d"
               % (beginWith, rideThisTime, (rideUpto+1)%n))
               """
        beginWith = (rideUpto+1) % n
        rides -= 1

    print "Case #%d: %d" % (cc+1, moneyEarned)