Technocup 2017 - Elimination Round 1 (Unofficially Open for Everyone, Rated for Div.2)
はい。
http://codeforces.com/contest/727
A. Transformation: from A to B
ざっくりと大意
・aを2倍にするか、10倍にして1を足す操作を繰り返してbになれるか。
Python2
a,b=map(int,raw_input().split()) ans=[str(b)] while 1: if b%10==1: ans.append(str(b/10)) b/=10 elif b%2==0: ans.append(str(b/2)) b/=2 else: print 'NO' break if b==a: print 'YES' print len(ans) print ' '.join(ans[::-1]) break if b<a: print 'NO' break
bからaに戻れるかを見たほうが楽な気がする。末尾1なら10で割る(10倍にして1を足すを戻す操作)か、偶数なら2で割る(2倍にするのを戻す操作)のをしていってaになるのかを確認すれば大丈夫そう。
B. Bill Total Value
ざっくりと大意
・商品名と金額が並んでいるので最後に総額を出力する。
・金額表記はドル部分が3桁ごとに'.'区切り、セント部分がある時はドルと'.'区切りで先頭0あり2桁表記する。
Python2
d=c=0 s=raw_input()+'$' tmp='' for i in s: if i.isdigit() or i=='.': tmp+=i elif len(tmp): if len(tmp)<=2: d+=int(tmp) elif tmp[-3]=='.': c+=int(tmp[-2:]) d+=int(tmp[:-2].replace('.','')) else: d+=int(tmp.replace('.','')) tmp='' d+=c/100 c%=100 ans='' if d==0: ans='0.' else: while d: if d>=1000: tmp='{0:03d}'.format(d%1000) ans=tmp+'.'+ans else: ans=str(d)+'.'+ans d/=1000 if c: print ans+'{0:02d}'.format(c) else: print ans.lstrip('0').rstrip('.')
金額をドルとセントに分けて総額のみを保存して繰り上がり分はドルに入れたり、ドル部分は%1000で余りを見て3桁ごとに'.'くぎりになるようにした。あとは先頭の0や末尾の.がWAの原因になることがあるのでそれの対策をする。
C. Guess the Array
ざっくりと大意
・flush操作をする対話式の問題。
・最初に持っている情報は配列aの長さnだけで、n回の問い合わせで配列の内容を推測する。
・問い合わせできるのはn回で? \(a_i\) \(a_j\) を問い合わせるとi番目とj番目の和が標準入力で返ってくる。
Python2
import sys n=int(raw_input()) l=[] ans=[0]*n for i in range(n): if i!=n-1: print '?',i+1,i+2 sys.stdout.flush() else: print '?','1','3' sys.stdout.flush() l.append(int(raw_input())) ans[0]=l[0]-(l[0]+l[1]-l[-1])/2 for i in range(1,n): ans[i]=l[i-1]-ans[i-1] print '!',' '.join(map(str,ans))
codeforcesでflush形式の問題を提出したのは初かもしれない。n回の問い合わせで数列aの内容を確定させる単純な問い合わせは1,2番目、2,3番目、3,4番目...1,3番目のn件にするのが最も単純だと思う。1,2番目、2,3番目の和から1,3番目を引くと2番目を2倍にしたものが残る。それを2で割れば2番目の数が定まる。そうすると他の1,3,4..と順に定まっていく。