1094번

수정 전

시간 제한 메모리 제한
2 초 128 MB

문제

지민이는 64cm 길이의 막대기를 가지고 있다. 갑자기 지민이는 Xcm 길이의 막대기가 가지고 싶어졌다. 지민 이는 원래 막대기를 몇 개의 작은 막대기로 쪼갠 후에, 막대기를 합쳐서 Xcm를 만들기로 했다.

지민이는 다음과 같이 막대기를 쪼갠다.

1. 모든 막대기의 길이를 더한다. (처음엔 64 하나다) 만약 이것이 X보다 크다면, 다음과 같이 한다.

(1) 가장 짧은 길이의 막대기를 골라서 반으로 쪼갠다.

(2) 위에서 쪼갠 것의 반을 제외한 막대기의 길이의 합이, X보다 작아지지 않는다면, 그 반을 버린다.

2. 마지막으로, 남은 막대기를 붙여서 Xcm를 만든다.

지민이가 위와 같이 막대기를 쪼갰을 때, 마지막에 몇 개의 막대기를 풀로 붙어야 하는지 구하는 프로그램을 작성하시오.
 

입력

첫째 줄에 X가 주어진다. X는 64보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 불가능 할 때는 -1을 출력한다.

예제 입력

23

예제 출력

4

힌트

수정 후

시간 제한 메모리 제한
2 초 128 MB

문제

지민이는 길이가 64cm인 막대를 가지고 있다. 어느날 갑자기 지민이는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 막대를 몇 개의 작은 막대로 자른다음, 합쳐서 Xcm를 만드려고 한다.

지민이가 막대를 자르는 방법은 다음과 같다.

  1. 모든 막대의 길이를 더한다. (처음에는 64cm이다) 이 값이 X보다 크다면, 아래와 같이 한다.
    1. 길이가 가장 짧은 막대를 골라서 반으로 자른다.
    2. 위에서 자른 막대 중 하나와 나머지 막대 길이의 합이 X보다 작지 않다면, 자른 막대 중 하나를 버린다.
  2. 남은 막대를 붙여서 Xcm를 만든다.

 

지민이가 위와 같이 막대를 잘랐을 때, Xcm를 이루는 막대의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X가 주어진다. X는 64보다 작거나 같은 자연수이다.

출력

문제에서 주어진 과정대로 막대를 잘랐을 때, Xcm를 이루는 막대의 개수를 출력한다. 만약, Xcm를 만들 수 없다면 -1을 출력한다.

예제 입력

23

예제 출력

4

힌트