0817 upside down cake problem
ph
문제 : [1]
풀이 : [2]
- 문제설명 일러스트도 좋고 (적당한?) 해설도 있다.
핵심은, ① 케이크를 잘라서 flip한 뒤 다시 꼽으면 조각의 순서가 바뀐다는 것, ② angle 크기 \(x\)로 케이크를 잘라나가다 보면 정확히 \(2\pi\)의 배수가 아닌 한 어느정도 남게 되어 있는데 이를 \(b\)라 하고, \(x=a+b\)로 놓으면, \( xk = (a+b)k = 2\pi + b\). 즉, \(ka + (k-1)b = 2\pi\) 이므로 케이크 하나(\(=2\pi\))는 \(a\)크기의 조각 \(k\)개와 \(b\)크기의 조각 \(k-1\)개로 이루어진다는 것, ③ 따라서 어떻게 잘라 나가도 인접한 \(a\)두개가 존재한다는 것.
def cakeflip(x):
# invert and reverse
x = np.array(x)
if x[0]+x[1] != 1: # [1,0], [0,1] are isomorphic
tmp = (x[1]+1)%2
x[1] = (x[0]+1)%2
x[0] = tmp
return np.append(x[2:],x[0:2])
import numpy as np
for a in range(2,4):
print '-'*40
arr = np.zeros(a+a-1, dtype=np.uint8)
#first filp
arr[-2:] = 1
cnt=1
while np.any(arr):
print cnt, "\t", arr
arr = cakeflip(arr)
cnt += 1
print cnt, "\t", arr
assert ((a*2-1)**2 - 1 )/2 == cnt
# cnt = 2*n*(n-1) = (len(arr)^2 - 1) / 2
# https://oeis.org/A046092
# why? can you prove?
def simple_cakeflip(arr):
return (len(arr)**2 - 1 )/2
def cakeflip2(x, idx=0):
lx = len(x)
assert lx>1
idx0 = idx % lx
idx1 = (idx+1) % lx
if x[idx0] + x[idx1] == 1: #[0,1] or [1,0] are stable.
return x
x0 = (x[idx1]+1)%2
x[idx1] = (x[idx0]+1)%2
x[idx0] = x0
return x
for a in range(2,4):
print '-'*40
arr = np.zeros(a+a-1, dtype=np.uint8)
idx = 0
cnt = 0
while cnt < 1 or np.any(arr):
print cnt,"\t",arr
arr = cakeflip2(arr, idx)
idx += 2
cnt += 1
print cnt,"\t",arr
assert cnt == simple_cakeflip(arr)
---------------------------------------- 0 [0 0 0] 1 [1 1 0] 2 [1 1 0] 3 [1 1 0] 4 [0 0 0] ---------------------------------------- 0 [0 0 0 0 0] 1 [1 1 0 0 0] 2 [1 1 1 1 0] 3 [1 1 1 1 0] 4 [1 0 0 1 0] 5 [1 0 0 1 0] 6 [1 0 0 1 0] 7 [1 0 0 1 0] 8 [1 0 0 1 0] 9 [1 1 1 1 0] 10 [1 1 1 1 0] 11 [0 0 1 1 0] 12 [0 0 0 0 0] ---------------------------------------- 0 [0 0 0 0 0 0 0] 1 [1 1 0 0 0 0 0] 2 [1 1 1 1 0 0 0] 3 [1 1 1 1 1 1 0] 4 [1 1 1 1 1 1 0] 5 [1 0 0 1 1 1 0] 6 [1 0 0 0 0 1 0] 7 [1 0 0 0 0 1 0] 8 [1 0 0 0 0 1 0] 9 [1 0 1 1 0 1 0] 10 [1 0 1 1 0 1 0] 11 [1 0 1 1 0 1 0] 12 [1 0 1 1 0 1 0] 13 [1 0 1 1 0 1 0] 14 [1 0 1 1 0 1 0] 15 [1 0 1 1 0 1 0] 16 [1 0 0 0 0 1 0] 17 [1 0 0 0 0 1 0] 18 [1 0 0 0 0 1 0] 19 [1 1 1 0 0 1 0] 20 [1 1 1 1 1 1 0] 21 [1 1 1 1 1 1 0] 22 [0 0 1 1 1 1 0] 23 [0 0 0 0 1 1 0] 24 [0 0 0 0 0 0 0]
대충 규칙을 알아내는 것은 어렵지 않다. 홀수개의 조각만으로 나뉘는데 차례로 두개씩 뒤집으면 언젠가 제자리로 돌아올 것이라는 것도 대강 이해할 수 있다. 그런데 왜 모든 permutation이 아니고 A046092인지 예제출력을 좀 봐도 쉽게 증명을 못하겠다.
아 물론 projecteuler에 나온 최초의 문제도 아직 미해결상태고. #cont