배열 고치기
시간 제한2초메모리 제한128 MB
배열의 각 값에 대해 주어진 범위 안에서 이진수 해밍 거리가 가장 작은 수를 찾고, 동률이면 가장 작은 값을 선택하는 문제입니다.
문제
정수 배열 A와 두 정수 low, high가 주어진다. A와 같은 길이의 배열 B를 만들어야 한다.
B의 모든 원소 X는 low <= X <= high를 만족해야 한다. 또한 각 위치 i에 대해 A[i]와 B[i]의 비트 차이가 최소가 되도록 B[i]를 골라야 한다. 이 조건을 만족하는 배열 B가 여러 개라면, 사전순으로 가장 앞서는 배열을 출력한다.
두 정수 a와 b의 비트 차이는 다음과 같이 계산한다. 두 수를 각각 이진수로 바꾸고, 길이가 다르면 더 짧은 쪽의 왼쪽에 0을 붙여 길이를 맞춘다. 그 뒤 같은 위치의 비트가 서로 다른 자리의 개수를 센다.
입력
첫째 줄에 배열 A의 크기 N과 두 정수 low, high가 주어진다.
둘째 줄에 배열 A의 원소 A_i가 공백으로 구분되어 주어진다.
출력
첫째 줄에 배열 B의 원소를 공백으로 구분하여 출력한다.
제한
- 1 <= N <= 50
- 0 <= low <= high <= 2^30 - 1
- 0 <= A_i <= 2^30 - 1