Tupper의 자기 지시 공식
골드 V의견: 0
1980년대에 Jeff Tupper가 발견한 자기 지시 공식(self-referential formula) 은 다음과 같다.
$$ \frac{1}{2} < \left\lfloor \mathrm{mod}\!\left( \left\lfloor \frac{y}{17} \right\rfloor \, 2^{\,-17\lfloor x \rfloor - \mathrm{mod}(\lfloor y \rfloor, 17)}, \; 2 \right) \right\rfloor $$
이 부등식을 만족하는 점 \((x, y)\) 를 평면에 찍으면 흑백 그림이 그려진다. 놀랍게도 적당한 정수 \(k\) 를 골라 \(0 \le x < W\), \(k \le y < k+17\) 인 영역만 들여다보면, 어떤 17행짜리 흑백 그림이든 그대로 나타나게 만들 수 있다.
이 영역에서 위치를 다음과 같이 읽는다. \(x = c\) (\(c = 0, 1, \dots, W-1\)) 는 왼쪽에서부터 센 열 번호이고, \(s = y - k\) (\(s = 0, 1, \dots, 16\)) 는 아래에서부터 센 높이다. 칸 \((c, s)\) 가 위 부등식을 만족하면 그 칸은 켜진 (\(1\)) 칸이다.
\(17\)행 \(W\)열짜리 그림이 주어진다. 이 그림을 정확히 재현하는 \(k\) 를 구하여라. 단, \(k\) 는 \(17\)의 배수여야 하며, 그런 \(k\) 는 유일하다.
\(1 \le W \le 106\). 그림은 항상 정확히 \(17\)개의 행으로 이루어진다. 각 칸의 값은 0 또는 1 이다.
첫째 줄에 그림의 너비 \(W\) 가 주어진다.
다음 \(17\)개의 줄에 각각 \(W\)개의 문자 0 또는 1 이 공백 없이 주어진다. 이 줄들은 그림을 위쪽 행부터 아래쪽 행 순서로 나타낸다. 즉 첫 번째 줄이 맨 윗줄(\(s = 16\)), 마지막(\(17\)번째) 줄이 맨 아랫줄(\(s = 0\))이다. 1 은 켜진 칸을 뜻한다.
주어진 그림을 재현하는, \(17\)의 배수인 음이 아닌 정수 \(k\) 를 한 줄에 출력한다. 이 값은 매우 커질 수 있다.
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
17
유일하게 켜진 칸은 열 \(c=0\), 높이 \(s=0\) 이므로 \(N = 2^{17\cdot 0 + 0} = 1\), 따라서 \(k = 17N = 17\) 이다.
2
00
00
00
00
00
00
00
00
00
00
00
00
00
00
00
01
10
4456465
켜진 칸은 \((c,s) = (0,0)\) 과 \((1,1)\) 이다. 비트 번호는 \(17\cdot0+0 = 0\) 과 \(17\cdot1+1 = 18\) 이므로 \(N = 2^{0} + 2^{18} = 262145\), \(k = 17N = 4456465\) 이다.
3
000
000
000
000
000
000
000
000
000
000
000
000
000
000
000
000
000
0
켜진 칸이 하나도 없으면 \(N = 0\) 이고 \(k = 0\) 이다.
riseoj 작성
출처 Original
평가 및 의견
Tupper의 자기 지시 공식
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Tupper의 자기 지시 공식