Bài toán gốc: 2109C - Codeforces

Tất cả các subtask đều có chung một ý tưởng: đưa ~x~ về một giá trị ~y~ bất kì, rồi sử dụng phép add n - y để đưa ~x~ về ~n~. Tuy nhiên, ý tưởng cho từng subtask lại không liên quan gì đến nhau.

Subtask 1: Ta tìm cách đưa ~n~ về ~1~ sau đó sử dụng lệnh add n - 1. Cụ thể:

• Áp dụng lệnh digit ~\Rightarrow~ ~x \in [1,81]~.

• Áp dụng lệnh digit ~\Rightarrow~ ~x \in [1,16]~.

• Đến đây việc áp dụng lệnh digit không còn hiệu quả do ta chỉ rút được ~x~ về khoảng ~[1,9]~ và không thể rút tiếp. Một ý tưởng để làm tiếp là sử dụng biểu diễn nhị phân của ~x~:

  • Áp dụng lệnh add -8 ~\Rightarrow~ ~x \in [1,8]~.

  • Áp dụng lệnh add -4 ~\Rightarrow~ ~x \in [1,4]~.

  • Áp dụng lệnh add -2 ~\Rightarrow~ ~x \in [1,2]~.

  • Áp dụng lệnh add -1 ~\Rightarrow~ ~x = 1~.

• Lệnh cuối cùng là add n - 1.

Số lệnh cần dùng tối đa là ~7~.

Subtask 2: Một số chia hết cho ~9~ khi và chỉ khi tổng các chữ số của nó chia hết cho ~9~. Như vậy ta có thể nghĩ đến ý tưởng nhân một số với ~9~ để làm cho nó chắc chắn chia hết cho ~9~, và áp dụng liên tiếp các lệnh digit để biến nó về ~9~. Cụ thể như sau:

• Áp dụng lệnh mul 9 để làm ~x~ chia hết cho ~9~.

• Áp dụng lệnh digit ~\Rightarrow~ ~9 \le x \le 81, 9|x~.

• Áp dụng lệnh digit ~\Rightarrow~ ~x=9~.

• Cuối cùng gọi lệnh add n - 9.

Số lệnh cần dùng tối đa là ~4~.

Subtask 3:

Ta sẽ chứng minh ~S \left( x \cdot (10^d-1) \right) = 9d~ ~\forall x \in [1,10^d]~.

• Nhận thấy ~x \cdot (10^d - 1)~ ~= x \cdot 10^d - x =~ ~(x - 1) \cdot 10^d + 10^d - x~ ~= (x - 1) \cdot 10^d + [(10^d - 1) - (x - 1)]~.

• Số hạng thứ nhất biểu diễn ~(x - 1)~ được dịch sang trái ~d~ vị trí (tức là nhân với ~10^d~). Số hạng thứ hai là một chuỗi gồm ~d~ chữ số ~9~ trừ đi ~(x - 1)~, cụ thể là ~\underbrace{999 \dots 999}_{d \text{ lần}} - (x - 1)~.

• Vì mọi chữ số của chuỗi trên đều là ~9~, phép trừ cho ~(x - 1)~ hoàn toàn không xảy ra việc nhớ ở bất kỳ hàng nào. Do đó, với mọi ~i~ (~1 \le i \le d~), chữ số thứ ~i~ của số hạng thứ hai và chữ số thứ ~(i + d)~ của số hạng thứ nhất sẽ bù trừ cho nhau để có tổng bằng ~9~.

• Có tổng cộng ~d~ cặp chữ số bù nhau như vậy, tổng các chữ số của toàn bộ kết quả hiển nhiên sẽ bằng ~9d~.

Như vậy ta chỉ cần chọn ~d=9~ là có thể biến đổi mọi ~x \in [1,10^9]~ về ~n~ trong đúng ~3~ bước:

• Áp dụng lệnh mul ~999\,999\,999~.

• Áp dụng lệnh digit ~\Rightarrow~ ~x=81~.

• Nếu ~n \neq 81~, gọi add n - 81.

Corner case: chỉ cần dùng ~2~ lệnh với ~n=81~.

Chứng minh vì sao không thể đạt được số ~n~ nào khác ~81~ chỉ trong ~\le 2~ lệnh:

• Xét các lựa chọn cho lệnh đầu tiên:

  • add y: Với ~y~ dương, lệnh này chỉ dịch khoảng giá trị có thể của ~x~. Với ~y~ âm, khoảng giá trị của ~x~ có thể giảm, nhưng không giảm quá một nửa kích thước của khoảng đó (với một lệnh add, khoảng giá trị của ~x~ bị chia làm 2 phần, nên tối thiểu kích thước của phần lớn hơn ~\ge \frac{L}{2}~). Tóm lại, trong cả hai trường hợp, không thể ép ~x~ về một giá trị duy nhất.

  • div y: Lệnh này thất bại ngay cả với các giá trị ~x~ nhỏ (ví dụ ~1 \le x \le 4~), vì nó không ép ra được một kết quả duy nhất.

  • digit: Sau lần áp dụng đầu tiên, nó chỉ giới hạn ~x~ trong khoảng ~[1, 81]~, và lần áp dụng thứ hai chỉ thu hẹp khoảng này xuống ~[1, 16]~. Ta vẫn không thu được một giá trị cố định duy nhất.

• Như vậy lựa chọn còn lại là mul y. Rõ ràng, ~y \le 10^9~ để phép nhân không bao giờ bị tràn số. Giả sử tồn tại ~y \neq 999\,999\,999~ mà ~S(x \cdot y)~ là hằng số với mọi ~x \le 10^9~. Mà ~S(1 \cdot y) \le 80 < 81 = S(999\,999\,999 \cdot y)~. Như vậy điều giả sử là vô lý.

• Tương tự như lập luận ở trên, lưu ý rằng ~S(i) \neq S(i + 1)~, lệnh thứ hai bắt buộc phải là digit (vì đây là cách duy nhất để tiếp tục thu hẹp khoảng không gian trạng thái, không có lệnh nào khác làm được). Do đó, chỉ có trường hợp ~n = 81~ mới có thể đạt được kết quả cố định trong hai lệnh; mọi giá trị ~n~ khác đều cần tới ba lệnh.

#include <bits/stdc++.h>

using namespace std;

int main() {
  int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;
    cout << "mul 999999999" << endl;
    int x;
    cin >> x;
    cout << "digit" << endl;
    cin >> x;
    if (n != 81) {
      cout << "add " << n - 81 << endl;
      cin >> x;
    }
    cout << "!" << endl;
    cin >> x;
  }
  return 0;
}