[PKU] 2590 Steps
Posted 2008/07/24 15:23수직선 상에 시작점과 끝점이 주어진다. 두 점의 위치를 알았을 때 두 점 사이를 이동하는 최소 스텝수를 구하여라.
규칙
- 한 스텝 거리는 자연수로 이전 스텝 거리와 같거나 1만큼만 차이가 나야 한다.
- 스텝의 처음과 마지막은 반드시 1이어야한다.
다음은 x Step으로 갈 수 있는 최대거리를 미리 계산해 본 것이다.
step : 길이
0 step : 0
1 step : 1 (이전 Step + 1)
2 step : 2 (이전 Step + 1)
3 step : 4 (이전 Step + 2)
4 step : 6 (이전 Step + 2)
5 step : 9 (이전 Step + 3)
6 step : 12 (이전 Step + 3)
.........
증가치가 꾸준히 1, 1, 2, 2, 3, 3, .. 식으로 1부터 차례대로 2개씩 나타나는 것을 알 수 있다.
// No.2590 Steps
import java.util.*;
import static java.lang.System.*;
public class Main {
Scanner in = new Scanner(System.in);
public Main() {
int n = in.nextInt();
for(int i=0 ; i<n ; i++) {
start();
}
}
private void start() {
int gapOfPoints = -1*in.nextInt() + in.nextInt();
if(gapOfPoints == 0) {
out.println(0);
return;
}
int i=1;
for(int gapOfTemp=0 ; gapOfTemp<gapOfPoints ; i++)
gapOfTemp += Math.ceil(i/2.0);
out.println(--i);
}
public static void main(String[] args) {
new Main();
}
}
'C.S.E > Algorithm' 카테고리의 다른 글
| [PKU] 2590 Steps (0) | 2008/07/24 |
|---|---|
| [PKU] 1028 Web Navigation (0) | 2008/07/24 |
| [PKU] 1218 The Drunk Jailer (0) | 2008/07/23 |
| [PKU] 1003 Hangover (0) | 2008/07/23 |
| PKU Judge Online 소개 (0) | 2008/07/23 |
| [ACM] Problem B. Editor (0) | 2008/07/12 |
- Filed under : C.S.E/Algorithm
- Tag : Algorithm, PKU
- Comment Trackback
이올린에 북마크하기