Phân tích

Gọi \(w_C\) là khối lượng nguyên tử của Codium và \(w_J\) là khối lượng nguyên tử của Jamarium theo các quy tắc trong đề bài. Với mọi \(1 \le i < N\), đặt \(\Delta C_i = C_{i+1} - C_i\) và \(\Delta J_i = J_{i+1} - J_i\). Tương tự như trong phần phân tích bài Nguyên tố mới: Phần 1, ta có:

• \(-\Delta C_i / \Delta J_i < w_J / w_C\) nếu \(\Delta J_i > 0\).
• \(w_J / w_C < -\Delta C_i / \Delta J_i\) nếu \(\Delta J_i < 0\).
• \(-\Delta C_i \times w_C < 0\) nếu \(\Delta J_i = 0\).

Do đó, chỉ cần xét các vị trí liên tiếp là ta có thể tìm được cận dưới và cận trên của \(w_J / w_C\). Ban đầu, ta đặt cận dưới (biểu diễn bằng phân số tối giản \(L_N / L_D\)) bằng 0 và cận trên (biểu diễn bằng phân số tối giản \(U_N / U_D\)) bằng \(\infty\). Với mỗi cặp chỉ số liên tiếp, ta cập nhật \(L_N / L_D\) hoặc \(U_N / U_D\), hoàn toàn tương tự phần phân tích của Phần 1.

Sau khi có \(L_N / L_D\) và \(U_N / U_D\), ta cần tìm một số hữu tỉ \(w_J / w_C\) sao cho

Nếu \(L_N / L_D \ge U_N / U_D\) thì chắc chắn không có lời giải. Ngược lại, phải tồn tại ít nhất một lời giải; chẳng hạn, phân số trung gian (mediant)

chắc chắn nằm giữa hai cận. Tuy nhiên, bài toán yêu cầu ta tối thiểu hóa \(w_C\) và \(w_J\) (trước hết là \(w_C\), sau đó là \(w_J\)).

Test Set 1

Vì \(\Delta J_i \le 99\) trong test set này, ta có \(L_D + U_D \le 198\). Vì vậy, ta biết rằng tồn tại một lời giải với \(w_C \le 198\). Ta có thể thử mọi giá trị từ 1 đến 198 cho \(w_C\). Với mỗi lựa chọn \(w_C\), ta suy ra giá trị \(w_J\) nhỏ nhất thỏa mãn \(L_N / L_D < w_J / w_C\), rồi kiểm tra xem \(w_J / w_C < U_N / U_D\) có đúng hay không.

Test Set 2

Với mỗi số nguyên \(C\) (từ 1 đến \(L_D + U_D\)), ta có thể kiểm tra xem có số hữu tỉ nào nằm nghiêm ngặt giữa \(L_N / L_D\) và \(U_N / U_D\), đồng thời có mẫu số không vượt quá \(C\), hay không. Để làm điều đó, ta có thể tìm số hữu tỉ có mẫu số không vượt quá \(C\) và gần trung bình cộng của \(L_N / L_D\) với \(U_N / U_D\) nhất. Cách này đúng vì mọi số hữu tỉ nằm nghiêm ngặt giữa \(L_N / L_D\) và \(U_N / U_D\) đều gần giá trị trung bình ấy hơn mọi số hữu tỉ không nằm nghiêm ngặt giữa hai cận. Ta có thể dùng một hàm thư viện như fractions.limit_denominator của Python, hoặc tự cài đặt phép xấp xỉ bằng phân số liên tục.

Khi đã giải được bài toán con trong đoạn trước, ta có thể dùng tìm kiếm nhị phân để tìm \(w_C\): đó là giá trị \(C\) nhỏ nhất sao cho tồn tại một số hữu tỉ có mẫu số không vượt quá \(C\) và nằm nghiêm ngặt giữa \(L_N / L_D\) với \(U_N / U_D\). Tương tự như với test set trước, ta suy ra \(w_J\) nhỏ nhất thỏa mãn \(L_N / L_D < w_J / w_C\).

Dữ liệu kiểm thử

Chúng tôi khuyên bạn nên luyện tập gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

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 2 — New Elements: Part 2.