근수의 카드게임

면접 대비

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

요약
매 턴 승형이가 1, 2, 3 카드 중 하나를 없애면 근수가 남은 카드 하나를 골라 S에 더한다. 둘 다 최선으로 두고, S가 K를 넘으면 -1이 된다.
난이도

보통10점 중 6점

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

문제

근수와 승형이는 '근수의 카드게임3'을 즐기고 있다. 근수의 목표는 최종 점수 SS를 최대화하는 것이고, 승형이의 목표는 SS를 최소화하는 것이다. 초기값은 S=0S = 0이다. 게임은 총 NN턴 동안 진행되고 각 턴에는 다음 과정이 이루어진다.

  1. 세 장의 카드가 주어진다. 각 턴마다 11, 22, 33이 적힌 카드가 각각 한 장씩 주어진다.
  2. 승형이가 세 장의 카드 중 한 장을 제거한다.
  3. 근수가 남은 두 장의 카드 중 한 장을 골라 그 카드의 값을 SS에 더한다.

모든 턴이 끝난 뒤 최종 점수 SS가 KK를 초과하면 최종 점수 SS는 S=−1S = -1로 처리된다. 모든 정보는 모두에게 공개되어 있으며, 두 사람은 항상 최선의 전략으로 행동한다. 이때의 최종 점수 SS를 구하여라.

입력

첫째 줄에 진행할 게임의 턴 수 NN과 KK가 주어진다. (1≤N≤100,0001 \le N \le 100\\,000; 1≤K≤3N1 \le K \le 3N)

출력

근수와 승형이가 항상 최선의 전략으로 게임을 진행하였을 때, 최종 목표치 값을 구하여라.

예제2

  1. 예제 1

    입력
    1 2
    
    예상 출력
    1
    
  2. 예제 2

    입력
    2 1
    
    예상 출력
    -1