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

A. Vladik and flights

ざっくりと大意

・全体で長さがn、現在地がaで目的地がb。
・1から1、0から0は同じ数字なら離れていても無料で移動できる。違う数へ移動する時は位置の差分の絶対値だけコストがかかる。

Python2

s=raw_input()
print 0 if s[a-1]==s[b-1] else 1

解は0か1しか存在しない。例えば現在地が0で目的地が1ならば、現在地0からどこかの1と隣あっている0へ無料で移動して、コスト1で隣の1へ移動する。その後は目的地の1へ無料で移動できる。0,1が入れ替わっても同様に。

B. Chloe and the sequence

ざっくりと大意

・始めに1がある。次の手で未使用の最小の数の2を末尾に入れて、更に末尾に元々の1を入れて1,2,1になる。次の手で1,2,1に未使用の最小の数3と元々の1,2,1を入れると1,2,1,3,1,2,1になる。・n手目のk番目の数はいくつか。

Python2

n,k=map(int,raw_input().split())
print bin(k)[::-1].index('1')+1

手数には特に意味はなく3手目の2番目の数も4手目の2番目の数も同じである。k番目の数がどんな数かというのは2進数表記にした時の1の初回の出現位置が解になる。

C. Vladik and fractions

ざっくりと大意

・2/nが1/x + 1/y + 1/zと等しい関係になるようなx, y, zを探す。

Python2

n=int(raw_input())
if n!=1:
    print n,n+1,n*(n+1)
else:
    print -1

サンプル2がヒントとなっている。2/nを作るためには1/nと後2つで1/nを作れば和が2/nになる。
2/n = (1/n) + (1/b) + (1/(nb))
1/n = (1/b) + (1/(nb))
1/n = (n+1)/(n*b)
1 = (n+1)/b
b = n+1
ということらしい。

D. Chloe and pleasant prizes

ざっくりと大意

・参加者のための商品がn個でそれぞれに一意のidが1からnまで割り当てられている。
・賞品の良さは正の値、0、負の値で評価されている。
・後で