bonus

[javelinsman]

Bonus 1. Pascal's Triangle Reconstruction

보너스 문제는 평균적인 실습 문제보다 더 어렵게 출제되며, 학생들의 자발적 심층 학습을 돕기 위한 문제입니다. 보너스 문제를 풀면 다른 실습 문제에서 받은 감점을 일부 면제받을 수 있습니다. 따라서 평소에 실습을 성실히 수행했다면 보너스 문제를 풀지 않아도 불이익은 없습니다. 실습 시간에는 보너스 문제에 대한 질문을 받지 않습니다.

파스칼의 삼각형은 1에서 시작해서, 양 끝은 모두 1로 고정하고, 나머지는 위의 행에 인접한 두 숫자를 더해서 만들어집니다. 자세한 사항은 Wikipedia를 참조하세요

이 문제는 위의 파스칼 삼각형을 확장해서, 임의의 숫자 리스트로부터 시작해 삼각형을 계산합니다. 파스칼 삼각형과 마찬가지로, 어떤 한 행이 주어졌을 때 다음 행의 양 끝은 이전 행과 동일하고, 행의 중간에는 이전 행에서 인접한 두 수의 합이 오게 됩니다. 예를 들어 2 7 8 3이 주어졌을 때, 그 다음 행은 양끝이 2와 3으로 동일하고 가운데에 2+7(9), 7+8(15), 8+3(11)이 오게 되어 결과적으로 2 9 15 11 3이 됩니다. 이를 반복하면 아래와 같이 확장된 파스칼 삼각형을 얻을 수 있습니다.

2 7 8 3 <-- 시작
2 9 15 11 3
2 11 24 26 14 3
2 13 35 50 40 17 3
...

1 8 10 5 7 5 <-- 시작
1 9 18 15 12 12 5
1 10 27 33 27 24 17 5
...

한편, 주어진 행으로부터 위의 행이 무엇이었을 지를 계산하는 것도 가능합니다. 위의 두 개의 예시에서 2 7 8 3은 사실 2 5 3의 다음 행이고, 2 5 3은 2 3의 다음 행입니다. 1 8 10 5 7 5는 1 7 3 2 5의 다음 행입니다. 따라서, 위의 두개 예시는 사실 아래와 같은 더 큰 삼각형의 일부라고 이해할 수 있습니다.

2 3
2 5 3
2 7 8 3 <-- 시작
2 9 15 11 3
2 11 24 26 14 3
2 13 35 50 40 17 3

1 7 3 2 5
1 8 10 5 7 5 <-- 시작
1 9 18 15 12 12 5
1 10 27 33 27 24 17 5

주어진 행과 양 끝이 같고, 길이가 1 작으면서, 0보다 큰 자연수로만 이루어져 있는 수열이 없다면 이전 행이 없다고 정의합니다. 위의 예시에서 2 3과 1 7 3 2 5는 이전 행이 정의되지 않습니다.

문제는 어떤 한 행이 주어졌을때 그것의 전후에 나올 행들을 계산하여 확장된 삼각형을 출력하는 것입니다.

• 주어진 행으로부터 이전 행이 존재하지 않을 때까지 이전 행들을 모두 계산합니다.
• 이전 행들을 모두 계산했을 때, 주어진 행을 포함하여 전체 행의 개수가 10보다 작다면, 주어진 행의 다음 행들을 차례로 계산해서 10개를 채웁니다
• 주어진 행을 포함한 전체 행의 개수가 10보다 크다면 다음 행은 계산하지 않고 해당 행들을 모두 출력합니다.

입력

처음 한 줄에 띄어쓰기로 구분된 숫자들이 주어집니다. 숫자는 적어도 1개 있음이 보장됩니다. 이는 어떤 삼각형의 한 줄입니다.

출력

위의 조건에 따라 확장한 삼각형을 출력합니다. 이때, 각 줄은 Python의 list를 출력하는 형식과 동일해야 합니다. 숫자들을 list에 담은 후 그대로 print()하면 됩니다.

예시 입력 1

1 8 10 5 7 5

예시 출력 1

[1, 7, 3, 2, 5]
[1, 8, 10, 5, 7, 5]
[1, 9, 18, 15, 12, 12, 5]
[1, 10, 27, 33, 27, 24, 17, 5]
[1, 11, 37, 60, 60, 51, 41, 22, 5]
[1, 12, 48, 97, 120, 111, 92, 63, 27, 5]
[1, 13, 60, 145, 217, 231, 203, 155, 90, 32, 5]
[1, 14, 73, 205, 362, 448, 434, 358, 245, 122, 37, 5]
[1, 15, 87, 278, 567, 810, 882, 792, 603, 367, 159, 42, 5]
[1, 16, 102, 365, 845, 1377, 1692, 1674, 1395, 970, 526, 201, 47, 5]

예시 입력 2

1 7 3 2 5

예시 출력 2

[1, 7, 3, 2, 5]
[1, 8, 10, 5, 7, 5]
[1, 9, 18, 15, 12, 12, 5]
[1, 10, 27, 33, 27, 24, 17, 5]
[1, 11, 37, 60, 60, 51, 41, 22, 5]
[1, 12, 48, 97, 120, 111, 92, 63, 27, 5]
[1, 13, 60, 145, 217, 231, 203, 155, 90, 32, 5]
[1, 14, 73, 205, 362, 448, 434, 358, 245, 122, 37, 5]
[1, 15, 87, 278, 567, 810, 882, 792, 603, 367, 159, 42, 5]
[1, 16, 102, 365, 845, 1377, 1692, 1674, 1395, 970, 526, 201, 47, 5]

예시 입력 3

2 7 8 3

예시 출력 3

[2, 3]
[2, 5, 3]
[2, 7, 8, 3]
[2, 9, 15, 11, 3]
[2, 11, 24, 26, 14, 3]
[2, 13, 35, 50, 40, 17, 3]
[2, 15, 48, 85, 90, 57, 20, 3]
[2, 17, 63, 133, 175, 147, 77, 23, 3]
[2, 19, 80, 196, 308, 322, 224, 100, 26, 3]
[2, 21, 99, 276, 504, 630, 546, 324, 126, 29, 3]

예시 입력 4

1

예시 출력 4

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]

예시 출력 5

1 10 45 120 210 252 210 120 45 10 1

예시 출력 5

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]
[1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1]

[javelinsman]

Bonus 2. Hexademical Look-and-say Sequence

보너스 문제는 평균적인 실습 문제보다 더 어렵게 출제되며, 학생들의 자발적 심층 학습을 돕기 위한 문제입니다. 보너스 문제를 풀면 다른 실습 문제에서 받은 감점을 일부 면제받을 수 있습니다. 따라서 평소에 실습을 성실히 수행했다면 보너스 문제를 풀지 않아도 불이익은 없습니다. 실습 시간에는 보너스 문제에 대한 질문을 받지 않습니다.

이 문제에서는 흔히 "개미 수열"이라고 알려진 읽고 말하기 수열을 구현하는 것이 목표입니다. 읽고 말하기 수열에 대한 자세한 설명은 Wikipedia를 참조하세요. 이해를 돕기 위해 아래의 예시를 참조하세요.

1. 1이라는 문자열이 처음에 주어졌습니다.
2. 1에는 1이 1개 있으므로, 다음 문자열은 11이 됩니다.
3. 11에는 1이 2개 있으므로, 다음 문자열은 12가 됩니다.
4. 12에는 1이 1개, 2가 1개 있으므로, 다음 문자열은 1121이 됩니다.
5. 1121에는 1이 3개, 2가 1개 있으므로, 다음 문자열은 1321이 됩니다.
6. 1321에는 1이 2개, 2가 1개, 3이 1개 있으므로, 다음 문자열은 122131이 됩니다.

이 문제에서의 특이한 점은, 문자열이 1-9 뿐만 아니라 a-f로도 구성된다는 점입니다. 또, 개수를 셀 때는 16진수로 나타냅니다. 다음의 예시를 보세요.

1. aaaaaaaaaa11111111111라는 문자열이 처음에 주어졌습니다.
2. aaaaaaaaaa11111111111에는 1이 b(=11)개, a가 a(=10)개 있으므로, 다음 문자열은 1baa가 됩니다.
3. 1baa에는 1이 1개, a가 2개, b가 1개 있으므로, 다음 문자열은 11a2b1이 됩니다.

각 문자의 개수가 두 자리수를 넘어가는 경우, 해당 수를 그대로 이어붙이면 됩니다.

1. eeeeeeeeeeeeeeeef라는 문자열이 처음에 주어졌습니다.
2. eeeeeeeeeeeeeeeef에는 e가 10(=16)개, f가 1개 있으므로, 다음 문자열은 e10f1이 됩니다.

그런데, 실제로 읽고 말하기 수열을 구현해보면 어느 정도 진행되다가 비슷한 문자열을 계속 맴돈다는 것을 알 수 있습니다. 예를 들어, 1에서부터 시작하는 읽고 말하기 수열을 계속 진행시키면 다음과 같습니다.

1
1
11
12
1121
1321
122131
132231
122232
112431
13213141
14213241
13223142
12233241
12233241
12233241
12233241
12233241
...

따라서 이 문제에서는 다음과 같이 출력하기로 합니다.

1. 초기 문자열이 주어집니다.
2. 초기 문자열을 포함해서, 16진수로 된 읽고 말하기 수열을 계속해서 출력해나갑니다.
3. 이미 출력한 문자열에 다시 도달하는 경우, 프로그램을 바로 종료합니다.

모든 초기 문자열은 언젠가 출력한 문자열에 다시 도달한다는 것이 보장됩니다.

입력

처음 한 줄에 0-9, a-f, A-F로 구성된 문자열이 주어집니다. 대소문자를 구분하지 않고 전부 소문자로 바꾼 후에 문제를 풀어야 합니다.

출력

위에서 설명한 방식에 따라 16진수로 된 읽고 말하기 수열을 출력합니다. 초기 문자열을 포함해야 하며, 출력되는 모든 영문자는 소문자여야 합니다.

예시 입력 1

1

예시 출력 1

1
11
12
1121
1321
122131
132231
122232
112431
13213141
14213241
13223142
12233241

예시 입력 2

a

예시 출력 2

a
a1
11a1
13a1
1231a1
132131a1
142132a1
13223141a1
14223241a1
13233142a1
13223341a1

예시 입력 3

AAAAAAAAAA

예시 출력 3

aaaaaaaaaa
aa
a2
21a1
1221a1
1322a1
122231a1
132331a1
132133a1

예시 입력 4

123456789abCDef

예시 출력 4

123456789abcdef
112131415161718191a1b1c1d1e1f1
1102131415161718191a1b1c1d1e1f1
011102131415161718191a1b1c1d1e1f1
021112131415161718191a1b1c1d1e1f1
011112231415161718191a1b1c1d1e1f1

예시 출력 5

aaaaaaAAAABBBbbbbbbbbccccccccccCCDDDDDDDddddddeeeeeeEEEEEEEEFFFffffffffffff

예시 출력 5

aaaaaaaaaabbbbbbbbbbbccccccccccccdddddddddddddeeeeeeeeeeeeeefffffffffffffff
aabbccddeeff
a2b2c2d2e2f2
26a1b1c1d1e1f1
162161a1b1c1d1e1f1
192162a1b1c1d1e1f1
18226191a1b1c1d1e1f1
1922618191a1b1c1d1e1f1
1a22618192a1b1c1d1e1f1
1923618191a2b1c1d1e1f1
192231618192a1b1c1d1e1f1
1a2331618192a1b1c1d1e1f1
1a2232618191a2b1c1d1e1f1
192431618191a2b1c1d1e1f1
1a223141618192a1b1c1d1e1f1
1b233141618191a2b1c1d1e1f1
1b223241618191a1b2c1d1e1f1
1a243141618191a1b2c1d1e1f1
1b223142618191a2b1c1d1e1f1