비트코인 채굴하기
View as PDF문제
Hashing 문제를 푼 후에 이 문제를 푸는 것을 추천합니다.
\(H(a) = \displaystyle\sum_{i=0}^{l-1}a_i \times r^i \mod M\)
\((M = 1\,234\,567\,891, r = 31)\)
여러분들은 혹시 비트코인을 채굴해 본 적이 있으신가요? 이 문제를 통해 비트코인 채굴의 원리를 이해해봅시다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수입니다. 예를 들어 위 문제에서 사용하는 해시 함수에 ana라는 문자열을 넣으면 501140102을 얻을 수 있습니다.
비트코인을 채굴한다는 것은 임의의 문자열을 계속해서 해시 함수에 넣어보면서 출력 결과가 \(111\cdots\) 처럼 연속하는 1로 시작하는지 확인하는 것입니다. 예를 들어, ana이라는 문자열을 해시 함수에 넣었더니 1396이라는 결과가 나온것을 확인했다면, 여러분은 비트코인 채굴에 성공한 것입니다.
Hashing 문제에서 주어지는 해시 함수를 사용해서 출력 결과가 연속하는 1로 시작하는 문자열을 아무 것이나 구해봅시다. 당연히 연속하는 1의 개수가 많을수록 찾기 어렵기 때문에 더 높은 점수를 얻을 수 있습니다.
길이 5이하의 알파벳 소문자로 이루어진 문자열 중에 연속하는 1의 개수가 7개 이상인 문자열이 존재함이 보장됩니다. 따라서 여러분은 \(\mathcal{O}(26^5)\)개의 경우의 수를 모두 시도해보면 문제의 정답을 찾을 수 있습니다.
입력
이 문제는 입력이 주어지지 않습니다.
출력
이 문제는 Text로만 제출할 수 있습니다. 즉, 소스 코드를 작성해 제출하는 것이 아닌 알파벳 소문자로 이루어진 문자열 \(S\)를 작성해 제출해야 합니다.
점수
\(H(S)\)의 앞에서 연속하는 1의 개수 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 점수 | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 100 |
예제 입력
이 문제는 입력이 주어지지 않습니다.
예제 출력
ana\(H(\text{ana}) = 1396\)이고, 앞에서 연속하는 1의 개수는 1개입니다. 따라서 2점을 얻습니다.
Comments
수정1
.