The Priest Mathematician/문보창

소감 ¶

2006-01-11 Accepted 0.688 14280

{{| 0.5a(a + 1) ≤ n, (a ≥ 0 이고, 수식을 만족하는 가장 큰 정수) |}}
그렇다면 입력 n 에 대하여 다음과 같은 식이 완성된다. a를 n에 대하여 바꿀 순 없을까?
{{| T(n) = 2<sup>a</sup>(a - 1) + 1 + 2<sup>a</sup>{n - 0.5 a ( a + 1 ) } |}}

p.s. 처음에는 k 개의 원반을 찾으려고 노력했으나, 실마리는 k 에 있지 않았다. 우리가 원하는 것은 k 를 찾는 것이 아니라 원반을 옮기는 총 횟수를 구하는 것이었다.

코드 ¶

~cpp
// 10254 - The Priest Mathematician
#include "BigInteger.h"
using namespace BigMath;

int findK(int n)
{
	int i;
	for (i = 0; ; i++)
		if (0.5 * i * (i + 1) > n)
			break;
	return i - 1;
}

void process(int n)
{
	if (n == 0)
	{
		cout << 0 << endl;
		return;
	}
	int k, temp;
	BigInteger result, kpow2(2);
	k = findK(n);
	temp = n - 0.5 * k * (k + 1);
	kpow2 = kpow2.Power(k);
	result = kpow2 * (k - 1) + 1 + temp * kpow2;
	cout << result << endl;
}

int main()
{
	int n;
	while (cin >> n)
		process(n);
	return 0;
}

----
ThePriestMathematician