Testing Round #13
はい。
http://codeforces.com/contest/753
A. Santa Claus and Candies
ざっくりと大意
・サンタクロースがn個のアメをできるだけ多くの子に配りたい。
・だが配るアメの個数が同じ子なのはいないようにしたい。
Python3
n=int(input()) ans=[] t=n for i in range(1,n+1): if i==1: ans=[1] t-=1 elif t>=i: ans.append(i) t-=i else: ans[-1]+=t t=0 if t==0: break print(len(ans)) print(*ans)
アメを配る個数がめっちゃ不公平でいいのかよ。。。1,2...と総和がnに近づくまで配って端数は末尾に足せば大丈夫だと思う。必ず末尾でないといけないわけではないですけども、例えば端数1を末尾以外に足すと重複が発生するので再調整が必要になる。だが末尾なら再調整不要で終えられる。
B. Interactive Bulls and Cows (Easy)
ざっくりと大意
・インタラクティブ問題で数字当てゲーム。
・4桁の数字を作成してクエリを投げると、クエリ結果が2つの数で返ってくる。
・左の数は位置と数字が共にあっているものの個数、右の数は使われている数字だが位置があっていないものの個数。
・よって、クエリ結果が4 0となると特定成功で完了となる。
Python3
#!/usr/bin/env pypy3 # -*- coding: UTF-8 -*- tmp='0000' k='' chk=set() for a in '0123': for b in '0123': for c in '0123': for d in '0123': if len(set([a,b,c,d]))==4: chk.add(a+b+c+d) while 1: print(tmp, flush=True) a,b=[int(i) for i in input().split()] c='' if a==4 and b==0: break if len(k)<4: if a>0: k+=tmp[:a] tmp=str((int(tmp[0])+1)%10)*4 else: p=chk.pop() tmp=k[int(p[0])]+k[int(p[1])]+k[int(p[2])]+k[int(p[3])]
クエリ件数にかなり余裕があるのでどうにでもなると思う。0000など4桁とも同じ数字のクエリを投げて、1 0などを得ることで解となる数字列に何が何個含まれているかを特定する。これが10件くらい。
あとは構成する数字4個を総当りで作成して、これが24件くらい。クエリ上限50件なので多少重複で余計なクエリ投げても余裕ありだと思う。