KOI 1차 2021 초1- 지우개 > 문제은행 : 정보올림피아드&알고리즘


4724 : 지우개

제한시간
1000 ms   
메모리제한
512 MB   
해결횟수
94 회   
시도횟수
156 회   

문제

N개의 칸에 1부터 N까지의 수들이 왼쪽부터 순서대로 저장되어 있다.

또, 각 칸은 왼쪽부터 1부터 N까지 순서대로 번호가 붙어 있다.

즉, 처음에는 각 칸의 번호와 각 칸에 저장된 수가 같다.

 

아래 그림은 N = 7일 때의 예이다.

 


 

다음 작업을 수가 정확히 하나가 남을 때 까지 반복한다.

(A) 홀수번 칸의 수들을 모두 지운다.

(B) 남은 수들을 왼쪽으로 모은다.

제일 첫 작업의 (A) 단계가 끝나면 칸들의 상태는 다음과 같을 것이다.

 

 

(B)단계가 끝나면 다음과 같을 것이다.

  

 

두 번째 작업이 진행되면 칸들은 아개 두 그림과 같이 바뀔 것이다.


 

이제 수가 하나 남았으므로 작업은 더 이상 진행되지 않는다.

N을 입력으로 받아 위와 같이 작업을 진행했을 때 마지막으로 남는 수를 계산하는 프로그램을 작성하라.

 

[제약조건]

* 1 ≤ N ≤ 100

 

[부분문제]

1. (5점) 입출력 예제만이 주어짐.

2. (15점) N ≤​ 8

3. (30점) N은 1, 2, 4, 8, 16, 32, 64 중 하나이다. 즉, N은 1이거나, 2이거나, 2를 여러번 곱한 수 중 하나이다.

4. (50점) 추가 제약 조건 없음

 

 


입력형식

첫 번재 줄에 정수 N이 주어진다.


출력형식

마지막으로 남는 수를 한 줄에 출력한다.


입력 예

1

출력 예

1

입력 예

2

출력 예

2

입력 예

7

출력 예

4

데이타 만든사람 : pai2

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

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

Copyrightⓒ 2010 jungol. All right reserved.

TOP