Eternal Masters

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

요약
공유 스택을 사용하는 대화형 카드 게임에서 Red나 White 중 한쪽을 선택해 최적의 전략으로 승리해야 한다.
난이도

어려움10점 중 9점

유형
게임 이론, 그리디, 정렬, 구현
정답자
아직 제출이 없습니다

문제

This is an interactive problem.

Two players, Red and White, are playing a game according to the following rules (inspired by the rules of "Magic: the Gathering"):

  • White has LL life total; LL is a positive integer.
  • Red's goal is to decrease LL to zero or below. White's goal is to prevent that.
  • Red has nn cards in her hand. The ii-th card can decrease LL by a positive integer r_ir\_i.
  • White has mm cards in her hand. The ii-th card can increase LL by a positive integer w_iw\_i.
  • Each card can only be played from hand at most once.
  • Players know each other's cards.
  • Red's and White's turns alternate; the first turn is Red's turn.
  • On each turn, the player whose turn it is can either play a card from her hand (if there is any) or pass.
  • There is a zone named "stack", much like a programmer's stack. Initially the stack is empty. Playing a card from the hand does not immediately trigger its effect. Instead, it causes the card to be placed on top of the stack. The stack is shared for both players' cards.
  • A pass causes the top card of the stack (which, as we can show, is always an opponent's card) to deal its effect. Then the card is removed from the stack and discarded.
  • If White's pass causes LL to become zero or less, White loses immediately.
  • If Red passes while the stack is empty, Red loses immediately.
  • It can be shown that every game will eventually end in one of the two ways described above.

Given LL, nn, rr, mm, and ww, select a player and play for that player against the interactor to win.

예제1

  1. 예제 1

    입력
    3
    6
    2
    2
    1
    9
    6
    
    play 2
    
    play 2
    
    play 6
    
    pass
    
    pass
    
    
    예상 출력
    
    
    
    
    
    
    
    White
    
    pass
    
    pass
    
    play 9
    
    pass
    
    win