結果
問題 | No.78 クジ付きアイスバー |
ユーザー |
![]() |
提出日時 | 2015-03-01 20:12:37 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 12 ms / 5,000 ms |
コード長 | 945 bytes |
コンパイル時間 | 107 ms |
コンパイル使用メモリ | 7,040 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2024-11-08 00:29:09 |
合計ジャッジ時間 | 1,669 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
N,K=map(int,raw_input().split()) S=raw_input() dp=[(0,0) for i in range(10*N+1)] rest = 0 lstart=-1 lend=-1 for i in range(1,10*N+1): if rest==0: dp[i]=(dp[i-1][0]+1,rest) else: dp[i]=(dp[i-1][0],rest) rest-=1 rest += ord(S[(i-1)%N])-ord("0") dp[i]=(dp[i][0],rest) if lstart == -1: for j in range(i-N,0,-N): if( dp[j][1]==dp[i][1] or dp[i][0]==dp[j][0] ): lstart=j lend=i #print i,"-",j break if K <= 10*N: print dp[K][0] else: #if K >= lend: dif=(K-lend) interval=lend-lstart times = dif/interval base= times*(dp[lend][0]-dp[lstart][0])+dp[lend][0] startline = lend+times*interval rest= dp[lend][1] for i in range(startline+1,K+1): #print base, if rest == 0: base+=1 else: rest-=1 rest += ord(S[(i-1)%N])-ord("0") print base