%2021. 11. 11. 16:04에 작성된 글입니다%
https://www.acmicpc.net/problem/16282
16282번: Black Chain
n개의 블랙 고리가 일렬로 연결된 체인이 있다. 블랙 고리 하나는 무게가 정확히 1g 이다. 이 고리들을 이용하여 1g 부터 ng 까지 가능한 모든 무게를 생성하려고 한다. 이를 위해 고리를 일부 풀어
www.acmicpc.net
1. 고리를 \(n\)번 분리하면 \(w=1\)인 고리가 \(n\)개 생긴다.
2. \(w=1\)인 고리 뭉탱이로 만들 수 있는 최대 무게는 \(n\)이다.
3. 따라서 \(n+1\)짜리 고리가 있어야 그보다 더 무거운 무게를 구성할 수 있다.
4. \(w=n+1\)짜리 고리와 \(w=1\)인 고리를 모두 선택하면 무게는 \(2n+1\)이다.
5. \(2n+1\) 고리 다음에는 \(2n+2\) 고리가 와야 더 무거운 무게를 구성할 수 있다.
\(4n+3\) -> \(4n+4\)
\(8n+7\) -> \(8n+8\)
.
.
.
->
고리를 n번 끊을 때 만들 수 있는 최대 무게는 처음에 들어온 고리가 \(W_n\)개일 때 \(W_n=\left(n+1\right)2^{n+1}-1\).
계산해봤는데 \(W_{100}\)이 대략 \(2.56\cdot 10^{32}\)이다.
\(10^{18}\)은 거뜬히 넘기 때문에 \(W_1\)부터 쭉 돌리면서 비교해줘도 문제없이 바로 나온다.