solution

Xét một vòng lặp đơn (không rẽ nhánh, không lồng nhau) với biến điều khiển $i$ chạy từ $1$ đến $N$ (bước nhảy 1; nếu $N = 0$ vòng lặp không chạy lần nào). Thân vòng lặp có $m$ biến phụ $y_1,\ldots,y_m$; biến $y_k$ được định nghĩa lại mỗi lần lặp (tại thời điểm $i$ hiện tại của lần lặp đó) theo công thức tuyến tính: $y_k = a_k \cdot i + b_k$ với $a_k, b_k$ là hằng số nguyên cho trước, không đổi trong suốt vòng lặp. Quy ước giá trị "trước vòng lặp" (tại $i = 0$, khi vòng lặp chưa chạy lần nào) là $y_k = b_k$.

Yêu cầu:

1. Phân loại: nếu $a_k = 0$, $y_k$ là bất biến vòng lặp (loop-invariant) — in INVARIANT. Nếu $a_k \ne 0$, $y_k$ là biến quy nạp (induction variable) — in INDUCTION.
2. Giá trị cuối cùng: giá trị của $y_k$ ngay sau khi vòng lặp kết thúc (sau lần lặp thứ $N$, hoặc giá trị trước vòng lặp nếu $N = 0$) — tính theo công thức $a_k \cdot N + b_k$ (công thức này đúng cho mọi $N \ge 0$, kể cả $N=0$).
3. Số phép cộng trình biên dịch cần thực hiện khi áp dụng giảm độ mạnh phép toán (strength reduction): thay vì nhân lại $a_k \cdot i$ mỗi lần lặp, khởi tạo $y_k \leftarrow b_k + a_k$ trước vòng lặp rồi mỗi lần lặp sau chỉ cộng thêm $a_k$. Biến INVARIANT không cần phép cộng nào (chỉ gán 1 lần $b_k$). Biến INDUCTION cần đúng $N$ phép cộng nếu $N \ge 1$, và $0$ phép cộng nếu $N = 0$.

In ra $m$ dòng theo thứ tự $k = 1,\ldots,m$: y{k} INVARIANT gia_tri hoặc y{k} INDUCTION gia_tri. Dòng cuối cùng: ADDS=tong_so_phep_cong (tổng trên tất cả biến INDUCTION).

Ví dụ

Input:

3 3
0 5
2 1
-1 10

Output:

y1 INVARIANT 5
y2 INDUCTION 7
y3 INDUCTION 7
ADDS=6