yimjunhyuck   8달 전

문제
두 명의 플레이어가 Polygons라는 게임을 한다.
게임을 하려면 꼭짓점이 n개인 볼록 다각형이 하나 필요하며, 이 다각형은 n-3개의 대각선에 의해 n-2개의 삼각형으로 나뉘어 있다. 이 대각선들은 다각형의 꼭짓점에서만 서로 만날 수 있다.

이 삼각형들 중 하나만 검은색이고, 나머지는 모두 흰색이다.
플레이어들은 번갈아 가며 차례를 진행한다.

각 플레이어는 자신의 차례가 오면, 다각형에서 삼각형 하나를 잘라낸다.
삼각형은 주어진 대각선을 따라 잘라낼 수 있다.
검은 삼각형을 잘라내는 플레이어가 승리한다.

참고로, 어떤 다각형 안의 임의의 두 점을 잇는 선분이 항상 그 다각형 내부에 완전히 포함되면, 그 다각형을 볼록 다각형(convex polygon) 이라고 한다.

표준 입력으로 다각형의 설명이 주어질 때,

  • 먼저 시작하는 플레이어가 이기는 전략을 가지고 있는지 판별하고,

  • 그 결과를 표준 출력으로 출력하는 프로그램을 작성하라.

입력
첫째 줄에 정수 n이 주어진다. (4 ≤ n ≤ 50000)
이는 다각형의 꼭짓점 개수이다.

다각형의 꼭짓점은 0부터 n-1까지 시계 방향으로 번호가 매겨져 있다.

다음 n-2개의 줄에는 다각형을 이루는 삼각형들의 정보가 주어진다.

  • i+1번째 줄 (1 ≤ i ≤ n-2)에는
    공백으로 구분된 세 개의 음이 아닌 정수 a, b, c가 주어진다.

  • 이는 i번째 삼각형의 세 꼭짓점 번호를 의미한다.

주어지는 삼각형들 중 첫 번째 삼각형이 검은색이다.

출력
한 줄에 다음 둘 중 하나를 출력하라.

  • TAK : 먼저 시작하는 플레이어가 이기는 전략이 있는 경우
    (TAK는 폴란드어로 “예”라는 뜻)

  • NIE : 먼저 시작하는 플레이어가 이기는 전략이 없는 경우
    (NIE는 폴란드어로 “아니오”라는 뜻)

댓글을 작성하려면 로그인해야 합니다.