Problems
BOJ 28915 Книжная полка

BOJ 28915 Книжная полка

문제 링크:

문제 내용

수직선 위에 도미노가 00과 rr의 위치에 하나씩 세워져 있습니다. 하나의 도미노의 높이는 hh이며, 두께는 무시합니다. 도미노가 쓰러질 때, 다음 도미노와 닿는 지점의 높이가 h2\frac{h}{2} 이상이면 다음 도미노가 쓰러지게 됩니다.

이때, 00의 위치에 있는 도미노를 쓰러뜨려서 rr의 위치에 있는 도미노가 쓰러지게 하기 위해 추가로 세워야 하는 도미노의 최소 개수를 구하세요. 도미노는 정수 좌표에만 세울 수 있습니다.

입력

첫 줄에는 짝수 정수 hh가 주어집니다. (2≤h≤1062 \le h \le 10^6)

두 번째 줄에는 정수 rr이 주어집니다. (1≤r≤1061 \le r \le 10^6)

출력

문제의 정답을 출력합니다.

문제 풀이

스포일러

다음 도미노가 쓰러지는 조건으로부터 두 도미노 사이의 최대 거리를 구할 수 있습니다. 두 도미노 사이의 거리가 xx일 때, 한 도미노가 다음 도미노에 닿은 시점에서 직각삼각형이 만들어지므로, 조건은 h2−x2≥(h2)2h^2 - x^2 \ge \left( \frac{h}{2} \right)^2가 됩니다. 이 조건을 충족하는 최대 xx는 브루트포스로 구할 수 있습니다.

이제 r≤xr \le x일 때 답은 0, x<r≤2xx < r \le 2x일 때 답은 1, …이므로 답은 ⌊r−1x⌋\left\lfloor \frac{r-1}{x} \right\rfloor가 됩니다.

Last updated on
BOJ 28835 Оптимальное перестроениеBOJ 28973 Разделение амулета