[C/C++] Codeforce 768B - Code For 1

B. Code For 1

time limit per test2 seconds

memory limit per test256 megabytes

inputstandard input

outputstandard output

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 , , 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 < 250, 0 ≤ r - l ≤ 105, 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.

 

Output

Output the total number of 1s in the range l to r in the final sequence.

 

 

<처음에 썻던 코드>

#include<stdio.h>

int arr[100001];
int i = 0;

void DC(int x)
{
	if (x == 1)
	{
		arr[i] = 1;
		i++;
	}
	else
	{
		if (x % 2 == 1)
		{
			x -= 1;
			DC(x / 2);
			arr[i] = 1;
			i++;
			DC(x / 2);
		}
		else
		{
			DC(x / 2);
			arr[i] = 0;
			i++;
			DC(x / 2);
		}
	}

}

int main(void)
{
	int n, l, r, sum = 0;
	scanf("%d %d %d", &n, &l, &r);

	DC(n);

	for (int j = l - 1; j < r; j++)
	{
		sum += arr[j];
	}
	printf("%d", sum);
}

내가 짠 코드를 살펴보면 만약 입력이 [10 3 10] 이라면 (101110101011101) 이므로 1~15까지의 값들을 모두 배열에 저장하여 l 부터 r 까지의 부분을 합계하여 출력하는 방식이다. n이 작은수이면 연산시간에 큰 차이를 못느끼겠지만 n의 최대값은 2^50 이다. 즉, 1.1259 X 10^15 인데 대략 1000조 정도 되는 값이다. 최악의 경우 길이 1000조 짜리 배열을 저장해야하는데 이는 말도안되는 일이다. 그리하여 24시간동안 다른 할일못하고 이 문제 풀려고 해당 범위만 조사를 하도록 코드를 구현해보려 했으나 마땅한 대안이 떠오르지 않았다. 결국 구글링을 하여서 좋은 아이디어를 얻을 수 있었다.

 

<다른 사람의 정답> - 참고블로그 https://cloud.tencent.com/developer/article/1086462

#include <stdio.h>

typedef long long ll;
ll n, l, r, s = 1, ans;
void solve(ll a, ll b, ll l, ll r, ll d) // a = 시작범위, b = 끝 범위, d = 나뉘는 수
{
	if (a > b || l > r) return; 
	else
	{
		ll mid = (a + b) / 2;
		if (r < mid) solve(a, mid - 1, l, r, d / 2);
		else if (mid < l) solve(mid + 1, b, l, r, d / 2);
		else {
			ans += d % 2;
			solve(a, mid - 1, l, mid - 1, d / 2);
			solve(mid + 1, b, mid + 1, r, d / 2);
		}
	}
}
int main()
{
	scanf("%lld %lld %ld", &n, &l, &r);
	long long p = n;
	while (p >= 2) // s = 길이
	{
		p /= 2;
		s = s * 2 + 1;
	}
	solve(1, s, l, r, n);
	printf("%d\n", ans);
	return 0;
}

기본적인 아이디어를 보자면 범위가 l 부터 r 까지 합을 구하는데

mid 값(여기에서 mid는 범위의 길이, ex : 만약 입력값이 10이라면 101110101011101 이므로 길이가 15이다.) 기준으로

1. l이 mid보다 크다면 다시 mid+1 부터 b 까지의 범위로 재귀를 하고

2. r이 mid보다 작을 경우 a 부터 mid - 1 까지의 범위를 재귀한다.

3. 1, 2번의 경우가 아니라면 중간 값(mid값 X)은 항상 범위 내에 있다는 말이므로  중간 값이 홀수면 +1, 짝수면 +0

 

그렇다면 해당 범위만 조사하고 r - l 의 최대값이 10만이므로 무리없이 연산이 가능하다.