Phân tích

Một cách tiếp cận là liệt kê các chuỗi độ dài \(N\) rồi kiểm tra chúng có phải jamcoin hay không. Để duyệt các jamcoin tiềm năng, ta có thể duyệt giá trị trong cơ số 2 của chúng — các số lẻ từ \(2^{N-1}+1\) đến \(2^N-1\), kể cả hai đầu — và dùng một hàm đệ quy để đổi các số này sang cơ số khác.

Với Test Set nhỏ, phép chia thử đủ để tìm thừa số của jamcoin tiềm năng. Cụ thể, tìm một ước không tầm thường của số nguyên \(k\) bằng cách thử tính chia hết cho mọi số nguyên tăng dần từ 2 đến \(\sqrt{k}\), kể cả đầu trên, và dừng khi tìm thấy. Không cần tìm quá căn bậc hai: nếu \(k\) có ước không tầm thường \(d\) thì \(k/d\) cũng là ước không tầm thường, và số nhỏ hơn trong \(d,k/d\) không vượt \(\sqrt{k}\). Một cài đặt C++ mẫu:

long long convertBinaryToBase(int x, int base) {
  // Some languages have built-ins which make this easy.
  // For example, in Python, we can avoid recursion and
  // just return int(bin(x)[2:], base)
  if (x == 0)
    return 0;
  return base * convertBinaryToBase(x / 2, base) + (x % 2);
}

long long findFactor(long long k) {
  for (long long d = 2; d * d <= k; d++)
    if (k % d == 0)
      return d;
  return 0;
}

void printCoins(int N, int X) {
  for (long long i = (1 << N-1) + 1; X > 0; i += 2) {
    vector<long long> factors;
    for (int base = 2; base <= 10; base++) {
      long long x = convertBinaryToBase(i, base);
      long long factor = findFactor(x);
      if (!factor)
        break;
      factors.push_back(factor);
    }
    if (factors.size() < 9)
      continue;

    cout << convertBinaryToBase(i, 10);
    for (long long factor : factors)
      cout << " " << factor;
    cout << endl;
    X -= 1;
  }
}

Giải Test Set lớn có thể gặp những thách thức riêng tùy ngôn ngữ. \(N=32\) nghĩa là trong cơ số 10 ta có các số 32 chữ số, không thể lưu bằng số nguyên 64 bit. Chúng cũng lớn đến mức chạy chia thử trên một số nguyên tố duy nhất có thể mất thời gian khổng lồ, thậm chí lâu hơn cả cuộc thi. Có thể khắc phục bằng cách dừng chia thử sớm (ví dụ sau 1000) và dùng số nguyên độ chính xác tùy ý, nhưng có một cách đẹp hơn nhiều.

Quan sát đầu ra Test Set nhỏ của chương trình trên. Trong 50 jamcoin độ dài 16 đầu tiên, 18 coin có các ước 3 2 3 2 7 2 3 2 3, còn 11 coin có các ước 3 2 5 2 7 2 3 2 11. Quy luật là gì? Các số 5, 7, 11 trong danh sách thứ hai gợi ý hữu ích: chúng lớn hơn cơ số tương ứng một đơn vị. Danh sách thứ hai được tạo bằng cách lấy thừa số nguyên tố nhỏ nhất của \(b+1\) với mỗi cơ số \(b\). Điều này gợi ý \(b+1\) luôn là ước của 11 jamcoin đó, và ta dễ dàng kiểm chứng. Việc hiểu danh sách ước phổ biến còn lại xin dành làm bài tập cho bạn đọc.

Trong cơ số \(b\), \(b+1\) được viết là \(11_b\). Có một dấu hiệu chia hết đơn giản cho 11 trong hệ thập phân: một số chia hết cho 11 nếu tổng chữ số ở vị trí lẻ và tổng chữ số ở vị trí chẵn chênh nhau một bội của 11. Quy tắc chia hết này mở rộng thành quy tắc: một chuỗi 0, 1 bắt đầu và kết thúc bằng 1, có cùng số lượng 1 ở chỉ số lẻ và chỉ số chẵn, thì khi hiểu là số cơ số \(b\) sẽ chia hết cho \(b+1\). Do đó chuỗi ấy là jamcoin, dù không phải mọi jamcoin đều thỏa điều kiện này.

Một điều kiện mạnh hơn nhưng dễ nhận thấy hơn: chuỗi 0, 1 bắt đầu và kết thúc bằng 1 là jamcoin nếu mọi chữ số 1 được ghép thành cặp, tức khớp biểu thức chính quy 11(0|11)*11. Ví dụ trong mọi cơ số \(b\), \(11011_b=1001_b\times11_b\).

Ví dụ cuối còn gợi ra quy tắc tổng quát hơn. Xét chuỗi p bất kỳ gồm 0, 1, dài ít nhất hai ký tự, bắt đầu và kết thúc bằng 1. Mọi chuỗi gồm p lặp nhiều lần, giữa các lần lặp có tùy ý số lượng 0, đều là jamcoin. Ở ví dụ trước p = 11, và quy tắc tổng quát viết bằng biểu thức chính quy (1[01]*1)(0*\1)+. Chẳng hạn, trong mọi cơ số \(b\),

Ta có thể dùng bất kỳ quy tắc nào trong số đó để đào jamcoin dễ dàng. Mã Python 2 sau đào các jamcoin có đúng năm cặp 11, đủ cho cả Test Set nhỏ và lớn.

def printCoins(N, X):
  # N digits, 10 1s, N-10 0s
  for i in range(N-10):
    for j in range(N-10-i):
      for k in range(N-10-i-j):
        l = N-10-i-j-k
        assert l >= 0
        template = "11{}11{}11{}11{}11"
        output = template.format("0"*i, "0"*j, "0"*k, "0"*l)
        factors = "3 2 5 2 7 2 3 2 11"
        print output, factors
        X -= 1
        if X == 0:
          return
  # If we get here, we didn't mine enough jamcoins!
  assert False

Nguồn

Bản dịch dựa trên phân tích chính thức Google Code Jam 2016 - Qualification Round - Coin Jam, kho Google Coding Competitions (Apache-2.0).