KOI 본선 2011 고2- 비밀번호 > 문제은행 : 정보올림피아드&알고리즘



2468 : 비밀번호

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
440 회   
시도횟수
1723 회   

문제

KOI 보안회사에서는 자동으로 비밀번호를 만드는 시스템을 연구하고 있다. 주어진 하나의 양의 정수에 대하여 다음의 원칙에 따라 두 수를 만들어 비밀번호를 정하려고 한다.

 

하나의 주어진 양의 정수 A에 대하여 비밀번호를 위한 두 수를 만드는 방법은 다음과 같다.
 
1. A의 이진수 표현에서 나오는 1의 개수 x를 찾는다.
2. A보다 작은수 중에서 그 수의 이진수 표현에서 1의 개수가 x와 같고 A에 가장 가까운 수를 하나 찾는다.
3. A보다 큰수 중에서 그 수의 이진수 표현에서 1의 개수가 x와 같고 A에 가장 가까운 수를 하나 찾는다.
 
예를 들어, 주어진 수 A가 43이면, 이 수의 이진수 표현은 101011(2)이다. 이 이진수는 1의 개수가 4이다. 그러므로 43보다 작고 43에 가장 가까우며 이진수 표현에서 1의 개수가 4인 수는 39=100111(2)이다. 또한 43보다 크고 43에 가장 가까우며 이진수 표현에서 1의 개수가 4인 수는 45=101101(2)이다.
 
이 두 수를 찾아 출력하는 프로그램을 작성하시오.
 
<제약조건>
• 전체 테스트 데이터의 30%는 1≤A≤104
• 전체 테스트 데이터의 60%는 1≤A≤108

입력형식

입력의 첫 번째 줄에는 하나의 양의 정수 가 주어진다. 단 1≤A≤1018이다.

출력형식

주어진 수 보다 작은 수 중에서 이진수의 1의 개수가 같으며 가장 가까운 수와, 주어진 수 보다 큰 수 중에서 이진수의 1의 개수가 같으며 가장 가까운 수를 한 줄에 빈칸을 사이에 두고 출력한다.

만약 그러한 수가 존재하지 않으면 그 수에 대해서는 0을 출력한다.


입력 예

43

출력 예

39 45

입력 예

7

출력 예

0 11


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP