Numoeba

어떤 과학자가 아메바의 이상한 변종을 발견했다. 과학자는 이것을 numoeba라고 이름 붙였다. numoeba는 아메바처럼 보이지만, 사실은 항상 트리를 이루는 세포들의 군집이다.

과학자는 트리의 루트 위치에 있는 세포를 리더라고 불렀다. 예를 들어 Fig. 1에서 리더는 A이다. numoeba에서는 리더가 때때로 바뀔 수 있다. 예를 들어 E가 새로운 리더가 되면, Fig. 1의 트리는 Fig. 2와 같이 된다. numoeba에 대해서도 그래프 이론에서 정의된 대로 루트, 리프, 부모, 자식, 서브트리라는 용어를 사용한다.

Fig. 1

Fig. 2

numoeba는 생물학적 시계마다 세포 분열과 세포 죽음을 통해 물리적 구조를 바꾼다. 이 물리적 변화에 따라 리더가 바뀔 수도 있다.

numoeba 세포에 관한 가장 놀라운 사실은 1부터 12,345,677까지의 홀수를 나타내는 numbosome이라는 유기 단위를 세포가 포함한다는 것이다. 생물학적 시계마다 numbosome의 값은 n에서 다음과 같이 새로운 값으로 바뀐다.

1. 3n + 1의 최대 홀수 인수를 계산한다. 이 값은 3n + 1을 짝수인 동안 계속 2로 나누어 얻을 수 있다.
2. 그 결과가 12,345,678보다 크면 12,345,678을 뺀다.

예를 들어 어떤 세포의 numbosome 값이 13이면, 13 × 3 + 1 = 40을 23 = 8로 나누어 새로운 numbosome 값 5를 얻는다. 어떤 세포의 numbosome 값이 11,111,111이면 16,666,667 대신 4,320,989로 바뀐다. 3n + 1이 2의 거듭제곱이어서 결과가 1이 나오면, 아래에서 설명하듯이 세포의 죽음을 뜻한다.

생물학적 시계마다 모든 세포의 다음 numbosome 값을 계산하고, 다음 단계에 따라 세포의 운명과 그에 따른 numoeba의 운명을 결정한다.

1. 리프이면서 numbosome 값이 증가하는 세포를 후보 리프로 지정한다.

   numbosome 값이 1이 되면 세포는 죽는다. 죽는 세포가 numoeba의 리더라면 numoeba 전체가 죽는다. 그렇지 않으면 죽는 세포부터 시작하는 서브트리의 모든 세포(자기 자신 포함)가 죽는다. 다만 예외가 있는데, 죽는 리더가 아닌 세포의 자식 세포가 하나뿐이면 그 자식 세포가 죽는 세포를 대체한다. 따라서 직선 사슬은 리더가 아닌 구성 세포가 죽으면 그대로 줄어들 뿐이다.

   예를 들어 리더가 A인 아래의 numoeba를 보자.

   (1)

   

   (1)에서 리더 A가 죽으면 numoeba는 죽는다.

   (1)에서 세포 D가 죽으면 (1)은 다음과 같이 된다.

   (2)

   

   그리고 (1)에서 세포 E가 죽으면 (1)은 다음과 같이 된다.

   (3)

   

   이 절차는 numoeba의 루트에서 리프 방향으로, 위에서 아래로 순차적으로 실행된다. (1)에서 세포 E와 F가 죽는다면, 절차가 세포 E를 검사하는 시점에 F의 죽음은 아직 감지되지 않는다. 따라서 numoeba는 (3)이 된다. F의 죽음 때문에 G가 E의 유일한 자식이 되고, 그래서 G가 죽는 E를 대체한다고 생각해서는 안 된다.

2. 후보 리프가 numbosome 값 n을 가지고 살아남으면, 자식으로 세포를 하나 낳아 새로운 리프가 되게 한다. 새 리프의 numbosome 값은 (n + 1)/2보다 크거나 같은 가장 작은 홀수이다. 이 자식 리프를 보너스라고 부른다.

3. 마지막으로 numoeba의 새 리더를 선출한다. 새 리더는 모든 구성 세포 중에서 numbosome 값이 유일하게 최대인 세포이다. numoeba의 트리 구조는 Fig. 1과 Fig. 2에서처럼 새 리더가 루트가 되도록 바뀐다. 이 리더 변경으로 일부 세포의 부모-자식 관계가 뒤집힐 수 있다. numbosome 값이 유일하게 최대인 세포, 그 값을 m이라 하면, 새 리더가 선출되면(이전 리더와 같은 세포일 수도 있다) numbosome 값이 (m + 1)/2보다 작거나 같은 가장 큰 홀수인 세포를 자식으로 하나 낳는다. 이 자식 세포를 리더 보너스라고 부른다. 그러나 numbosome 값이 최대인 세포가 둘 이상이면 다음 주기 동안 리더는 바뀌지 않고 리더 보너스도 없다.

다음은 numbosome 값이 15인 단일 세포 씨앗에서 시작하는 numoeba의 성장과 죽음을 보여준다. 시작할 때 이 세포는 리더와 리프의 역할을 모두 맡는다. 그림에서 세포는 numbosome 값으로 불린다. 부모의 자식 순서는 중요하지 않다.

clock	structure	comments
0		15가 리더와 리프의 역할을 모두 맡는다.
1		23(15에서)이 새 리더(다시)이다. 13은 리프 보너스, 11은 리더 보너스이다.
2		17은 리더 보너스이다. 35(23에서)가 새 리더(다시)이다. 5는 13에서 나왔다. 17(11에서)이 리프 보너스 9를 낳는다.
3		13은 17에서 나왔다. 53(35에서)이 새 리더(다시)이다. 27은 리더 보너스이다. 5는 죽는다.
4		5는 13에서 나왔다. 41(27에서)이 새 리더이고, 리더 보너스와 리프 보너스로 둘 다 21을 낳는다. 5(53에서)는 리더 자리를 잃는다.
5		31(41에서)만 살아남고, 이것이 리더 보너스 15를 낳는다.

numoeba는 계속 구조를 바꾸며, clock 104에서는 다음과 같이 된다.

여기서 야심 찬 2429 두 개는 리더가 되지 못했다. 리더 5는 다음 clock에 이 재능 있는 세포들을 승진시키지 못한 채 죽는다. 이는 큰 조직의 취약함을 암시한다.

그리고 numoeba는 clock 105에서 죽는다.

여러분의 과제는 clock 0에서 단일 세포 씨앗으로 시작하는 numoeba의 생애에 관한 통계를 출력하는 프로그램을 작성하는 것이다.

한 줄에 하나씩 홀수 정수가 주어진다. 각 홀수 ki(3 ≤ ki ≤ 9,999)는 시작 세포의 초기 numbosome 값이다. 이 수열은 0으로 끝난다.

정수 쌍의 수열을 출력한다. 각 쌍은 numoeba의 수명을 나타내는 정수와 생애 중 구성 세포 수의 최댓값을 나타내는 정수로 이루어진다. 두 정수는 공백 하나로 구분하고, 각 쌍 뒤에는 바로 줄바꿈을 출력한다. 여기서 수명은 numoeba가 죽는 clock을 뜻한다.

입력으로 주어지는 모든 씨앗 값에 대해 수명이 500 미만이고 어떤 시점에도 세포 수가 500을 넘지 않는다는 사실을 이용해도 된다. 프로그램이 메모리를 많이 소모할 것이라고 짐작할 수 있다. 일반적으로는 사실이다. 하지만 걱정하지 마라. 채점 데이터는 시작 값이 10개 이하이고, 그중 어느 값에서 시작하더라도 수명 동안 낳는 세포 수의 합이 5000을 넘지 않는다.