結果

問題 No.78 クジ付きアイスバー
ユーザー lam6er
提出日時 2025-03-20 20:57:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 40 ms / 5,000 ms
コード長 2,952 bytes
コンパイル時間 240 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 54,176 KB
最終ジャッジ日時 2025-03-20 20:57:43
合計ジャッジ時間 2,970 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    N, K = map(int, sys.stdin.readline().split())
    S = sys.stdin.readline().strip()
    S = list(S)
    
    current_ate = 0
    current_bought = 0
    current_credit = 0
    pos = 0
    
    visited = dict()  # key: (credit, pos), value: (ate, bought)
    
    while current_ate < K:
        if pos == 0:
            # Check for possible steady state
            # Simulate the processing of the entire box starting from current_credit
            simulated_credit = current_credit
            purchase_occurred = False
            for i in range(N):
                if simulated_credit == 0:
                    purchase_occurred = True
                    break
                simulated_credit -= 1
                simulated_credit += int(S[i])
            if not purchase_occurred and simulated_credit >= current_credit:
                # Steady state detected
                remaining = K - current_ate
                boxes_needed = remaining // N
                if remaining % N != 0:
                    boxes_needed += 1
                # Calculate how many boxes we can take without exceeding K
                possible_ate = boxes_needed * N
                if current_ate + possible_ate > K:
                    boxes_needed = (K - current_ate + N - 1) // N
                current_ate += boxes_needed * N
                # Since all are processed with credits, no new bought
                current_credit = simulated_credit  # Update credit for consistency, though not used further
                break  # Exit loop as we've reached/exceeded K
        
        key = (current_credit, pos)
        if key in visited:
            # Cycle detected
            prev_ate, prev_bought = visited[key]
            cycle_ate = current_ate - prev_ate
            cycle_bought = current_bought - prev_bought
            if cycle_ate <= 0:
                break  # No progress, avoid infinite loop
            # How many cycles can we do?
            remaining = K - current_ate
            cycles = remaining // cycle_ate
            if cycles > 0:
                current_ate += cycles * cycle_ate
                current_bought += cycles * cycle_bought
            # If still not enough, proceed to handle remaining steps
            if current_ate >= K:
                break
            # Reset visited to find new cycles
            visited = {}
        else:
            visited[key] = (current_ate, current_bought)
        
        # Process next ice
        ice = S[pos]
        if current_credit > 0:
            current_credit -= 1
            current_ate += 1
            current_credit += int(ice)
        else:
            current_bought += 1
            current_ate += 1
            current_credit += int(ice)
        pos = (pos + 1) % N  # Move to next pos, wrap around at N
        
        if current_ate >= K:
            break
    
    print(current_bought)

if __name__ == "__main__":
    main()
0