solution

Lan truyền hằng số (constant propagation) là một phép tối ưu xác định biến nào luôn nhận một giá trị biết trước tại thời điểm dịch (compile-time constant), và biến nào phụ thuộc dữ liệu chỉ có lúc chạy nên trình biên dịch không thể biết trước.

Cho một chuỗi câu lệnh gán tuần tự, mỗi câu lệnh có một trong hai dạng:

• var = a
• var = a OP b

trong đó a, b mỗi cái là một trong: một số nguyên hằng (có thể âm), từ khoá INPUT (đại diện một giá trị đọc từ người dùng lúc chạy — không biết trước được), hoặc tên một biến đã được gán trước đó trong chương trình. OP $\in \{+, -, *, \texttt{//}\}$, với // là chia lấy phần nguyên kiểu Python (làm tròn về $-\infty$); đề bảo đảm không có phép // nào chia cho một giá trị mà tại thời điểm đó là hằng số 0. Mỗi lần một biến var xuất hiện ở vế trái, giá trị (và tính "hằng" hay không) của nó bị ghi đè hoàn toàn bởi câu lệnh đó.

Một phép gán được coi là cho ra giá trị hằng nếu và chỉ nếu mọi toán hạng ở vế phải (tại đúng thời điểm câu lệnh đó thực hiện) đều là hằng số hoặc biến đang mang giá trị hằng — khi đó giá trị của var được tính trực tiếp bằng công thức tương ứng. Nếu có bất kỳ toán hạng nào là INPUT, hoặc là biến đang không phải hằng, thì kết quả gán là không hằng (dù có thể một số toán hạng khác là hằng).

Cho $m$ truy vấn, mỗi truy vấn là tên một biến; với mỗi truy vấn, dựa vào lần gán cuối cùng của biến đó (nếu có) hãy cho biết: giá trị hằng của nó (nếu là hằng), hoặc biến đó không phải hằng, hoặc biến đó chưa từng xuất hiện ở vế trái lần nào.

Ví dụ: với 3 lệnh x = 5, y = x + 3, z = y * 2 thì x là hằng giá trị 5, z là hằng giá trị 16.