아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

동전 더미

면접 대비

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

요약
n개의 동전 더미가 주어질 때, 서로 다른 두 비어 있지 않은 더미에서 동전을 하나씩 제거하는 과정을 반복해 모든 동전을 없앨 수 있는지 판정하고 가능한 이동 순서를 출력한다.
난이도

보통10점 중 5점

유형
그리디, 구현, 시뮬레이션, 수학
정답자
아직 제출이 없습니다

문제

A와 B는 nn개의 동전 더미를 사용한 협동 게임을 한다. 더미에는 11번부터 nn번까지 번호가 붙어 있다. 게임의 매 라운드에서 두 사람은 비어 있지 않은 더미를 하나씩 고르는데, 같은 더미를 고를 수는 없다. 그런 다음 고른 두 더미에서 동전을 하나씩 꺼내고 다음 라운드가 시작된다.

두 사람은 모든 동전을 꺼내면 게임에서 이긴다. 두 사람이 게임에서 이길 수 있는지, 이길 수 있다면 어떻게 플레이해야 하는지 구하시오.

입력

첫째 줄에는 동전 더미의 개수 nn이 주어진다. (2≤n≤502 \le n \le 50) 다음 줄에는 음이 아닌 정수 nn개 a1,a2,…,ana_1, a_2, \ldots, a_n이 주어지는데, aia_i는 ii번째 더미에 있는 동전의 개수이다. 동전의 총개수는 1 0001\,000 이하이다.

출력

두 사람이 게임에서 이길 수 있으면 첫째 줄에 "yes"를 출력하고, 이어서 이동을 설명한다. 그렇지 않으면 첫째 줄에 "no"를 출력한다. 이동을 설명할 때는 한 줄에 하나씩 출력하며, 각 이동은 두 개의 서로 다른 정수 aa와 bb (11 이상 nn 이하)로 나타내는데, 이는 두 사람이 aa번째 더미와 bb번째 더미에서 동전을 하나씩 꺼낸다는 뜻이다. 가능한 답이 여러 개라면 그중 아무거나 하나를 출력한다.

예제2

  1. 예제 1

    입력
    3
    1 4 3
    
    예상 출력
    yes
    1 2
    2 3
    2 3
    2 3
    
  2. 예제 2

    입력
    3
    1 1 1
    
    예상 출력
    no