만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

칠판 게임

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

요약
3N개의 정수를 두 플레이어가 번갈아 고르고 지웁니다. 첫 번째 플레이어가 빨간 원소의 합과 파란 원소의 합을 다르게 만들 수 있는지 판정합니다.
난이도

보통10점 중 7점

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

문제

Carlinhos와 Equalizer가 게임을 한다. 게임은 칠판에 적힌 정수 3N3N개로 시작한다. 그 후 다음 두 단계를 NN번의 라운드 동안 반복한다.

  1. 첫 번째 플레이어인 Carlinhos가 선택되지 않은 원소 하나를 골라 빨간 원으로 표시한다.
  2. 두 번째 플레이어인 Equalizer가 선택되지 않은 원소 두 개를 고른다. 그중 하나는 파란 사각형으로 표시하고, 나머지 하나는 칠판에서 지운다.

라운드가 모두 끝나면 칠판에는 빨간 표시가 된 원소 NN개와 파란 표시가 된 원소 NN개가 남고, 더 이상 둘 수 있는 수가 없다. 빨간 표시 원소의 합과 파란 표시 원소의 합이 다르면 Carlinhos가 이기고, 같으면 Equalizer가 이긴다.

그림은 첫 번째 예제에서 나올 수 있는 유일한 결과를 보여 준다. 이 경우 두 플레이어가 어떻게 두든 두 합이 모두 25가 되어 Equalizer가 이긴다.

입력

첫 번째 줄에 정수 NN (1≤N≤10001 \le N \le 1000)이 주어진다.

두 번째 줄에는 칠판에 처음 적혀 있는 정수 B1,B2,…,B3NB_1, B_2, \ldots, B_{3N} (−105≤Bi≤105-10^5 \le B_i \le 10^5)이 주어진다.

출력

두 플레이어가 최선을 다한다고 가정할 때 Carlinhos가 이길 수 있으면 대문자 "Y", 그렇지 않으면 대문자 "N"을 한 줄에 출력한다.

예제3

  1. 예제 1

    입력
    5
    5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
    
    예상 출력
    N
    
  2. 예제 2

    입력
    2
    1 2 4 8 16 32
    
    예상 출력
    Y
    
  3. 예제 3

    입력
    1
    2 3 3
    
    예상 출력
    Y