Codeforces Beta Round #60
Codeforces Beta Round #60
はい。
http://codeforces.com/contest/65
A. Harry Potter and Three Spells
implementation,math
ざっくりと大意
・aグラムの砂がbグラムの鉛に変わる??
・cグラムの鉛がdグラムの金に変わる??
・eグラムの金がfグラムの砂に変わる??
・ループで増やせれば'RON'、そうでなければ'Hermione'
方針のようなもの
・aからfまで試して砂が増えてるかどうかかな?と思ったら各々が0の場合が上手く処理を分けられなかった。
#!/usr/bin/env python # -*- coding: UTF-8 -*- import time import sys, io import re, math #start = time.clock() #n=int(raw_input()) l=[int(x) for x in raw_input().split()] #金が作れない場合 if l[3]==0: print'Hermione'; sys.exit() #金が無限に作れる場合 if l[2]==0: print 'Ron'; sys.exit() #鉛が作れないは、 金が作れないと同義に if l[1]==0: print'Hermione'; sys.exit() #砂がなしで鉛を作れるは、 金が無限に作れると同義に if l[0]==0: print 'Ron'; sys.exit() #最後に砂が0になってしまう場合 if l[5]==0: print'Hermione'; sys.exit() #最後に砂が無限に作れる場合 if l[4]==0: print 'Ron'; sys.exit() print 'Ron' if (l[0]*l[2]*l[4])<(l[1]*l[3]*l[5]) else 'Hermione'
参考先さま http://topcoder.g.hatena.ne.jp/nodchip/20110305
んんー、こういう流れの交換の時って ace<bdf だと増加って保証されるらしいっぽい。
最初の交換時に重さの変動がb/aの割合で、次は(b/a)d/cの割合でなのが式の書き方を変えるとbd/a*cなのかな。。。なるほどわからん。。。。
- Harry Potter and the History of Magic
brute force,greedy,implementation
ざっくり大意
・与えられるn個の年数をそのままor一箇所だけ変更して1000<=z<=2011の範囲で前年以上の数に変更できるか?方針のようなもの
・1の位、10の位〜を0-9の範囲で変更して、前年以上になったらbreakで探索終了。
・1000の位まで探し終わるまでに見つかったらansリストに入れる。ansリストが全ての年の分あれば順に出力。なければ'No solution'。
#!/usr/bin/env python # -*- coding: UTF-8 -*- import time import sys, io import re, math #start = time.clock() n=int(raw_input()) l,ans=[],[0] #l=[int(x) for x in raw_input().split()] for i in range(n): l.append(int(raw_input())) for i in range(len(l)): osu=l[i] ich=l[i]%10 chk=l[i]-ich for j in range(10): if 1000<=chk+j<=2011 and chk+j>=ans[-1]: if osu>=ans[-1]: osu=min(osu,chk+j) break else: osu=chk+j juu=l[i]%100 chk=l[i]-juu+ich for j in range(10): if 1000<=chk+j*10<=2011 and chk+j*10>=ans[-1]: if osu>=ans[-1]: osu=min(osu,chk+j*10) break else: osu=chk+j*10 hya=l[i]%1000 chk=l[i]-hya+juu for j in range(10): if 1000<=chk+j*100<=2011 and chk+j*100>=ans[-1]: if osu>=ans[-1]: osu=min(osu,chk+j*100) break else: osu=chk+j*100 sen=l[i]%10000 chk=l[i]-sen+hya for j in range(1,3): if 1000<=chk+j*1000<=2011 and chk+j*1000>=ans[-1]: if osu>=ans[-1]: osu=min(osu,chk+j*1000) else: osu=chk+j*1000 if osu>=ans[-1] and 1000<=osu<=2011: ans.append(osu) if len(ans)-1!=len(l): print 'No solution' else: for jk in range(1,len(ans)): print ans[jk]
調べる年の初期値が前年以上ではなくてchk+j〜で前年以上になる変更が見つかった時にosu=min(osu,chk+j*100)
というのが良くなかった。というかminで見る必要がない気がしてきた。。。