結果
問題 | No.648 お や す み |
ユーザー |
|
提出日時 | 2020-12-07 10:37:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 38 ms / 2,000 ms |
コード長 | 1,445 bytes |
コンパイル時間 | 205 ms |
コンパイル使用メモリ | 82,136 KB |
実行使用メモリ | 54,804 KB |
最終ジャッジ日時 | 2024-09-17 13:45:11 |
合計ジャッジ時間 | 5,098 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 84 |
ソースコード
#二分探索from operator import floordiv,truediv,truth,not_from math import log'''domain:= 定義域が整数(0)or実数(1)searchtype:= T→Fで最大値(0)かF→Tで最小値(1)かf:= boolを返す関数(単調性が必要)(答えでtrueを返すように)l,r:= 探索範囲(l,rはsearchtypeの条件を満たすように)eps:= 誤差(整数なら1,実数なら誤差指定による)args:= fの引数(iterable)…f(i,args)という形にして展開する必要がある'''#答えはvalueに格納class binary_search:def __init__(self,domain,searchtype,f,l,r,eps,args=None):self.domain=domainself.searchtype=searchtypeself.f=fself.args=argsself.l,self.r=l,rself.iter=int(log((r-l)/eps,2.0))+5self.op1=[floordiv,truediv][domain]self.op2=[not_,truth][searchtype]self.value=self.calc()def calc(self):for _ in range(self.iter):diff=self.op1(self.r-self.l,2)bisection=self.l+diffif self.op2(self.f(bisection,self.args)):self.r=bisectionelse:self.l=bisectionreturn [self.l,self.r][self.searchtype]n=int(input())#i秒目、F→T、Tの最小def g(i):return i*(i+1)//2def f(i,args):return g(i)>=n#0でF、10**10でTb=binary_search(0,1,f,0,10**10,1)if g(b.value)==n:print("YES")print(b.value)else:print("NO")