|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||4||3||3||75.000%|
One of the most popular attractions at the county fair is the climbing wall. Bessie wants to plan her trip up the wall in advance and needs your help.
The wall is 30,000 millimeters wide and H (1001 <= H <= 30,000) millimeters high and has F (1 <= F <= 10,000) hoof-holds at unique X,Y coordinates expressed in millimeters. 0,0 is at the ground level on the left side of the wall. Hoof-holds are separated by at least 300 millimeters since no cow can maneuver them if they are spaced too close! Bessie knows there is at least one way up.
Bessie, through techniques only she knows, uses successive single hoof-holds to climb the wall. She can only move from one hoof-hold to another if they are no more than one meter apart. She can, of course, move up, down, right, left or some combination of these in each move. Similarly, once she gets to a hoof-hold that is at least H-1000 millimeters above the ground, she can nimbly climb from there onto the platform atop the wall. Bessie can start at any X location that has a Y location <= 1000 millimeters.
Given the height of the wall and the locations of the hoof-holds, determine the smallest number of hoof-holds Bessie should use to reach the top.
3000 5 600 800 1600 1800 100 1300 300 2100 1600 2300