Codeforces Round #377 (Div.2) - 君はまるで砂漠に咲く、一輪の花。

A. Buy a Shovel

ざっくりと大意

・無限の10ルーブル硬貨とr枚の1ルーブル硬貨でをつかって、1つあたりkルーブルのシャベルを買う時にお釣りが発生しないようにするにはシャベルを幾つ買えばよいか。

　 Python2 　

r,k=map(int,raw_input().split())
for i in range(1,11):
    if r*i%10==k or r*i%10==0:
        print i
        break

10ルーブル硬貨のみ支払いでお釣り無しになるパターンがやや注意。それ以外はシャベルを1つずつ増やしていってルーブルの下一桁が0かkと同じになれば解になる。

B. Cormen — The Best Friend Of a Man

ざっくりと大意

・犬のCormenは2日の連続した日の間で少なくともkを運動しなければならない。
・運動予定表aで運動が足りない日にだけ最小限の加算をして、加算分の合計と最終の運動予定表を出力する。

Python2

n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=[0]*n
ans[0]=a[0]
for i in range(1,n):
    ans[i]=max(a[i],k-ans[i-1])
print sum(ans)-sum(a)
print ' '.join(map(str,ans))

C. Sanatorium

ざっくりと大意

・朝食前、昼食前、夕食前のいずれかのタイミングでsanatoriumへ来て、sanatoriumから帰る。
・食事をした回数のメモb,d,sがある。滞在中に食事を逃したかもしれない最小回数はいくつか。
　 Python2 　

l=map(int,raw_input().split())
l.sort()
ans=0
if l[2]!=l[1]:
    ans+=(l[2]-1)-l[1]
if l[2]!=l[0]:
    ans+=(l[2]-1)-l[0]
print ans

codeforcesに書かれているTutorialでは9シナリオと言っているがシナリオ？は8件しか無い気がする。もっと絞るとパターンは3通りしかなくなる。ソートして最大値との差分が(-1,-1,0), (-1,0,0), (0,0,0)の3通りしかない。例えば朝食前に来て当日昼食前に帰る1,0,0と、夕食前に来て翌日朝食前に帰る0,0,1は実質は同等の内容であるのでそれらを整理すると3通りに絞られる。よってb,d,sをソートして3通りシナリオ想定を比較し最小の値を出力すれば大丈夫そう。