Phân tích

Trước hết giải bài toán con: từ một đơn vị kim loại \(x\), có thể tạo đủ mọi kim loại yêu cầu không?

Dùng tham lam. Duy trì đa tập \(H\) các đơn vị đang có (ban đầu \(\{x\}\)) và đa tập \(D\) các đơn vị còn nợ (ban đầu là yêu cầu). Lặp:

1. Xóa giao \(H\cap D\) khỏi cả \(H,D\).
2. Nếu \(D\) rỗng, trả lời có. Nếu \(H\) rỗng mà \(D\) chưa rỗng, trả lời không.
3. Lấy toàn bộ \(c\) đơn vị của kim loại có chỉ số lớn nhất \(i\) còn trong \(H\).
4. Xóa chúng và chèn \(c\) đơn vị \(i-A\), \(c\) đơn vị \(i-B\) nếu chỉ số tương ứng hợp lệ.

Thuật toán đúng vì các đơn vị được biến đổi tham lam không phải thứ ta còn nợ, nên không có cách dùng nào tốt hơn (biến đổi có thể vô ích nhưng không gây hại). Các đơn vị đang nợ cũng nên được trả ngay: mọi việc có thể làm với đơn vị hiện tại cũng có thể làm với một đơn vị tương lai vốn dùng để trả món nợ đó.

Test Set 1

Nếu tìm được một đáp án \(m\) cho đầu vào mà \(N\) và mọi \(U_i\) đều đạt tối đa, quy trình cũng tạo đủ cho mọi đầu vào khác. Chạy kiểm tra tham lam trên trường hợp đó với \(m\) tăng dần nhanh chóng cho thấy \(m=29\) giải được. Vì vậy mọi đầu vào có đáp án không quá \(29\), và thử \(m\) tăng dần là lời giải hợp lệ cho toàn Test Set.

Cũng có thể chứng minh không có trường hợp bất khả thi và đáp án nhỏ. Số lượng tăng theo hàm mũ: từ một đơn vị \(m\), ta tạo được \(2\) đơn vị \(m-2\) (cùng phần dư), nên tạo được \(2^i\) đơn vị \(m-2i\). Phân phối chúng cho các phần tử từ \(m-2i-N+1\) đến \(m-2i\), ta có khoảng \(2^i/N\) đơn vị của mỗi trong \(N\) chỉ số liên tiếp; chúng còn có thể tiếp tục hạ xuống khi cần.

Do đó một \(m\) thỏa \(2^{m-2\times20}/20>20\) phải đủ; \(m=49\) thỏa điều kiện.

Test Set 2

Ví dụ cho thấy có trường hợp bất khả thi. Nếu cứ thử \(m\) mãi như Test Set 1, chương trình không kết thúc. Ta cần một cận trên tương đối nhỏ và trả IMPOSSIBLE sau cận đó; việc tìm và chứng minh cận phải dựa vào lý thuyết.

Từ kim loại \(m\), mọi kim loại tạo được có cùng số dư với \(m\) modulo \(g=\gcd(A,B)\). Đây là một ứng dụng của phương trình Diophantine, dù không bắt buộc phải biết lý thuyết đó.

Xét số dư modulo \(g\) của mọi \(i\) có \(U_i>0\). Nếu tất cả cùng một giá trị \(k\), thì \(m\bmod g\) cũng phải bằng \(k\). Nếu chúng không cùng số dư, bài toán bất khả thi.

Lúc này mọi chỉ số liên quan viết được thành \(gx+k\). Để chứng minh mọi trường hợp còn lại khả thi, có thể tổng quát hóa chứng minh Test Set 1 bằng đẳng thức Bézout; hoặc thử nghiệm mọi cặp nguyên tố cùng nhau \(A/g,B/g\) trên trường hợp lớn nhất.

Kết quả cho thấy đáp án lớn nhất của một trường hợp khả thi trong Test Set 2 là \(402\). Vì vậy thử \(m\) tới \(402\) bằng thuật toán tham lam; nếu không tìm thấy thì trả IMPOSSIBLE.

Dựa trên phân tích chính thức của Google Code Jam 2021, Vòng 1B, bài Subtransmutation.