시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)197523623.529%

문제

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

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

  • 생성되는 맵의 가장 왼쪽 아래 좌표는 $(0,0)$이고, 오른쪽 위 좌표는 $(h,w)$이다.
  • 쿠키의 초기 시작 위치는 $(0,0)$이며, 초기 시간은 $0$, 초기 점수는 $0$이다.
  • 팬케이크맛 쿠키는 $1$초당 $1$칸의 $x$ 좌표를 이동한다.
  • 팬케이크맛 쿠키가 능력을 사용하면 $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$ 인 각 시점 $t$에 대해서 $0 < t' < t$ 의 선택이 정해져 있을 때, $t$ 시점의 점수를 최대화하도록 능력 사용 여부를 결정한다. 만약, 두가지 이상 경로에서 얻을 수 있는 최대 점수가 같다면 더 빠른 시점에 능력을 사용하는 경로를 우선시한다. 위 경로를 저장하고 있는 PanCakeCookie 클래스를 구현해보자.

구현

  • C++11, C++14, C++17, C++20
    • 클래스 이름: PanCakeCookie
    • 생성자
      • PanCakeCookie(int w, int h ,int maxC, int u ,int d) : $y=1$ $h$ 인 지점들에 젤리가 배치된 맵이 생성된다. width는 $1\,000$보다 작거나 같은 정수, height는 $1\,000$보다 작거나 같은 정수이다. 이때, $y=0$인 지점은 젤리가 존재하지 않는다.
    • 멤버 변수
      • int w : 맵의 가로 크기
      • int h : 맵의 세로 크기
      • int x : 현재 팬케이크맛 쿠키의 x 좌표
      • int y : 현재 팬케이크맛 쿠키의 y 좌표
      • int t : 현재 게임이 진행된 시간
      • int score : 현재까지 팬케이크맛 쿠키가 획득한 점수
      • int maxC : 팬케이크맛 쿠키가 능력을 발동 할 수 있는 최대 시간, $1$보다 언제나 크거나 같다
      • int curC : 팬케이크맛 쿠키가 능력을 발동 할 수 있는 남은 시간, 초기 상태는 maxC와 동일하다
      • int u : 팬케이크맛 쿠키가 능력 사용 시 올라가는 최대 칸수, $1$보다 언제나 크거나 같으며 $1\,000$보다 언제나 작거나 같다.
      • int d : 팬케이크맛 쿠키가 능력 미사용 시 감소하는 칸수, $1$보다 언제나 크거나 같으며 $1\,000$보다 언제나 작거나 같다.
    • 멤버 함수
      • int getX() : 현재 팬케이크맛 쿠키의 x 좌표를 리턴한다.
      • int getY() : 현재 팬케이크맛 쿠키의 y 좌표를 리턴한다.
      • int getU() : 현재 설정된 팬케이크맛 쿠키가 능력 사용 시 올라가는 최대 칸수 u를 리턴한다.
      • int getD() : 현재 설정된 팬케이크맛 쿠키가 능력 미사용 시 감소하는 칸수 d를 리턴한다.
      • int getScore() : 현재 시간 t까지 획득한 점수를 리턴한다.
      • int getC() : 현재 남은 능력치 발동 시간을 나타낸다.
      • void reset() : 현재 팬케이크맛 쿠키를 초기 상태 (젤리 초기화, 점수 초기화, 좌표 초기화)로 만든다.
      • void setU(int x) : 팬케이크맛 쿠키 능력 사용 시 상승할 수 있는 최대 칸수 u를 x로 설정한다. 해당 수치가 조정되게 되면, 모든 게임 진행상태가 초기화된다. 이때, x는 $1$ 이상 $1\,000$ 이하의 정수여야 하며 올바르지 않은 값이 들어온다면 아무 수치도 변화시키지 않는다.
      • void setD(int x) : 팬케이크맛 쿠키 능력 미사용 시 하강하는 칸수 d를 x로 설정한다. 해당 수치가 조정되게 되면, 모든 게임 진행 상태가 초기화된다. 이때, x는 $1$ 이상 $1\,000$ 이하의 정수여야 하며 올바르지 않은 값이 입력된다면 아무 수치도 변화시키지 않는다.
      • voin setC(int x) : 팬케이크맛 쿠키 최대 능력 사용 시간을 x로 설정한다. 해당 수치가 조정되면, 모든 게임 진행 상태가 초기화된다. 이때, x는 $1$이상 $1\,000$이하의 정수여야 하며 올바르지 않는 값이 입력된다면 아무 수치도 변화시키지 않는다.
      • void setT(int t) : 게임의 진행상태를 t로 설정한다. t가 변경되면 x, y, curC, score 값이 모두 조건에 알맞게 변화된다. t가 음수이거나, w 이상일 경우는 아무 수치도 변화시키지 않는다.
  • Python3, PyPy3
    • 클래스 이름: PanCakeCookie
    • 생성자
      • def __init__(self, w: int, h: int, maxC: int, u: int , d: int) : $y=1$ $h$ 인 지점들에 젤리가 배치된 맵이 생성된다. width 는 $1\,000$ 보다 작거나 같은 정수, height는 $1\,000$ 보다 작거나 같은 정수이다. 이때, $y=0$ 인 지점은 젤리가 존재하지 않는다.
    • 멤버 변수
      • self.__w : 맵의 가로 크기
      • self.__h : 맵의 세로 크기
      • self.__x : 현재 팬케이크맛 쿠키의 x 좌표
      • self.__y : 현재 팬케이크맛 쿠키의 y 좌표
      • self.__t : 현재 게임이 진행된 시간
      • self.__score : 현재까지 팬케이크맛 쿠키가 획득한 점수
      • self.__maxC : 팬케이크맛 쿠키가 능력을 발동 할 수 있는 최대 시간, $1$보다 언제나 크거나 같다.
      • self.__curC : 팬케이크맛 쿠키가 능력을 발동 할 수 있는 남은 시간, 초기 상태는 maxC와 동일하다.
      • self.__u : 팬케이크맛 쿠키가 능력 사용 시 올라가는 최대 칸수, $1$보다 언제나 크거나 같으며 $1\,000$보다 언제나 작거나 같다.
      • self.__d : 팬케이크맛 쿠키가 능력 미사용 시 감소하는 칸수, $1$보다 언제나 크거나 같으며 $1\,000$보다 언제나 작거나 같다.
    • 멤버 함수
      • def getX(self) : 현재 팬케이크맛 쿠키의 x 좌표를 리턴한다.
      • def getY(self) : 현재 팬케이크맛 쿠키의 y 좌표를 리턴한다.
      • def getU(self) : 현재 설정된 팬케이크맛 쿠키가 능력 사용 시 올라가는 최대 칸수 u를 리턴한다.
      • def getD(self) : 현재 설정된 팬케이크맛 쿠키가 능력 미사용 시 감소하는 칸수 d를 리턴한다.
      • def getScore(self) : 현재 시간 t까지 획득한 점수를 리턴한다.
      • def getC(self) : 현재 남은 능력치 발동 시간을 나타낸다.
      • def reset(self) : 현재 팬케이크맛 쿠키를 초기 상태 (젤리 초기화, 점수 초기화, 좌표 초기화)로 만든다.
      • def setU(self, x: int) : 팬케이크맛 쿠키 능력 사용 시 상승할 수 있는 최대 칸수 u를 x로 설정한다. 해당 수치가 조정되게 되면, 모든 게임 진행상태가 초기화된다. 이때, x는 $1$ 이상 $1\,000$ 이하의 정수여야 하며 올바르지 않은 값이 들어온다면 아무 수치도 변화시키지 않는다.
      • def setD(self, x: int) : 팬케이크맛 쿠키 능력 미사용 시 하강하는 칸수 d를 x로 설정한다. 해당 수치가 조정되게 되면, 모든 게임 진행 상태가 초기화된다. 이때, x는 $1$ 이상 $1\,000$ 이하의 정수여야 하며 올바르지 않은 값이 입력된다면 아무 수치도 변화시키지 않는다.
      • def setC(self, x: int) : 팬케이크맛 쿠키 최대 능력 사용 시간을 x로 설정한다. 해당 수치가 조정되면, 모든 게임 진행 상태가 초기화된다. 이때, x는 $1$이상 $1\,000$이하의 정수여야 하며 올바르지 않는 값이 입력된다면 아무 수치도 변화시키지 않는다.
      • def setT(self, t: int) : 게임의 진행상태를 t로 설정한다. t가 변경되면 x, y, curC, score 값이 모두 조건에 알맞게 변화된다. t가 음수이거나, w 이상일 경우는 아무 수치도 변화시키지 않는다.
  • Java 8, Java 8 (OpenJDK), Java11, Java15
    • 클래스 이름: Test
    • 생성자
      • Test(int w, int h ,int maxC, int u ,int d) : $y=1$ $h$ 인 지점들에 젤리가 배치된 맵이 생성된다. width 는 $1\,000$ 보다 작거나 같은 정수, height는 $1\,000$ 보다 작거나 같은 정수이다. 이때, $y=0$ 인 지점은 젤리가 존재하지 않는다.
    • 멤버 변수
      • int w : 맵의 가로 크기
      • int h : 맵의 세로 크기
      • int x : 현재 팬케이크맛 쿠키의 x 좌표
      • int y : 현재 팬케이크맛 쿠키의 y 좌표
      • int t : 현재 게임이 진행된 시간
      • int score : 현재까지 팬케이크맛 쿠키가 획득한 점수
      • int maxC : 팬케이크맛 쿠키가 능력을 발동 할 수 있는 최대 시간, $1$보다 언제나 크거나 같다.
      • int curC : 팬케이크맛 쿠키가 능력을 발동 할 수 있는 남은 시간, 초기 상태는 maxC와 동일하다.
      • int u : 팬케이크맛 쿠키가 능력 사용 시 올라가는 최대 칸수, $1$보다 언제나 크거나 같으며 $1\,000$보다 언제나 작거나 같다.
      • int d : 팬케이크맛 쿠키가 능력 미사용 시 감소하는 칸수, $1$보다 언제나 크거나 같으며 $1\,000$보다 언제나 작거나 같다.
    • 멤버 함수
      • int getX() : 현재 팬케이크맛 쿠키의 x 좌표를 리턴한다.
      • int getY() : 현재 팬케이크맛 쿠키의 y 좌표를 리턴한다.
      • int getU() : 현재 설정된 팬케이크맛 쿠키가 능력 사용 시 올라가는 최대 칸수 u를 리턴한다.
      • int getD() : 현재 설정된 팬케이크맛 쿠키가 능력 미사용 시 감소하는 칸수 d를 리턴한다.
      • int getScore() : 현재 시간 t까지 획득한 점수를 리턴한다.
      • int getC() : 현재 남은 능력치 발동 시간을 나타낸다.
      • void reset() : 현재 팬케이크맛 쿠키를 초기 상태 (젤리 초기화, 점수 초기화, 좌표 초기화)로 만든다.
      • void setU(int x) : 팬케이크맛 쿠키 능력 사용 시 상승할 수 있는 최대 칸수 u를 x로 설정한다. 해당 수치가 조정되게 되면, 모든 게임 진행상태가 초기화된다. 이때, x는 $1$ 이상 $1\,000$ 이하의 정수여야 하며 올바르지 않은 값이 들어온다면 아무 수치도 변화시키지 않는다.
      • void setD(int x) : 팬케이크맛 쿠키 능력 미사용 시 하강하는 칸수 d를 x로 설정한다. 해당 수치가 조정되게 되면, 모든 게임 진행 상태가 초기화된다. 이때, x는 $1$ 이상 $1\,000$ 이하의 정수여야 하며 올바르지 않은 값이 입력된다면 아무 수치도 변화시키지 않는다.
      • voin setC(int x) : 팬케이크맛 쿠키 최대 능력 사용 시간을 x로 설정한다. 해당 수치가 조정되면, 모든 게임 진행 상태가 초기화된다. 이때, x는 $1$이상 $1\,000$이하의 정수여야 하며 올바르지 않는 값이 입력된다면 아무 수치도 변화시키지 않는다.
      • void setT(int t) : 게임의 진행상태를 t로 설정한다. t가 변경되면 x, y, curC, score 값이 모두 조건에 알맞게 변화된다. t가 음수이거나, w 이상일 경우는 아무 수치도 변화시키지 않는다.

제한

각각 테스트 케이스당 능력치를 변화하는 멤버함수(setC, setU, setD)는 최대 $15$번 들어오며, 각 능력치 변화 이후 setT 함수는 최대 $100$회 호출된다. 즉, setT 함수는 최대 $1\ 500$회 호출된다.

첨부

다음 압축 파일에는 C++, python, java의 채점기, 예제 입력, class 탬플릿이 들어 있다.

제출할 수 있는 언어

C++17, Java 8, Python 3, PyPy3, C++11, C++14, Java 8 (OpenJDK), Java 11, C++20, Java 15