사루만의 탑 레벨업

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

요약
N이 10^16 이하로 주어질 때, 1부터 N까지의 정수 중 이진수 표현에서 1의 개수가 3의 배수인 수의 개수를 구한다.
난이도

어려움10점 중 8점

유형
동적 계획법, 비트 연산, 수학, 조합론
정답자
아직 제출이 없습니다

문제

사루만의 오크 군대와 그 밖의 어둠의 부하들은 그의 거대한 탑 주변 땅에서 NN일 동안 매일 석탄을 캐고 목재를 벤다. ii번째 날마다 사루만은 자원을 채굴과 벌목에 쓰거나, 탑의 레벨(즉 높이)을 올리는 데 쓴다. 그는 ii의 이진 표현에 들어 있는 1의 개수가 정확히 3의 배수인 날에만 탑의 레벨을 1만큼 올린다. 0일째의 탑의 초기 레벨은 0이다.

예를 들어 사루만은 7일째(이진수 111)에 탑의 레벨을 올리고, 그 다음 11일째(이진수 1011), 이어서 13일째, 14일째, 19일째 등에 레벨을 올린다.

사루만은 NN일이 지난 뒤 탑의 레벨을 예측하고 싶어 한다. 이를 도와줄 프로그램을 작성하라.

입력

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 한 줄에 하나씩 주어진다. 각 테스트 케이스는 위에서 설명한 양의 정수 NN (N<1016N < 10^{16}) 하나로 이루어진다. 입력은 파일의 끝(EOF)에서 종료된다.

출력

각 테스트 케이스마다 한 줄에 Day N: Level = L 형식으로 출력한다. 여기서 NN은 입력으로 주어진 값이고, LL은 NN일이 지난 뒤 탑의 레벨이다.

예제2

  1. 예제 1

    입력
    2
    19
    64
    
    예상 출력
    Day 2: Level = 0
    Day 19: Level = 5
    Day 64: Level = 21
    
  2. 예제 2

    입력
    1
    7
    11
    13
    14
    
    예상 출력
    Day 1: Level = 0
    Day 7: Level = 1
    Day 11: Level = 2
    Day 13: Level = 3
    Day 14: Level = 4