Xét máy hai phép toán, gọi tắt là TOM, có chín thanh ghi được đánh số từ \(1\) đến \(9\). Mỗi thanh ghi lưu một số nguyên trong khoảng từ \(0\) đến \(1000\). Máy có hai phép toán:

Một chương trình TOM gồm các giá trị khởi tạo của chín thanh ghi và một dãy lệnh. Cho số nguyên \(N\), với \(0\le N\le255\), hãy tạo chương trình TOM in đúng dãy giảm dần \(N,N-1,N-2,\ldots,0\). Cần làm nhỏ nhất có thể số lệnh S liên tiếp lớn nhất trong chương trình.

Đây là bài chỉ nộp kết quả. Có 16 bộ dữ liệu vào, được đánh số từ 1 đến 16, trong tệp đính kèm ioi03reverse-inputs.zip. Với mỗi bộ, hãy nộp chương trình TOM dưới dạng tệp kết quả, không nộp chương trình sinh ra nó.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(K\), số thứ tự của bộ dữ liệu.
• Dòng thứ hai chứa \(N\).

Dữ liệu ra

Trong bản luyện tập, chọn ngôn ngữ OUTPUT và nộp một tệp ZIP chứa 16 tệp kết quả ngay tại thư mục gốc, không đặt trong thư mục con. Tên tệp kết quả dùng chỉ số từ 0 đến 15, trong khi số bộ dữ liệu \(K\) trong tệp vẫn là từ 1 đến 16:

Nội dung mỗi tệp kết quả giữ nguyên định dạng của đề gốc:

• Dòng đầu phải có dạng FILE reverse K, trong đó \(K\) là số thứ tự của bộ dữ liệu. Không có ký tự # trước FILE.
• Dòng thứ hai chứa chín số nguyên cách nhau bởi dấu cách, lần lượt là giá trị khởi tạo của thanh ghi 1, 2, ..., 9.
• Các dòng còn lại là các lệnh theo thứ tự thực hiện, mỗi dòng đúng một lệnh. Dòng thứ ba chứa lệnh đầu tiên. Mọi dòng phải là lệnh hợp lệ, viết theo dạng trong ví dụ.
• Dòng cuối cùng phải là lệnh in ra số \(0\); không được thực hiện thêm lệnh sau đó.

Chẳng hạn, reverse.0.out bắt đầu bằng FILE reverse 1, còn reverse.15.out bắt đầu bằng FILE reverse 16.

Phân nhóm

Có 16 bộ dữ liệu: bộ 1–12 mỗi bộ tối đa 6 điểm, bộ 13–16 mỗi bộ tối đa 7 điểm, tổng 100 điểm.

Điểm của mỗi bộ dựa trên tính đúng đắn và mức tối ưu của chương trình TOM:

• Tính đúng đắn, 20%: chương trình không có quá 131 lệnh S liên tiếp, in đúng \(N+1\) số theo thứ tự từ \(N\) xuống \(0\), và không có phép S nào làm giá trị thanh ghi vượt quá \(1000\).
• Mức tối ưu, 80%: đối với chương trình đúng, xét số lệnh S liên tiếp lớn nhất. Giá trị này càng nhỏ càng tốt. Điểm dựa trên độ chênh lệch so với chương trình TOM tốt nhất đã biết.

Bản luyện tập dùng các mốc cố định trong bộ đáp án gốc. Với các bộ dữ liệu từ 1 đến 16, mốc số lệnh S liên tiếp lớn nhất lần lượt là 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 4. Chương trình đúng đạt bằng hoặc tốt hơn mốc đều nhận toàn bộ điểm của bộ dữ liệu.

Gọi \(d\) là số lệnh S liên tiếp lớn nhất của chương trình trừ đi mốc tương ứng. Tỷ lệ điểm của một chương trình đúng là:

Ví dụ

1
2

FILE reverse 1
0 2 0 0 0 0 0 0 0
P 2
S 1 3
P 3
P 1

FILE reverse 1
0 2 1 0 0 0 0 0 0
P 2
P 3
P 1

Nguồn

Đề gốc IOI 2003. Bảng tổng quan ngày 1.