| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | IOI 2003 - Trail Maintenance | 100 (p) | 1.0s | 64M |
| 2 | IOI 2003 - Comparing Code | 100 (p) | 2.0s | 64M |
| 3 | IOI 2003 - Reverse | 100 (p) | 3.0s | 256M |
Những con bò của nông dân John muốn đi lại tự do giữa \(N\) cánh đồng, được đánh số từ \(1\) đến \(N\), trong trang trại. Các cánh đồng bị ngăn cách bởi rừng. Đàn bò muốn bảo dưỡng một số đường mòn nối các cặp cánh đồng để từ bất kỳ cánh đồng nào cũng có thể đi đến mọi cánh đồng khác. Mỗi đường mòn được đi theo cả hai chiều.
Đàn bò không xây đường mới mà chỉ bảo dưỡng những đường mòn của thú rừng đã tìm thấy. Vốn tò mò, đầu mỗi tuần chúng lại phát hiện thêm đúng một đường mòn. Trong tuần đó, chúng chỉ có thể đi trên các đường đang được bảo dưỡng. Chúng được chọn lại bất kỳ tập con nào của tất cả các đường đã biết, không phụ thuộc vào những đường được bảo dưỡng ở tuần trước.
Mục tiêu mỗi tuần là làm cho các cánh đồng liên thông với tổng độ dài đường phải bảo dưỡng nhỏ nhất. Các đường mòn của thú rừng không bao giờ thẳng, kể cả khi được bảo dưỡng; nhiều đường có thể nối cùng một cặp cánh đồng và có độ dài khác nhau. Dù các đường có thể giao nhau, đàn bò vẫn nhất quyết chỉ đổi từ đường này sang đường khác tại một cánh đồng.
Đây là bài tương tác. Sau khi nhận thông tin về đường mới của một tuần, chương trình phải trả lời ngay cho tuần đó trước khi đọc đường mới của tuần tiếp theo.
Ngay sau khi nhận đường mòn mới, ghi ra đầu ra chuẩn một dòng chứa tổng độ dài nhỏ nhất cần bảo dưỡng để đi được giữa mọi cặp cánh đồng. Nếu chưa thể làm được điều đó, ghi -1.
Đẩy hết dữ liệu trong bộ đệm đầu ra sau mỗi câu trả lời. Kết thúc chương trình sau câu trả lời cho tuần cuối cùng.
Giới hạn thời gian: 1 giây CPU. Giới hạn bộ nhớ: 64 MiB.
Có 20 bộ dữ liệu, mỗi bộ tối đa 5 điểm. Một bộ dữ liệu chỉ được điểm khi chương trình trả lời đúng tất cả các tuần; không có điểm thành phần trong một bộ dữ liệu.
Ví dụ tương tác
4 6
1 2 10
1 3 8
3 2 3
1 4 3
1 3 6
2 1 2-1
-1
-1
14
12
8Các dòng được trao đổi luân phiên: sau mỗi đường mòn mới, chương trình phải ghi câu trả lời tương ứng rồi mới nhận đường tiếp theo. Trong ba tuần đầu, cánh đồng 4 chưa nối được với các cánh đồng khác.
Tuần 4 có thể bảo dưỡng các đường (1,4,3), (1,3,8), (3,2,3), tổng độ dài 14. Tuần 5 chọn (1,4,3), (1,3,6), (3,2,3), tổng 12. Tuần 6 chọn (1,4,3), (2,1,2), (3,2,3), tổng 8. Sau câu trả lời cuối, chương trình kết thúc.
Công ty Racine Business Networks (RBN) kiện công ty Heuristic Algorithm Languages (HAL), cho rằng HAL đã lấy mã nguồn của RBN UNIX và đưa vào hệ điều hành mã nguồn mở HALnix.
Cả hai công ty đều dùng một ngôn ngữ lập trình có đúng một câu lệnh trên mỗi dòng, theo dạng STOREA = STOREB + STOREC. Tên biến đầu tiên bắt đầu ở cột đầu tiên; giữa tên biến và mỗi ký hiệu =, + có đúng một dấu cách. Một biến có thể xuất hiện nhiều lần trên cùng một dòng. Tên biến gồm từ 1 đến 8 chữ cái ASCII in hoa từ A đến Z.
RBN cho rằng HAL đã sao chép một đoạn gồm các dòng liên tiếp trong chương trình của RBN và chỉ thực hiện những thay đổi sau:
STOREA = STOREB + STOREC có thể trở thành STOREA = STOREC + STOREB.Cho mã nguồn của cả RBN và HAL, hãy tìm độ dài lớn nhất của một đoạn gồm các dòng liên tiếp trong chương trình HAL có thể thu được từ một đoạn gồm các dòng liên tiếp trong chương trình RBN bằng những thay đổi trên. Hai đoạn không nhất thiết bắt đầu tại cùng một số dòng.
Trong bản luyện tập, đọc dữ liệu từ đầu vào chuẩn. Tệp đầu vào trong đề gốc có tên code.in.
Ghi ra đầu ra chuẩn một số nguyên trên một dòng: độ dài lớn nhất của đoạn liên tiếp mà HAL có thể đã sao chép và biến đổi từ RBN. Tệp đầu ra trong đề gốc có tên code.out.
Giới hạn thời gian: 2 giây CPU. Giới hạn bộ nhớ: 64 MiB.
Có 20 bộ dữ liệu, mỗi bộ tối đa 5 điểm. Mỗi bộ chỉ được điểm khi kết quả đúng; không có điểm thành phần trong một bộ dữ liệu.
Ví dụ 1
4 3
RA = RB + RC
RC = D + RE
RF = RF + RJ
RE = RF + RF
HD = HE + HF
HM = HN + D
HN = HA + HB2Dòng 1–2 của RBN tương ứng với dòng 2–3 của HAL khi đổi tên RA thành HM, RB thành D, RC thành HN, D thành HA, RE thành HB. Không có hai đoạn tương ứng dài từ 3 dòng trở lên.
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:
| Lệnh | Ý nghĩa |
|---|---|
S i j |
Gán cho thanh ghi \(j\) giá trị của thanh ghi \(i\) cộng một. Có thể có \(i=j\). |
P i |
In giá trị của thanh ghi \(i\). |
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ó.
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:
| Số bộ dữ liệu \(K\) | Tệp đầu vào trong gói đính kèm | Tệp kết quả trong ZIP nộp |
|---|---|---|
| 1 | reverse1.in |
reverse.0.out |
| 2 | reverse2.in |
reverse.1.out |
| 3 | reverse3.in |
reverse.2.out |
| 4 | reverse4.in |
reverse.3.out |
| 5 | reverse5.in |
reverse.4.out |
| 6 | reverse6.in |
reverse.5.out |
| 7 | reverse7.in |
reverse.6.out |
| 8 | reverse8.in |
reverse.7.out |
| 9 | reverse9.in |
reverse.8.out |
| 10 | reverse10.in |
reverse.9.out |
| 11 | reverse11.in |
reverse.10.out |
| 12 | reverse12.in |
reverse.11.out |
| 13 | reverse13.in |
reverse.12.out |
| 14 | reverse14.in |
reverse.13.out |
| 15 | reverse15.in |
reverse.14.out |
| 16 | reverse16.in |
reverse.15.out |
Nội dung mỗi tệp kết quả giữ nguyên định dạng của đề gốc:
FILE reverse K, trong đó \(K\) là số thứ tự của bộ dữ liệu. Không có ký tự # trước FILE.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.
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:
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\).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à:
| Độ chênh lệch \(d\) | Tỷ lệ điểm của bộ dữ liệu |
|---|---|
| \(d\le0\) | 100% |
| \(d=1\) | 80% |
| \(d=2\) | 60% |
| \(3\le d\le4\) | 50% |
| \(5\le d\le7\) | 40% |
| \(8\le d\le10\) | 30% |
| \(d\ge11\) | 20% |
Ví dụ 1
1
2FILE reverse 1
0 2 0 0 0 0 0 0 0
P 2
S 1 3
P 3
P 1FILE reverse 1
0 2 1 0 0 0 0 0 0
P 2
P 3
P 1Kết quả thứ nhất chỉ được một phần điểm. Ban đầu các thanh ghi là 0 2 0 0 0 0 0 0 0. Lệnh P 2 in 2 và không đổi thanh ghi. Lệnh S 1 3 làm các thanh ghi trở thành 0 2 1 0 0 0 0 0 0. Hai lệnh P 3, P 1 lần lượt in 1 và 0, không đổi các thanh ghi.
Kết quả thứ hai được toàn bộ điểm vì đã khởi tạo sẵn cả ba giá trị cần in và không dùng lệnh S nào.