二分探索の練習問題
A - 二分探索の練習問題
O(logN)
import sys import math import heapq import itertools from collections import deque from functools import reduce # main def main(): N, K = list(map(int, input().split())) A = list(map(int, input().split())) l = -1 r = N while abs(r-l)>1: mid = (l + r) // 2 if A[mid] >= K: r = mid else: l = mid if r==N: print(-1) else: print(r) # エントリポイント if __name__ == '__main__': main()
C - Buy an Integer
O(logN)
import sys import math import heapq import itertools from collections import deque from functools import reduce # main def main(): A, B, X = list(map(int, input().split())) ok = 0 ng = 10**9 + 1 while abs(ok-ng) > 1: mid = (ok + ng) // 2 d = len(str(mid)) price = mid * A + B * d if X >= price: ok = mid else: ng = mid print(ok) # エントリポイント if __name__ == '__main__': main()
B - 花束
O(logN)
import sys import math import heapq import itertools from collections import deque from functools import reduce # main def main(): R, B = list(map(int, input().split())) x, y = list(map(int, input().split())) def check(X): r = R - X b = B - X if r<0 or b<0: return False num = r // (x-1) + b // (y-1) return (num>=X) ok = 0 ng = 10**18 + 1 while abs(ok - ng) > 1: mid = (ok+ng) // 2 if check(mid): ok = mid else: ng=mid print(ok) # エントリポイント if __name__ == '__main__': main()