얕은 스택은 상한을 다 쓴다
12편은 두 가지를 남겼다. 커널 축의 기울기 2.25 가 식인지 (커널 값이 셋뿐이라
법칙으로 안 내놨다), 그리고 천장이 어디서부터 무는지.
둘 다 잴 수 있다. 커널 7 과 11 을 넣으면 앞이 갈리고, 층을 둘셋으로 줄이면
뒤가 갈린다.
재기 전에 예측을 넷 적었다.
구성 상한 내 예측 근거
k5 x2 8 8 상한이 천장 12 아래니 상한을 다 쓴다
k5 x3 12 12 마찬가지, 상한이 천장과 같다
k7 x4 24 16 2.25 x 7 = 15.75
k11 x4 40 25 2.25 x 11 = 24.75얕은 쪽과 넓은 쪽
같은 예산 637k 다.
구성 커널 층 채널 파라미터 상한
k3 x2 3 2 303 635,565 4
k3 x3 3 3 250 635,400 6
k3 x4 3 4 218 636,162 8
k5 x2 5 2 238 635,746 8
k5 x3 5 3 196 636,180 12
k7 x4 7 4 145 636,835 24
k11 x4 11 4 116 633,152 40과제와 규약은 12편과 같다. 복사 거리를 바꿔 가며 끊기는 자리를 찾고, 판정은
시드 둘 다 2.0 아래여야 푼 것으로 한다. 상한이 작은 구성은 이분 탐색보다
한 자씩 올리는 게 싸서 그렇게 했다.
결과
12편 것까지 합쳐 열셋이다.
구성 커널 층 상한 실제 상한 대비
k3 x2 3 2 4 4 1.00
k3 x3 3 3 6 6 1.00
k3 x4 3 4 8 6 0.75
k3 x8 3 8 16 7 0.44
k3 x12 3 12 24 8 0.33
k5 x2 5 2 8 8 1.00
k5 x3 5 3 12 11 0.92
k5 x4 5 4 16 12 0.75
k5 x6 5 6 24 12 0.50
k5 x8 5 8 32 12 0.38
k7 x4 7 4 24 17 0.71
k9 x4 9 4 32 21 0.66
k11 x4 11 4 40 25 0.62얕으면 상한이 전부다
k3 x2 는 상한 4 에 4 를, k3 x3 은 상한 6 에 6 을, k5 x2 는 상한
8 에 8 을 쓴다. 한 자도 안 남는다.
12편은 “상한을 늘려도 쓸 수 있는 거리는 안 는다” 로 끝났는데, 그건 상한 16 부터
잰 것이다. 그 아래에서는 상한이 곧 답이다.
k5 x3 만 상한 12 에 11 로 한 자 남는다. 상한이 천장과 같은 자리라 어느
쪽에 걸린 건지 이 하나로는 안 갈린다.
팔꿈치
커널마다 줄로 세우면 모양이 하나다.
커널 5 층 2 3 4 6 8
상한 8 12 16 24 32
실제 8 11 12 12 12
커널 3 층 2 3 4 8 12
상한 4 6 8 16 24
실제 4 6 6 7 8상한을 따라 올라가다 눕는다. 커널 5 는 12 에서 눕고 4층이면 이미 다 왔다.
4층과 8층이 같은 것을 준다. 커널 3 은 6 근처에서 눕는데 완전히 평평하진
않아서 층 넷에서 열둘까지 가며 6, 7, 8 로 두 자 는다.
커널 7 과 11
k7 x4 가 17, k11 x4 가 25 다. 12편의 직선 2.25k + 0.75 는 16.5 와
25.5 를 준다. 정수 측정이니 둘 다 한 자 안이다.
k11 은 외삽이었다. 12편은 커널 3, 5, 9 만 갖고 있었고 11 은 그 밖이다.
밖에서도 한 자 안으로 맞았다.
내가 본문에 적어 둔 예측은 16 과 25 였는데, 2.25k 만 쓰고 절편 0.75 를
빠뜨린 값이다. 직선은 16.5 를 주고 실측은 17 이다. 직선이 맞고 내 산수가
틀렸다.
12편 직선을 고친다
그런데 층을 4 로 맞춰 놓고 다시 보면 어긋나는 데가 있다.
커널 (전부 4층) 실제 12편 직선
3 6 7.50
5 12 12.00
7 17 16.50
9 21 21.00
11 25 25.50커널 3 에서 1.5 자 어긋난다. 나머지 넷은 반 자 안이다.
이유는 12편이 커널 3 의 값으로 7 과 8 을 썼기 때문이다. 그 둘은 8층과
12층 짜리다. 커널 5 쪽은 12 를 4층·6층·8층에서 다 얻었으니 깊이를 안 타는데,
커널 3 은 깊이를 타므로 깊은 값을 커널 축에 올리면 위로 뜬다.
층을 맞춘 커널 3 은 6 이다. 12편 그림의 아래 패널은 깊이가 섞인 점들을 커널
축에 놓은 것이었다. 기울기 2.25 자체는 커널 5 이상에서 살아 있지만, 커널
3 을 그 직선에 올린 것은 잘못이다.
예측 성적
구성 내 예측 실제 결과
k3 x2 4 4 맞음
k3 x3 6 6 맞음
k5 x2 8 8 맞음
k5 x3 12 11 한 자
k11 x4 25 25 맞음
k7 x4 16 17 한 자 (절편 빠뜨림)
k3 x4 7~8 6 두 자얕은 쪽 “상한을 다 쓴다” 는 셋 다 맞았다. 틀린 셋은 전부 천장 근처다 - 천장이 정확히 어디인지는 아직 한 자 안으로 못 짚는다.
설계할 때
11편과 12편이 준 것에 하나가 더 붙는다.
- 잡아야 하는 거리가 작으면 수용장 공식대로 쌓으면 된다. 상한
4,6,8짜리는 상한만큼 한다 - 거리가 그 커널의 천장을 넘으면 층을 더 쌓아도 안 된다. 커널 5 는 4층에서
12고 8층에서도12다 - 넘기려면 커널을 키워야 한다. 커널
5→12,7→17,9→21,11→25다. 같은 예산이면 채널이171에서116으로 깎인다
남는 것
k5 x3 이 상한 12 에 11 인 것을 못 갈랐다. 상한 12 를 층으로 만드는
다른 방법이 없어서 (커널 5 에 3층뿐) 이 하나로는 상한 탓인지 천장 탓인지 모른다.
커널 3 의 천장을 못 봤다. 4, 8, 12 층에서 6, 7, 8 이라 아직 오르는
중이다. 층을 20, 30 으로 늘리면 어디서 멈추는지 볼 수 있는데, 예산 고정이라
채널이 계속 깎이므로 그때는 채널이 원인이 될 수 있다.
시드는 여전히 2개다. 경계에서 갈린 자리가 이제 열셋 중 셋이다 - k5 x8 의
13, k9 x4 의 22, k11 x4 의 26 (0.0041 과 3.0002).
한 과제다. 11편과 12편의 단서가 그대로 붙어 있다.
그래서
- 층을
2,3으로 줄인 구성과 커널7,11짜리를 같은 예산637k로 재서 12편 표를 열셋으로 늘렸다 - 얕으면 상한을 다 쓴다.
k3 x2는4/4,k3 x3은6/6,k5 x2는8/8이다. 12편의 “상한은 값을 못 한다” 는 상한16이상에서 잰 것이다 - 커널 5 는 상한을 따라
8,11,12로 오르다12에서 눕는다. 4층이면 이미 다 왔고 8층도 같다 - 커널 3 은
4,6,6,7,8로 눕는 속도가 느리다. 층 넷에서 열둘까지 가며 두 자 는다 k7 x417,k11 x425. 12편 직선은16.5와25.5를 주니 둘 다 한 자 안이고,11은 외삽이었다- 12편 직선의 커널 3 점을 고친다. 12편은 8층·12층 값
7·8을 커널 축에 올렸는데, 층을4로 맞추면6이라 직선보다1.5자 아래다 - 내 예측 일곱 중 넷이 맞고 둘이 한 자, 하나가 두 자 틀렸다. 틀린 것은 전부 천장 근처다
Comments