팬케이크맛 쿠키

쿠키런 오븐브레이크는 점프와 슬라이드로 젤리를 최대한 많이 획득해 최대 점수를 얻는 게임이다. 스탠딩벨은 가장 좋아하는 팬케이크맛 쿠키의 설정값($maxC$, $u$, $d$)을 바꿔 가며 점수가 얼마나 변하는지 실험하기로 했다.

팬케이크맛 쿠키를 실험하기 위해 가로 $w+1$, 세로 $h+1$ 크기의 맵에서 아래 조건에 따라 플레이한다.

• 생성되는 맵의 가장 왼쪽 아래 좌표는 $(0,0)$이고, 가장 오른쪽 위 좌표는 $(h,w)$이다.
• 쿠키의 시작 위치는 $(0,0)$이고, 초기 시간은 $0$, 초기 점수는 $0$이다.
• 팬케이크맛 쿠키는 1초에 x 좌표가 1칸씩 이동한다.
• 능력을 사용하면 $u$만큼 떠오른다. 현재 위치가 $(x, y)$이면 직선 경로로 $(x+1, y+u)$까지 이동한다. 이동하는 중 $y+u$가 설정된 높이 $h$보다 커지면 높이는 $h$로 유지된다.
• 능력을 사용하지 않으면 $d$만큼 가라앉는다. 현재 위치가 $(x, y)$이면 직선 경로로 $(x+1, y-d)$까지 이동한다. 이동하는 중 $y-d$가 설정된 바닥인 $0$보다 작아지면 높이는 $0$으로 유지된다.
• 능력을 사용할 때마다 능력치가 1 줄어든다.
• 능력을 사용하지 않은 경우 능력치가 1 회복된다.
• 능력치는 $maxC$를 넘을 수 없고, 능력치가 $0$이면 능력을 사용할 수 없다.
• 팬케이크맛 쿠키는 자신의 위치와 그 아래에 있는 젤리를 모두 먹는다.

이제 이 실험 환경에서 능력치 $maxC$, $u$, $d$를 조절하며 팬케이크맛 쿠키의 밸런스를 맞춰 보자. 아래 예시는 $w=4$, $h=5$, $u=3$, $d=1$, $maxC=2$로 설정된 맵에서 시점 $t$별 PanCakeCookie 클래스의 정보이다.

밸런스는 쿠키가 얻을 수 있는 최대 점수를 기준으로 맞춘다. 각 시점 $0 < t \leq w$에 대해 $0 < t' < t$의 선택이 정해져 있다고 보고, $t$ 시점의 점수가 최대가 되도록 능력 사용 여부를 정한다. 두 개 이상의 경로에서 얻는 최대 점수가 같다면 더 빠른 시점에 능력을 사용하는 경로를 우선한다. 이 경로를 저장하는 PanCakeCookie 클래스를 구현하라.

능력치를 바꾸는 멤버 함수(setC, setU, setD)는 테스트 케이스당 최대 15번 호출된다. 각 능력치 변경 이후 setT 함수는 최대 100번 호출된다. 따라서 setT 함수는 최대 $1\ 500$번 호출된다.