32151번 - 비밀번호 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 72 | 12 | 9 | 40.909% |
문제
우람이는 $1$과 $M$ 사이의 수 $N$개로 이루어진 비밀번호를 가지고 있다. 해당 비밀번호를 기억하기 쉽게 하기 위해 각 수를 2진법으로 나타냈을때 1의 개수를 적어두었다. 그 이후 우람이는 비밀번호를 잊어버렸다.
우람이는 비밀번호의 이웃한 수의 차이가 1인 수를 쓰는 것을 좋아한다. 각 수를 이진법으로 나타냈을 때 1의 개수가 주어졌을 때 이웃한 수 중에 차이가 1인 수의 쌍이 가장 많은 비밀번호 수열을 찾아서 우람이를 도와주자. 단, 개수가 같을 경우 사전순으로 가장 작은 수열을 출력한다.
입력
첫째 줄에 $N$과 $M$이 주어진다.
둘째 줄에 우람이의 비밀번호의 각 수를 2진법으로 나타냈을 때 1의 개수를 나타내는 길이 $N$의 수열 $a_1, \cdots, a_N$이 공백을 사이에 두고 주어진다.
출력
첫번째 줄에 가능한 차이가 1인 이웃한 수의 쌍의 개수의 최대값을 출력한다.
두번째 줄에 문제의 조건을 만족하면서 차이가 1인 이웃한 수의 쌍의 개수가 가장 많은 수열을 출력한다. 개수가 같은 수열이 여럿 있는 경우, 사전순으로 가장 작은 수열을 출력한다.
가능한 수열이 없을 경우 -1을 출력한다.
제한
- $2 \leq N \leq 2000$
- $3 \leq M \leq 1023$
- $1 \leq a_i \leq 10$
서브태스크 1 (20점)
$N \leq 7$, $M \leq 7$, $a_i \leq 3$
서브태스크 2 (80점)
추가 제한 조건이 없다.
예제 입력 1
5 7 1 3 2 2 3
예제 출력 1
2 1 7 5 6 7
예제 입력 2
7 7 1 1 2 1 2 2 3
예제 출력 2
6 1 2 3 4 5 6 7
예제 입력 3
3 3 3 3 3
예제 출력 3
-1
힌트
수열 $a_1, ..., a_n$과 수열 $b_1, ... b_n$에 대해 앞의 수열이 더 사전순으로 작다는 것은 다음과 같다.
어떤 $i$가 존재해서 모든 $j<i$에 대해 $a_j = b_j$이고 $a_i < b_i$이다.
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호