ABC_115_D - Christmas

[zeikar]

Problem link

https://atcoder.jp/contests/abc115/tasks/abc115_d

Problem Summary

버거를 일정 규칙으로 쌓을 수 있다.
해당 레벨의 버거의 x층 까지 중에 패티가 몇 개인지 구하는 문제.

일정 규칙:

• 레벨 0의 버거는 패티 1개이다.
• 레벨 L의 버거는 번 + 레벨 L-1 버거 + 패티 + 레벨 L-1 버거 + 번이다.

Solution

분할 정복으로 레벨 L의 버거의 패티 수를 빨리 구할 수 있다.

번 + 레벨 L-1 버거 + 패티 + 레벨 L-1 버거 + 번

중간의 패티를 기점으로 반을 나눌 수 있고,
x가 레벨 L-1 버거의 층수 + 1 보다 작으면 레벨 L-1 버거의 패티의 개수를 구하는 식으로 재귀적으로 나눠나갈 수 있다.

대신 특정 레벨의 전체 버거 층 수 및 패티의 총 개수를 빨리 구하기 위해 먼저 전처리로 전부 구해놓았다.

Source Code

#include <iostream>
using namespace std;

long long totalLength[51];
long long pattyLength[51];

void getLength(int level) {
	if (level == 0)
	{
		totalLength[level] = 1;
		pattyLength[level] = 1;
		return;
	}

	getLength(level - 1);

	totalLength[level] = totalLength[level - 1] * 2 + 3;
	pattyLength[level] = pattyLength[level - 1] * 2 + 1;
}

long long solve(int level, long long x) {
	if (level == 0)
	{
		return 1;
	}

	if (x <= 1)
	{
		return 0;
	}
	else if (x <= 1 + totalLength[level - 1])
	{
		return solve(level - 1, x - 1);
	}
	else if (x == 1 + totalLength[level - 1] + 1)
	{
		return pattyLength[level - 1] + 1;
	}
	else if (x < totalLength[level])
	{
		return pattyLength[level - 1] + 1 + solve(level - 1, x - totalLength[level - 1] - 2);
	}
	else
	{
		return pattyLength[level];
	}
}

int main() {
	int n;
	long long x;

	cin >> n >> x;

	getLength(n);

	cout << solve(n, x) << endl;
}