2077번 - 싼데 비슷한 스페셜 저지

문제

메모리 제한에 유의하세요.

2077년, 신경계에 연결하여 움직임을 빠르게 하는 기계 장치 ’산데비스탄’이 개발되었다. 산데비스탄 제작에는 광물 X가 필수적으로 들어가는데, 문제는 이 광물의 가격이 매우 비싸다는 것이다. 어느 날 광물 X 대신 광물 Y를 사용해서 산데비스탄을 제작하는 방법이 발견되었다. 광물 Y의 가격은 광물 X의 가격보다 훨씬 저렴해 획기적인 방법이었다. 그래서 여러 회사들이 광물 Y를 채굴하기 위해 달려들기 시작했다.

광물 Y가 묻힌 광맥은 좌우로 길게 뻗은 일직선 형태이다. 광맥은 총 $N$개의 칸으로 이루어져 있으며, 왼쪽에서 $i$번째 칸에는 $A_i$만큼의 광물이 매장되어 있다. 첫 번째 칸($i=1$)은 이미 통로로 개발이 완료되어 더 이상 매장된 광물이 없으므로 $A_1=0$이다.

이 광물을 채굴하기 위해서는 ’장비’가 필요하며, 장비 하나로 장비가 설치된 칸 바로 옆의 오른쪽으로 연속한 최대 3칸의 광물을 모두 채굴할 수 있다. 이때 장비는 채굴할 구간의 맨 왼쪽 칸의 바로 왼쪽 칸(즉, 채굴할 구간의 왼 경계 직전 칸)에 설치해야 하며, 안전 규정상 장비가 설치된 칸에 묻힌 광물은 채굴할 수 없다. 또한 다른 장비에 의해 채굴되는 칸 위에도 장비를 설치할 수 없다.

총 광물 매장량을 $S=\sum_{i=1}^{N}A_i$라 하자. 이때 0ドル.75S$ 이상을 채굴할 방법이 존재하는지 판별하고, 만약 존재한다면 어떻게 장비를 설치하고 어떤 칸을 채굴할지 구해 보자!

예제 1을 시각화한 그림.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\le T\le 100,円 000)$

각 테스트 케이스마다 첫째 줄에 광맥의 길이 $N$이 주어진다. $(1\le N\le 20,円 772,円 077)$

둘째 줄에 광맥의 각 칸에 묻힌 광물의 양을 의미하는 $A_1,A_2,\dots ,A_N$을 공백을 사이에 두고 주어진다. $(0\le A_i\le 100,A_1=0)$

모든 테스트 케이스에서 $N$의 합은 20ドル,円 772,円 077$을 넘지 않는다.

출력

각 테스트 케이스마다, 만약 0ドル.75S$ 이상의 광물을 채굴할 방법이 없다면 첫 줄에 NO를 출력한다.

방법이 있다면 첫 줄에 YES를 출력한다. 그리고 둘째 줄에는 길이 $N$의 0-3 문자로 구성된 문자열을 출력한다.

$i$번째 칸이 채굴되지 않았다면 문자열의 $i$번째 문자는 0ドル$이다. 반면 $i$번째 칸이 채굴되었고, 그 칸을 채굴한 장비가 채굴한 영역의 길이가 $k$라면 문자열의 $i$번째 문자로 $k$를 출력한다.

제한

노트

이 문제는 SNUPC 2024의 히든 문제였습니다. 대회 포스터의 우하단을 참고하세요.