헥사코인 잼 timer 90s memory 1024MB

Code Jam 팀의 첫 번째 암호화폐인 jamcoin은 끝내 인기를 끌지 못했다. 올해는 16진법을 사용한다는 점에서 이름을 딴 hexacoin으로 다시 도전한다! D자리(hex) hexacoin을 "채굴"하려면, 필요하다면 앞에 0을 붙이더라도 정확히 D개의 16진수 자리로 표현되는 정수들만 다뤄야 한다. 각 값은 0 이상 16^D - 1 이하의 정수를 나타낸다. 16진수 자리는 일반적으로 그렇듯 0부터 9까지의 숫자와 대문자 A부터 F까지의 글자로 표현한다. 예를 들어 D=3일 때 F2B, 0C8, 000은 모두 유효한 값이며, 각각 10진수로 3883, 200, 0에 해당한다. 반면 D=3일 때 1234, DF, C0DE, JAM은 유효한 값이 아니다.

D자리 16진수 값끼리 덧셈을 할 때는, 자릿수 넘침(overflow)으로 생기는 더 높은 자리들은 버린다. 즉, 덧셈은 16^D로 나눈 나머지(modulo)로 계산된다. 예를 들어 F2B + 0C8 = FF3(10진수로 4083)이고, F2B + F2B = E56이다(10진수로는 3670인데, 합의 10진수 값은 7766이고 16³으로 나눈 나머지가 3670이기 때문이다).

D자리 hexacoin을 "채굴"하기 위해 컴퓨터는 다음 과정을 수행한다.

1. D자리 16진수 값 N개로 이루어진 목록 L ( L₁, L₂, ..., L_N )을 선택한다.
2. D자리 16진수 값의 목표 구간을 선택한다: S부터 E까지(양 끝 포함)이다.
3. 16진수 자리 0부터 F까지에 대한 순열 P를, 가능한 16!개의 순열 중에서 균등 무작위로 하나 선택한다.
4. P를 목록의 모든 수의 모든 자리에 적용해 새 목록 L'을 만든다. 형식적으로, L'의 i번째 원소의 j번째 자리는 L의 i번째 원소의 j번째 자리에 P를 적용한 결과이다.
5. L'에서 서로 다른 두 원소를 중복 없이 고르되, 가능한 모든 쌍 중에서 균등 무작위로 하나를 선택한다. 이 선택은 순열을 고른 것과 독립적으로 이루어진다.
6. 선택된 두 원소를 더하되, overflow 자리는 버리고(즉 16^D로 모듈러 덧셈을 해서) 합을 계산한다.

마지막 단계에서 계산된 합이 S 이상 E 이하라면 hexacoin을 찾은 것이다! 예를 들어 다음과 같다고 하자.

• L = [134, 000, FFB, 000, AA9].
• S = 85C이고 E = EDF이다.
• 컴퓨터가 우연히 P = (0 → 4, 1 → A, 2 → 2, 3 → 8, 4 → 9, 5 → B, 6 → C, 7 → 7, 8 → F, 9 → 1, A → 0, B → 3, C → 5, D → 6, E → E, F → D) 를 선택했다고 하자.

그러면 P를 L에 적용했을 때 얻는 L'은 [A89, 444, DD3, 444, 001]이 된다. P는 S와 E에는 적용하지 않는다는 점에 유의하라.

고를 수 있는 쌍은 (5 × 4) / 2 = 10개이며, 각 쌍이 선택될 확률은 1/10이다. 이 중 합이 구간 안에 들어오는 경우는 A89 + DD3 = 85C, 444 + 444 = 888, A89 + 001 = A8A, DD3 + 001 = DD4, 그리고 A89 + 444 = ECD(이 경우는 444가 두 번 있으므로 두 번 등장한다)이다.

처음 두 단계는 이미 계산되어 있고, 당신은 선택된 목록 L과 구간 [S, E]를 알고 있다. 나머지 과정이 수행된 뒤 hexacoin을 찾을 확률은 얼마인가?