31543번 - 짝수가 싫어 서브태스크스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 324 | 98 | 54 | 26.214% |
문제
한 변의 길이가 $N=2\,050$인 정사각형 모양의 격자판이 있다.
서진이는 이 $N^2$개의 격자들에 원하는 대로 격자 당 최대 하나의 돌을 채울 수 있다. 이때 서진이는 짝수를 싫어하기 때문에 다음과 같은 규칙으로 돌을 채우고자 한다.
어떤 양의 정수 $K$가 주어졌을 때, $K=a\times b$를 만족하는 모든 양의 정수 $a$, $b$에 대해, 격자판 내의 격자들을 골라 만들 수 있는 $a\times b$ 형태의 직사각형을 생각하자. 이렇게 고를 수 있는 모든 직사각형에 대해, 해당 직사각형의 $K$개의 격자 중 돌이 들어있는 격자의 개수를 직사각형의 값이라고 하자. 서진이는 짝수를 싫어하기 때문에 직사각형의 값이 짝수인 조건을 만족하는 직사각형이 단 하나도 존재하지 않도록 하고 싶다.
이 조건을 만족하도록 $N\times N$크기의 정사각형 판에 돌을 채워보자.
입력
첫 번째 줄에 $N$과 $K$가 공백으로 구분되어 주어진다. $(N=2\,050;$ $1\le K\le N^2)$
출력
만약 조건을 만족하도록 $N\times N$ 정사각형 모양의 격자판을 채울 수 있다면, $N$개의 줄에 걸쳐 각 격자의 상태를 나타내는 정수 $N$개를 순서대로 공백으로 구분해 출력한다. 1은 그 격자에 돌을 채우는 것을, 0은 그 격자에 돌을 채우지 않는 것을 의미한다.
만약 조건을 만족하도록 $N\times N$ 정사각형 모양의 격자판을 채울 수 없다면 격자판 대신 -1을 하나 출력한다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 16 | $K=31$ |
| 2 | 32 | $K\le 2$ |
| 3 | 32 | $K\le 4$ |
| 4 | 32 | $K\le 8$ |
| 5 | 32 | $K\le 16$ |
| 6 | 128 | $K\le 1\,024$ |
| 7 | 128 | 추가적인 제한 조건 없음 |
예제 입력 1
3 3
예제 출력 1
1 0 0 0 1 0 0 0 1
첫 번째 예제는 $n=3$이므로 실제 입력으로 주어지지 않는다. 예제 출력의 $3\times 3$ 정사각형에서 넓이가 $3$인 직사각형은 $1\times 3$, $3\times 1$ 각각 $3$개 있으며, 이 직사각형 $6$개 모두 각각 돌이 $1$개 있으므로 조건을 만족한다.
예제 입력 2
4 8
예제 출력 2
0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0
두 번째 예제는 $n=4$이므로 실제 입력으로 주어지지 않는다. 예제 출력의 $4\times 4$ 정사각형에서 넓이가 $8$인 직사각형은 $2\times 4$, $4\times 2$ 각각 $3$개 있으며, 이 직사각형 $6$개 모두 각각 돌이 $1$개 혹은 $3$개 있으므로 조건을 만족한다.
예제 입력 3
4 15
예제 출력 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
세 번째 예제는 $n=4$이므로 실제 입력으로 주어지지 않는다. 예제 출력의 $4\times 4$ 정사각형에서 넓이가 $15$인 직사각형은 존재하지 않으므로 조건을 만족한다.
출처
University > 고려대학교 > MatKor Cup > 제4회 고려대학교 MatKor Cup: 2024 Winter/Spring K번
- 문제를 만든 사람: alex04, gs25, kidw0124
- 문제를 번역한 사람: tikiliki0417
- 문제를 검수한 사람: coo001, devluyten, kevinlys00, lighter, sshs29hanul, tlsdydaud1, utilforever
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호