8055번 - Polygons
문제 두 명의 플레이어가 Polygons라는 게임을 한다. 게임을 하려면 꼭짓점이 n개인 볼록 다각형이 하나 필요하며, 이 다각형은 n-3개의 대각선에 의해 n-2개의 삼각형으로 나뉘어 있다. 이 대각선들은 다각형의 꼭짓점에서만 서로 만날 수 있다.
n
n-3
n-2
이 삼각형들 중 하나만 검은색이고, 나머지는 모두 흰색이다. 플레이어들은 번갈아 가며 차례를 진행한다.
각 플레이어는 자신의 차례가 오면, 다각형에서 삼각형 하나를 잘라낸다. 삼각형은 주어진 대각선을 따라 잘라낼 수 있다. 검은 삼각형을 잘라내는 플레이어가 승리한다.
참고로, 어떤 다각형 안의 임의의 두 점을 잇는 선분이 항상 그 다각형 내부에 완전히 포함되면, 그 다각형을 볼록 다각형(convex polygon) 이라고 한다.
표준 입력으로 다각형의 설명이 주어질 때,
먼저 시작하는 플레이어가 이기는 전략을 가지고 있는지 판별하고,
그 결과를 표준 출력으로 출력하는 프로그램을 작성하라.
입력 첫째 줄에 정수 n이 주어진다. (4 ≤ n ≤ 50000) 이는 다각형의 꼭짓점 개수이다.
4 ≤ n ≤ 50000
다각형의 꼭짓점은 0부터 n-1까지 시계 방향으로 번호가 매겨져 있다.
0
n-1
다음 n-2개의 줄에는 다각형을 이루는 삼각형들의 정보가 주어진다.
i+1번째 줄 (1 ≤ i ≤ n-2)에는 공백으로 구분된 세 개의 음이 아닌 정수 a, b, c가 주어진다.
i+1
1 ≤ i ≤ n-2
a, b, c
이는 i번째 삼각형의 세 꼭짓점 번호를 의미한다.
i
주어지는 삼각형들 중 첫 번째 삼각형이 검은색이다.
출력 한 줄에 다음 둘 중 하나를 출력하라.
TAK : 먼저 시작하는 플레이어가 이기는 전략이 있는 경우 (TAK는 폴란드어로 “예”라는 뜻)
TAK
NIE : 먼저 시작하는 플레이어가 이기는 전략이 없는 경우 (NIE는 폴란드어로 “아니오”라는 뜻)
NIE
댓글을 작성하려면 로그인해야 합니다.
yimjunhyuck 8달 전 1
문제
두 명의 플레이어가 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는 폴란드어로 “아니오”라는 뜻)