結果

問題 No.78 クジ付きアイスバー
コンテスト
ユーザー norioc
提出日時 2025-05-14 00:00:21
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,435 bytes
コンパイル時間 567 ms
コンパイル使用メモリ 82,908 KB
実行使用メモリ 84,292 KB
最終ジャッジ日時 2025-05-14 00:00:30
合計ジャッジ時間 8,036 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 1 TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

def floyds_cycle_finding(a0, f) -> tuple[int, int]:
    """
    フロイドの循環検出法
    a0 : 初期値
    f  : 次の値を求める関数
    return: tuple[サイクルに入るまでの長さ, サイクルの長さ]
    """
    x = y = a0
    while 1:
        x = f(x)
        y = f(f(y))
        if x == y:
            break

    x = a0
    head_len = 0
    while x != y:
        x = f(x)
        y = f(y)
        head_len += 1

    cycle_len = 0
    while 1:
        x = f(x)
        y = f(f(y))
        cycle_len += 1
        if x == y:
            break

    return head_len, cycle_len


def simulate(k, stock):
    buy = 0
    s = stock
    for i in range(k):
        if s > 0:
            s -= 1
        else:
            buy += 1

        s += ds[i % N]

    return buy, s


def box(stock):
    s = stock
    for i in range(N):
        if s > 0:
            s -= 1
        s += ds[i]

    return min(s, 100)


INF = 1 << 60
N, K = map(int, input().split())
S = input()
ds = [int(c) for c in S]

if K < 1000:
    buy, stock = simulate(K, 0)
    print(buy)
    exit()

head_len, cycle_len = floyds_cycle_finding(0, box)
buy, stock = simulate(head_len * N, 0)

k = K - (head_len * N)
tot_b = 0
s = stock
for _ in range(cycle_len):
    b2, s = simulate(N, s)
    tot_b += b2

t = k // (cycle_len * N + 10)

buy += tot_b * t
rest = k - (t * N)
for _ in range(rest):
    b2, s = simulate(N, s)
    buy += b2

print(buy)
0