Journey to Mastery

시간 제한1초메모리 제한2048 MB

요약
더미의 행동 순서와 쿨다운 규칙이 주어질 때, 플레이어가 항상 더미보다 먼저 공격을 명중시킬 수 있는지 판정한다.
난이도

어려움10점 중 8점

유형
시뮬레이션, 게임 이론, 동적 계획법, 구현
정답자
아직 제출이 없습니다

문제

Your best friend Ken has really gotten into the new Street fighter game (Ultra Ultimate Street Fighter 2 Turbo Championship Edition DX+ \& Knuckles). Unfortunately, he is not very good yet, especially on defence, and really wants to attend the Fighting Pro Cup (FPC) in a few months. To get better, he has set up a training mode room where he can set a dummy computer player to fight him one on one using a specific set of actions. Reyn's goal is to consistently hit the training mode dummy without getting hit. To give him an example for how to always play optimally under these particular circumstances, you have decided to write a program that, provided with any computer player actions, always hits the dummy with an attack first.

The fight starts with the player and the dummy nn spaces away from each other. They then proceed to take turns taking actions at a regular interval of 11 unit of time (the dummy takes an action, then the player takes an action 11 unit of time later, followed by the dummy taking an action 11 unit of time after that). The completion of every action takes two units of time, *but some moves have an additional cooldown of \mathit{2* or 4\mathit{4} units of time after the move is finished}, in which no action can be taken, effectively "skipping" the user's next move(s). The player and the dummy both have a predetermined set of actions to choose from, detailed below:

Training Mode Dummy:

  • Walk Forward ("W")
    • The user slowly moves a single space toward the opponent. If this action is performed when already 11 space away from the opponent, it does nothing.
  • Jump Forward and Kick ("J")
    • The user makes a swift leap, moving 22 spaces towards the opponent, then performs a kick 11 unit of time after the action has been initiated. Since the user is in the air, the jump is able to avoid any "Hadouken" attacks for the duration of the action. If the opponent is 11 space away, after the leap, the kick attack will connect and end the game. If before the start of the action, players are 11 unit away, the dummy will jump over the player and be 11 space away on the other side (functionally, the side does not matter). If the players is 22 spaces away, the jump will only travel 11 space and end up 11 space from the player.
  • Grounded Kick ("K")
    • The user performs a kick attack that hits the opponent if they are up to 22 spaces away, ending the game if it connects. The kick comes out 11 unit of time after the attack has been selected and lasts for the next 11 unit of time. Has a cooldown of 22 units of time after being used.
  • Hadouken ("H")
    • A blue fireball that fires immediately, after which it begins travelling horizontally across the screen at a speed of 11 space per unit of time (by the user's next action it will have traveled 22 spaces, and by their action after that it will have traveled 44 spaces). Hits grounded opponents when it reaches the space they are currently on, ending the game on contact. If a Hadouken comes into contact with an opposing Hadouken, the fireballs cancel each other out. Has a cooldown of 22 units of time after being used.

Player:

  • Nothing ("N")
    • The user stands completely stationary for the duration of this action.
  • Grounded Kick ("K")
    • Identical to dummy Grounded Kick.
  • Hadouken ("H")
    • Identical to dummy Hadouken.
  • Shoryuken ("S")
    • The user performs an inhumanly high leap upward, and performs an uppercut that hits an opponent 11 space away and ends the game on contact. The uppercut comes out immediately as the user selects the attack. For the first unit of time after this action is selected, the user is completely invulnerable to any attacks (so for instance, this move can be used in reaction to a "jump forward and kick" action, and if players are 11 space away by the time the Shoryuken action is taken, the human player wins, as they land the uppercut and are invulnerable to the kick). Has a cooldown of 44 units of time after being used.

예제3

  1. 예제 1

    입력
    3
    W
    K
    V
    
    예상 출력
    
    
    K
    
    
  2. 예제 2

    입력
    3
    K
    
    -
    
    V
    
    예상 출력
    
    
    H
    
    -
    
    
  3. 예제 3

    입력
    6
    H
    
    -
    
    W
    
    H
    
    -
    
    J
    
    V
    
    예상 출력
    
    
    H
    
    -
    
    H
    
    -
    
    H
    
    -