시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 117 | 37 | 29 | 35.802% |
상수는 프로그래밍 대회 상품으로 타일들이 들어 있는 상자를 받았다. 이 타일들은 두 개의 정사각형 칸이 변을 맞대고 붙어 있는 직사각형 모양이고, 각 칸에는 정해진 개수만큼의 점이 찍혀 있다. 편의상 한 칸에는 a개, 다른 칸에는 b개의 점이 찍힌 타일을 (a, b) 타일이라고 하자.
타일 상자는 크기에 따라서 안에 들어 있는 타일들의 구성이 달라지며, 상수가 받은 타일 상자는 크기가 K인 상자이다. 이 상자에는 1 ≤ a ≤ b ≤ K를 만족하는 모든 정수 쌍 a, b에 대해 (a, b) 타일이 각각 하나씩, 총 K(K+1)2개의 타일이 들어 있다.
K = 4인 경우의 예시
머릿속이 온통 알고리즘 문제뿐인 상수는 타일의 모양을 보자마자 유명한 “2×N 타일링” 문제가 생각났다. 그래서 상수도 상자에 들어 있는 타일들 중 M개의 타일을 골라서 2 × M 격자판을 채워 보기로 했다.
타일을 놓을 때는 반드시 격자판의 칸에 맞춰서 놓아야 하며, 가로로 놓을지 세로로 놓을지는 자유롭게 정할 수 있다. 같은 방향이더라도 타일을 180도 돌려서 두 칸의 순서를 바꿔서 놓을 수도 있다. 당연히 타일이 격자판을 벗어나거나 두 타일이 겹쳐서는 안 되고, 따라서 M개의 타일을 올바르게 놓으면 2M개의 칸을 전부 덮게 된다.
그러나 단순히 격자판을 채우는 것은 너무 쉽다고 생각한 상수는 타일들에 찍혀 있는 점들을 이용해서 다음과 같은 조건들을 추가로 만들었다.
상수가 주어진 조건에 맞게 격자판을 채울 수 있을지 알아보자.
첫 줄에 두 개의 정수 K과 M이 공백을 사이에 두고 주어진다. K는 상수가 받은 타일 상자의 크기, M은 상수가 채우려는 격자판의 너비를 의미한다.
상수가 조건에 맞게 격자판을 채울 수 있다면 첫 줄에 YES
를 출력한다. 그리고 다음 두 줄에 걸쳐 각 줄에 격자판의 각 칸에 찍혀 있는 점의 개수를 의미하는 M개의 정수를 공백으로 구분하여 출력한다. 단, 해당 칸을 덮는 타일이 세로로 놓여 있을 경우는 앞에 -
를 붙여 음수로 출력한다.
격자판을 채울 수 없는 경우는 첫 줄에 NO
를 출력한다.
4 4
YES -1 3 3 -3 -4 2 2 -2
위 예제의 출력은 다음과 같은 배치를 나타낸다.
2 3
NO
University > 서울대학교 > 2020 서울대학교 프로그래밍 경시대회 > Division 1 F번
University > 서울대학교 > 2020 서울대학교 프로그래밍 경시대회 > Division 2 H번