More actions
imported>Unknown No edit summary |
(Table transclusion repair v1) |
||
| Line 4: | Line 4: | ||
| 2006-01-11 Accepted 0.688 14280 | | 2006-01-11 Accepted 0.688 14280 | ||
|} | |} | ||
0.5a(a + 1) ≤ n, (a ≥ 0 이고, 수식을 만족하는 가장 큰 정수) | |||
그렇다면 입력 n 에 대하여 다음과 같은 식이 완성된다. a를 n에 대하여 바꿀 순 없을까? | 그렇다면 입력 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 를 찾는 것이 아니라 원반을 옮기는 총 횟수를 구하는 것이었다. | p.s. 처음에는 k 개의 원반을 찾으려고 노력했으나, 실마리는 k 에 있지 않았다. 우리가 원하는 것은 k 를 찾는 것이 아니라 원반을 옮기는 총 횟수를 구하는 것이었다. | ||
Latest revision as of 12:46, 27 March 2026
소감
| 2006-01-11 Accepted 0.688 14280 |
0.5a(a + 1) ≤ n, (a ≥ 0 이고, 수식을 만족하는 가장 큰 정수)
그렇다면 입력 n 에 대하여 다음과 같은 식이 완성된다. a를 n에 대하여 바꿀 순 없을까?
T(n) = 2a(a - 1) + 1 + 2a{n - 0.5 a ( a + 1 ) }
p.s. 처음에는 k 개의 원반을 찾으려고 노력했으나, 실마리는 k 에 있지 않았다. 우리가 원하는 것은 k 를 찾는 것이 아니라 원반을 옮기는 총 횟수를 구하는 것이었다.
코드
// 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;
}