집으로 돌아가기
면접 대비시간 제한2초메모리 제한1024 MB
각 버튼은 현재 우주 번호와 OR 연산을 합니다. A에서 B로 가는 100회 이하의 버튼 누름 순서를 찾고, 불가능하면 -1을 출력합니다.
문제
콜라이더가 폭발한 뒤 스파이더맨 마일스 모랄레스는 평행 우주로 떨어졌다. 상황을 살펴보고 도움이 필요하다는 것을 깨달은 마일스는 곧바로 이 우주의 스파이더맨인 피터 파커를 찾아가 자신의 이야기를 들려주었다. 마일스가 실수로 가져온 콜라이더 설계도와 여러 변수를 분석한 두 사람은 마일스가 지금 우주 번호 에 있고, 그의 우주 번호는 라는 사실을 알아냈다. 몇 달 동안 작업한 끝에 두 사람은 마일스를 집으로 돌려보낼 수 있는 우주 간 이동 장치를 만들었다. 이 장치에는 이라는 수가 적힌 개의 버튼이 있다. 버튼 를 누르면 현재 우주 번호 에서 우주 번호 로 이동한다 (는 비트 단위 OR 연산). 다만 자원이 부족해서 장치의 전력은 100번의 이동만큼만 남아 있다. 마일스와 피터는 마일스를 집으로 보내려면 버튼을 어떤 순서로 눌러야 하는지 고민하고 있다. 두 사람을 도와 달라.
입력
첫 줄에 세 정수 , , 가 주어진다. 은 버튼의 개수, 는 마일스가 지금 있는 우주의 번호, 는 마일스가 돌아가야 할 우주의 번호이다 (, ). 둘째 줄에는 버튼에 적힌 수 이 주어진다 ().
출력
마일스를 집으로 돌려보낼 수 없으면 을 한 줄에 출력한다. 돌려보낼 수 있으면 첫 줄에 버튼을 누르는 횟수 ()를 출력하고, 둘째 줄에 눌러야 할 버튼 번호를 누르는 순서대로 공백으로 구분해 출력한다. 답이 여러 개이면 아무거나 출력해도 된다.
힌트
첫 번째 예제에서는 먼저 1번 버튼을 눌러 우주 2에서 인 우주 3으로 이동한다. 그다음 4번 버튼을 눌러 우주 3에서 인 우주 11로 이동한다.