2869 - 달팽이는 올라가고 싶다.

원 제목 : PUŽ

A는 낮에 올라갈 높이
B는 밤에 내려갈 높이
V는 넘어야 할 최소 높이(목표) 이다.

시뮬레이팅을 해보자면

   +A  -B  +A  +B  +A  -B  +A ...

이렇게 진행될 것이다. 즉 while( (res += (A-B)) < V ) 의 반복문일 것이다.

하지면 여기서 함정은 입력에 있다.
입력을 읽어보면 100,000,000 이다. 무려 10의 9승. 10^9 (비트연산자 XOR 아님)

반복문으로 시뮬레이팅을 하는 위 알고리즘은 O(N)의 시간복잡도를 가진다.
그럼 N ≤ 10^9 에 대해서는 분명 TLE(Time Limit Exceeded) 이다.

다시 살펴보자.

  +A  -B  +A  -B  +A  -B  +A ...

-B인 순간 달팽이가 V를 넘기진 않을 것이다. 바람이 불지 않는 이상
그럼 중요한 시점은 +A가 되는 순간이라는 건데, 달팽이의 현재 높이를 차례대로 나타내면 다음과 같다.

 A  A-B  A-B+A   A-B+A-B   A-B+A-B+A ...

즉, A + n*(A-B) 의 형태가 보인다. 여기서 n은 경과 일수(days)-1 을 의미한다.
A + n*(A-B) 가 V를 넘기는. 다시말해 A + n*(A-B) ≥ V 인 n 을 찾으면 끝난다.

n에 대한 방정식으로 바꾸자면
n ≥ (V-A) / (A-B)

소수점 처리를 잘 이용하면 정답 n을 찾을 수 있을 것이다.