[알고연] (4주차-2) 768B. Code For 1

768B. Code For 1

Jon fought bravely to rescue the wildlings who were attacked by the white-walkers at Hardhome. On his arrival, Sam tells him that he wants to go to Oldtown to train at the Citadel to become a maester, so he can return and take the deceased Aemon's place as maester of Castle Black. Jon agrees to Sam's proposal and Sam sets off his journey to the Citadel. However becoming a trainee at the Citadel is not a cakewalk and hence the maesters at the Citadel gave Sam a problem to test his eligibility.

Initially Sam has a list with a single element n. Then he has to perform certain operations on this list. In each operation Sam must remove any element x, such that x > 1, from the list and insert at the same position $\left \lfloor \frac{x}{2}\right \rfloor,\ x\mod 2,\ \left \lfloor \frac{x}{2}\right \rfloor$  sequentially. He must continue with these operations until all the elements in the list are either 0 or 1.

Now the masters want the total number of 1s in the range l to r (1-indexed). Sam wants to become a maester but unfortunately he cannot solve this problem. Can you help Sam to pass the eligibility test?

Input: The first line contains three integers n, l, r (0 ≤ n < $2^{50}$, 0 ≤ r - l ≤ $10^5$, r ≥ 1, l ≥ 1) – initial element and the range l to r. It is guaranteed that r is not greater than the length of the final list.

입력된 숫자가 홀수인지 짝수인지에 따라 가운데를 0 또는 1로 두고 좌우에 각각 2로 나눈 값을 분배하는 과정을 반복하는 문제이다. 이 문제는 케이스를 잘 분류하고, 입력 값에 따른 시간초과 여부를 잘 확인해서 풀어야 한다. 

1. sovle(n, l, r)은 입력값이 n이고, 구간이 [l, r] 일 때의 답을 구하는 함수이다. 최종적으로 구해야 하는 답도 solve(n, l, r)이다.
2. length는 n이 쪼개질 때 구간의 최대 길이를 나타낸다. 따라서 [l, r] 이 [1, length] 이면 모든 구간이 1임을 나타내므로 n을 바로 리턴한다.
3. mid는 최대 길이의 절반을 나타낸다. 
4. l이 mid보다 클 경우 n을 2로 나누고 구간 [l-mid, r-mid] 에서 solve를 호출한다. 즉, 오른쪽 절반만 재귀호출하는 작업이다.
5. r이 mid보다 작을 경우, n을 2로 나누고 구간 [l, r] 에서 solve를 호출한다. 즉, 왼쪽 절반만 재귀호출하는 작업이다.
6. l과 r이 mid와 같을 경우, 가운데 숫자만 존재한다는 뜻이므로 홀짝 여부에 따라 1 또는 0을 리턴한다.
7. l이 mid와 같고 r은 mid와 다를 경우, n을 2로 나누고 구간 [1, r-mid] 에서 solve를 호출하고 홀짝 여부에 따라 1 또는 0을 더한다. (이 부분은 이해를 잘 못했다..)
8. r이 mid와 같고 l은 mid와 다를 경우, n을 2로 나누고 구간 [l, r] 에서 solve를 호출하고 홀짝 여부에 따라 1 또는 0을 더한다.
9. l과 r 사이에 mid가 껴있는 경우 (가장 일반적인 경우): 왼쪽 절반과 오른쪽 절반에서의 답을 각각 구하고 홀짝 여부에 따라 1 또는 0을 더한다. (분할 정복)

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
long long solve(long long n, long long l, long long r) {
    long long nn, mid, length;
    nn = n / 2; length = 1;
    while (nn > 0) {
        length = length * 2 + 1;
        nn /= 2;
    }
    if (l == 1 && r == length) return n;
    
    mid = (length + 1) / 2;
    
    // Cases..
    if (l > mid) return solve(n / 2, l - mid, r - mid);
    if (r < mid) return solve(n / 2, l, r);
 
    if (l == mid && r == mid) return n % 2;
 
    if (l == mid) return solve(n / 2, 1, r - mid) + n % 2;
    if (r == mid) return solve(n / 2, l, r) + n % 2;
 
    return solve(n / 2, l, mid - 1) + solve(n / 2, 1, r - mid) + n % 2;
}
 
int main() {
    cin.tie(NULL);	cout.tie(NULL);	std::ios::sync_with_stdio(false);
    long long n, l, r; cin >> n >> l >> r;
    cout << solve(n, l, r) << "\n";
    return 0;
}