📝 문제 정보
🧐 관찰 및 접근
- 집 - 토카 - 돌돌이 형태로 있는 것 같다.
- 매 수행마다 토카는 $B, B-K, B-2*K \cdots$ 만큼 움직이고, 돌돌이는 $D$만큼 계속 움직인다.
- 토카가 잡힌다면, 그 순간 토카가 움직인 길이는 $D$보다 작을 것이다.
- 따라서 토카가 어느 순간 잡혔다면, 토카와 돌돌이가 계속 움직인다고 가정하면 돌돌이는 토카보다 훨씬 왼쪽에 있게 된다.
- 따라서 시간에 토카와 돌돌이의 위치에 단조성이 존재한다.
- 이분 탐색을 이용할 수 있겠다.
- 토카가 집에 도착하지도 못하는 상황, $K$가 0인상황 등 여러가지 예외 상황을 조심하자.
💻 풀이
A, B = map(int, input().split())
C, D = map(int, input().split())
K = int(input())
# 토카가 집에 도착할 수는 있는가?
# B + (B-K) + (B-2K) + ... >= A
if K > 0: # K = 0이면 무조건 도착할 수 있음
cnt = B // K # B - cnt * K >= 0 인 최대 cnt
tot = B * (cnt + 1) - K * (cnt * (cnt + 1)) // 2 # B + (B-K) + ... + (B - cnt * K)
if tot < A:
print(-1)
exit(0)
# 토카가 집에 도착하는 타이밍이 돌돌이보다 이른가?
def toka_move(time):
if K > 0:
time = min(time, B // K + 1)
return B * time - K * (time * (time - 1)) // 2
ok, ng = 10**12, 0
# 토카가 집에 도착하는 가장 빠른 타이밍
while ok - ng > 1:
mid = (ok + ng) // 2
if toka_move(mid) >= A:
ok = mid
else:
ng = mid
if D*ok < A + C: # 아직 돌돌이가 도착하지 않았다면
print(ok)
else:
print(-1)