Phân tích

Trong bài toán này, ta cần xác định số lượng nhẫn của từng loại X ngày bằng cách truy vấn tổng số nhẫn đang tồn tại vào cuối một ngày nào đó.

Gọi \(R_1\) là số nhẫn 1 ngày, \(R_2\) là số nhẫn 2 ngày, ..., tại cuối ngày 0. Số nhẫn X ngày tăng gấp đôi vào cuối mỗi ngày là bội của \(X\). Vì vậy, tổng số nhẫn vào ngày \(i\) là

Test set 1

Trong test set đầu tiên, ta được phép thực hiện sáu truy vấn để xác định sáu biến chưa biết. Lưu ý rằng nếu truy vấn một ngày lớn hơn 63, số nhẫn 1 ngày vào ngày đó sẽ là một bội của \(2^{63}\) (tương đương bằng 0 theo modulo \(2^{63}\)). Tương tự, nếu truy vấn một ngày lớn hơn \(X \cdot 63\), số nhẫn X ngày vào ngày đó sẽ bằng 0 theo modulo \(2^{63}\).

Do đó, vào ngày \(315 = 5 \cdot 63\), tổng số nhẫn theo modulo \(2^{63}\) là \(R_6 \cdot 2^{52}\) (vì số nhẫn 1 ngày, 2 ngày, ..., 5 ngày đều bằng 0 theo modulo \(2^{63}\)). Vì \(R_6 \le 100\), ta biết \(R_6 \cdot 2^{52}\) không vượt quá \(2^{63}\), nên có thể xác định trực tiếp \(R_6\). Tiếp theo, vào ngày \(252 = 4 \cdot 63\), tổng số nhẫn theo modulo \(2^{63}\) là \(R_6 \cdot 2^{42} + R_5 \cdot 2^{50}\). Vì đã biết \(R_6\) và biết tổng này không thể lớn hơn \(2^{63}\), ta có thể tìm \(R_5\). Ta tiếp tục quá trình này bằng cách truy vấn các ngày \(189 = 3 \cdot 63\), \(126 = 2 \cdot 63\), \(63 = 1 \cdot 63\) và 1 để lần lượt xác định \(R_4\), \(R_3\), \(R_2\) và \(R_1\).

Cách khác

Vì ta truy vấn sáu ngày và cần tìm sáu biến, ta có thể chọn truy vấn, chẳng hạn, các ngày 1, 2, ..., 6. Khi đó ta thu được một hệ sáu phương trình với sáu ẩn. Vì các phương trình này độc lập tuyến tính, ta có thể giải hệ, chẳng hạn bằng phương pháp khử Gauss, để thu được đáp án.

Test set 2

Test set thứ hai đòi hỏi thêm một nhận xét. Ta chỉ có hai truy vấn, vì vậy mỗi truy vấn phải giúp tìm được nhiều giá trị \(R_i\) cùng lúc.

Hãy xét thông tin nhận được khi truy vấn ngày \(189 = 3 \cdot 63\). Ta nhận được \(R_6 \cdot 2^{31} + R_5 \cdot 2^{37} + R_4 \cdot 2^{47}\) theo modulo \(2^{63}\). Tuy nhiên, các phần \(R_6 \cdot 2^{31}\) và \(R_5 \cdot 2^{37}\) có thể chồng lấn. Ví dụ, nếu mọi yếu tố khác đều như nhau, ta không thể phân biệt trường hợp \(R_6 = 64\), \(R_5 = 0\) với trường hợp \(R_6 = 0\), \(R_5 = 1\). Trong cả hai trường hợp, hai loại này đều đóng góp tổng cộng \(2^{37}\) chiếc nhẫn.

Ta phải tận dụng điều kiện \(R_i \le 100\). Để số nhẫn \(i\) ngày không ảnh hưởng đến số nhẫn \((i-1)\) ngày vào ngày \(d\), ta cần

Lưu ý rằng điều này tương đương với \(\lfloor d/(i-1) \rfloor \ge \lfloor d/i \rfloor + 7\), vì \(2^7 > 100\). Nếu bỏ qua giới hạn modulo \(2^{63}\), ta có thể giải bài toán chỉ bằng một truy vấn, chẳng hạn truy vấn ngày 1000. Khi đó ta nhận được

Vì \(R_i \le 100\), ta có thể xác định \(R_6\) bằng cách lấy giá trị này modulo \(2^{200}\) để thu được \(R_6 \cdot 2^{166}\), rồi chia cho \(2^{166}\). Sau đó, ta có thể lần lượt xác định \(R_5\), \(R_4\), ..., \(R_1\). Tuy nhiên, ý tưởng này không dùng được vì bài toán tính theo modulo \(2^{63}\). Không có một truy vấn duy nhất nào có thể cung cấp toàn bộ thông tin cần thiết theo modulo \(2^{63}\).

Ta sẽ dùng truy vấn thứ nhất để xác định \(R_4\), \(R_5\) và \(R_6\), rồi dùng truy vấn thứ hai để xác định \(R_1\), \(R_2\) và \(R_3\). Ở trên, ta đã thấy truy vấn ngày \(189 = 3 \cdot 63\) không dùng được. Tuy nhiên, truy vấn ngày 200 chẳng hạn sẽ hoạt động:

Sau đó, ta tìm từng giá trị theo cùng cách như trong trường hợp ngày 1000. Tiếp theo, ta có thể thực hiện truy vấn thứ hai, chẳng hạn ở ngày 56:

Ta đã biết \(R_4\), \(R_5\) và \(R_6\) từ bước đầu tiên, nên có thể thay các giá trị ấy vào biểu thức rồi lần lượt tìm \(R_1\), \(R_2\) và \(R_3\).

Lưu ý rằng 200 và 56 không phải là những lựa chọn duy nhất. Trong bài toán này, ta có thể thử các giá trị ngoại tuyến hoặc (tốt hơn) viết một vòng lặp trong chương trình để tìm hai giá trị thỏa mãn các tiêu chí. Ta cũng cần bảo đảm rằng số hạng có số mũ lớn nhất không quá lớn. Ví dụ, không thể dùng truy vấn ngày 250 ở bước đầu tiên, vì khi đó ta nhận được \(R_4 \cdot 2^{62} + R_5 \cdot 2^{50} + R_6 \cdot 2^{41}\), và số hạng đầu tiên (\(R_4 \cdot 2^{62}\)) có thể không nhỏ hơn \(2^{63}\).

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2019, Vòng 1B — Draupnir.