IOI 2005 - Ngày 2

Hôm nay là sinh nhật của Byteman. Có \(n\) bạn nhỏ tham dự bữa tiệc, kể cả Byteman, được đánh số từ \(1\) đến \(n\). Bố mẹ Byteman đã chuẩn bị một chiếc bàn tròn lớn và đặt \(n\) chiếc ghế xung quanh. Khi đến dự tiệc, các bạn lần lượt ngồi xuống: bạn số \(1\) chọn một ghế, bạn số \(2\) ngồi vào ghế bên trái bạn số \(1\), bạn số \(3\) ngồi vào ghế tiếp theo bên trái, và cứ như vậy. Cuối cùng, bạn số \(n\) ngồi vào chiếc ghế trống còn lại, giữa bạn số \(1\) và bạn số \(n-1\).

Bố mẹ Byteman hiểu rất rõ các bạn nhỏ và biết rằng một số bạn sẽ gây ồn ào nếu ngồi quá gần nhau. Vì vậy, họ muốn sắp xếp lại chỗ ngồi theo một thứ tự nhất định. Thứ tự đó được mô tả bằng một hoán vị \(p_1,p_2,\ldots,p_n\) của các số từ \(1\) đến \(n\): bạn \(p_1\) phải ngồi giữa \(p_n\) và \(p_2\); bạn \(p_i\), với \(i=2,3,\ldots,n-1\), phải ngồi giữa \(p_{i-1}\) và \(p_{i+1}\); còn bạn \(p_n\) phải ngồi giữa \(p_{n-1}\) và \(p_1\). Lưu ý rằng bạn \(p_1\) có thể ngồi bên trái hoặc bên phải bạn \(p_n\).

Để đưa các bạn về đúng thứ tự, bố mẹ Byteman phải cho mỗi bạn di chuyển quanh bàn sang trái hoặc sang phải một số ghế. Với từng bạn, họ phải chọn cả hướng di chuyển và khoảng cách di chuyển, tính bằng số ghế. Khi có hiệu lệnh, tất cả các bạn cùng đứng dậy, di chuyển đến vị trí của mình rồi ngồi xuống.

Việc đổi chỗ làm bữa tiệc trở nên lộn xộn. Mức độ lộn xộn bằng khoảng cách lớn nhất mà một bạn phải di chuyển. Có nhiều cách sắp xếp lại chỗ ngồi, và bố mẹ Byteman muốn chọn cách có mức độ lộn xộn nhỏ nhất.

Cho số bạn nhỏ và hoán vị mô tả thứ tự mong muốn, hãy viết chương trình tìm mức độ lộn xộn nhỏ nhất có thể.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa một số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(p_1,p_2,\ldots,p_n\), cách nhau bởi một dấu cách. Các số này tạo thành một hoán vị của tập \(\{1,2,\ldots,n\}\), mô tả thứ tự chỗ ngồi mong muốn.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: mức độ lộn xộn nhỏ nhất có thể.

Ràng buộc

• \(1 \le n \le 1\,000\,000\).
• \(1 \le p_i \le n\) với \(1 \le i \le n\); các giá trị \(p_i\) đôi một khác nhau.

Phân nhóm

Trong \(50\%\) số bộ dữ liệu kiểm tra, \(n\) không vượt quá \(1\,000\).

Ví dụ

6
3 4 5 1 2 6

2

Nguồn

IOI 2005, ngày thi thứ hai: Birthday, bản tiếng Anh 1.02. Tác giả đề bài: Jakub Pawlewicz. Tập đề bài và lời giải IOI 2005.

Hai người chơi một trò chơi với một hình chữ nhật kích thước \(x \times y\), trong đó \(x\) và \(y\) là các số nguyên dương. Hai người luân phiên thực hiện nước đi. Mỗi nước đi là một nhát cắt dọc hoặc ngang, chia hình chữ nhật thành hai hình chữ nhật có các kích thước nguyên dương.

Hình vẽ minh họa các nhát cắt có thể thực hiện trên một hình chữ nhật \(4 \times 3\).

Sau mỗi nhát cắt, hình chữ nhật có diện tích nhỏ hơn bị bỏ đi, còn hình chữ nhật kia được chuyển cho đối thủ. Nếu hai phần có diện tích bằng nhau, một phần bị bỏ đi. Người nhận được hình chữ nhật \(1 \times 1\) không thể thực hiện nước đi và thua cuộc.

Hãy viết chương trình chơi và thắng trò chơi này. Chương trình phải dùng thư viện được cung cấp để biết kích thước hình chữ nhật và thực hiện các nước đi.

Giao tiếp

Mỗi lần chạy, chương trình của bạn đóng vai một người chơi trong đúng một ván đấu. Bạn đi trước và phải cắt hình chữ nhật ban đầu. Hai hàm dimension_x() và dimension_y() trả về kích thước hiện tại của hình chữ nhật theo hai chiều.

Để thực hiện một nước đi, gọi thủ tục cut(dir, position). Tham số dir chỉ hướng cắt, còn position chỉ vị trí cắt:

• dir phải là một trong hai giá trị vertical hoặc horizontal.
• Nếu dir = vertical, nhát cắt là nhát cắt dọc và position là hoành độ của đường cắt. Phải bảo đảm \(1 \le \texttt{position} \le \texttt{dimension\_x()}-1\).
• Nếu dir = horizontal, nhát cắt là nhát cắt ngang và position là tung độ của đường cắt. Phải bảo đảm \(1 \le \texttt{position} \le \texttt{dimension\_y()}-1\).

Khi chương trình gọi cut, nước đi của bạn được ghi nhận và quyền điều khiển được chuyển cho đối thủ. Sau khi đối thủ thực hiện nước đi, quyền điều khiển mới trở lại chương trình của bạn. Khi đó, các giá trị trả về bởi dimension_x() và dimension_y() phản ánh kết quả của cả nước đi của bạn lẫn nước đi của đối thủ.

Ngay khi bạn thắng, thua hoặc thực hiện một nước đi không hợp lệ, tức gọi cut với tham số không hợp lệ, chương trình sẽ bị kết thúc tự động. Vì việc kết thúc do thư viện đảm nhiệm, chương trình của bạn phải tiếp tục thực hiện nước đi chừng nào còn có thể. Dữ liệu kiểm tra bảo đảm luôn tồn tại một chiến lược thắng cho chương trình của bạn từ vị trí ban đầu.

Chương trình của bạn không được đọc hoặc ghi bất kỳ tệp nào, không được sử dụng đầu vào hay đầu ra chuẩn, và không được tìm cách sửa đổi vùng nhớ nằm ngoài chương trình của mình. Vi phạm các quy tắc này có thể dẫn đến bị loại. Mọi trao đổi trong ván đấu đều phải thông qua giao diện thư viện.

Giao diện thư viện

Bài này trên LQDOJ chấp nhận chương trình C hoặc C++. Bạn cần tự viết hàm main() và thêm #include "creclib.h". Tệp tiêu đề cung cấp giao diện:

typedef enum __direction {vertical, horizontal} direction;
int dimension_x(void);
int dimension_y(void);
void cut(direction dir, int position);

Hệ thống sẽ biên dịch chương trình của bạn cùng thư viện handler.c và tệp tiêu đề creclib.h. Chỉ nộp mã nguồn chương trình của bạn; không nộp lại thư viện và không tự cài đặt ba hàm trên. Giao diện này dùng được trong cả C và C++.

Tệp đính kèm templates.zip chứa creclib.h, handler.c, tài liệu của thư viện và mã nguồn đối thủ mẫu Pascal được mô tả dưới đây. Thư viện C/C++ dùng khi chấm tự trao đổi với đối thủ của hệ thống; chương trình của bạn chỉ gọi các hàm đã công bố.

Thư viện đối thủ mẫu

Tệp test_preclib.pas trong bộ đính kèm là mã nguồn thư viện đối thủ mẫu Pascal của kỳ thi gốc, chỉ được cung cấp để tham khảo và thử nghiệm riêng. Đối thủ mẫu sử dụng một chiến lược rất đơn giản, không phải đối thủ dùng để chấm bài trên LQDOJ. Giao diện Pascal tương ứng là:

type direction = (vertical, horizontal);
function dimension_x(): longint;
function dimension_y(): longint;
procedure cut(dir: direction; position: longint);

Trong chương trình thử nghiệm Pascal, khai báo uses preclib;. Bạn có thể sửa phần cài đặt của đối thủ mẫu để thử một chiến lược mạnh hơn, nhưng không được thay đổi giao diện. Khi sử dụng Pascal để thử nghiệm riêng, cần biên dịch lại thư viện để tạo các tệp preclib.o và preclib.ppu, rồi đặt chúng cùng thư mục với mã nguồn chương trình.

Thư viện đối thủ mẫu nhận kích thước ban đầu từ hai dòng, mỗi dòng chứa một số nguyên: dòng thứ nhất là chiều rộng, dòng thứ hai là chiều cao. Chính thư viện mẫu đọc các số này; chương trình người chơi không được tự đọc đầu vào chuẩn.

Khi chấm bài, chương trình của bạn đấu với một đối thủ khác, không phải đối thủ đơn giản trong thư viện mẫu. Đối thủ dùng để chấm chơi tối ưu. Đối thủ mẫu không phải là một lời giải đúng cho bài toán.

Ràng buộc

• Hai kích thước ban đầu là các số nguyên trong khoảng từ \(1\) đến \(100\,000\,000\).
• Ít nhất một trong hai kích thước ban đầu lớn hơn \(1\).
• Vị trí ban đầu luôn có chiến lược thắng cho người đi trước.

Phân nhóm

Trong \(50\%\) số bộ dữ liệu kiểm tra, cả hai kích thước ban đầu đều không vượt quá \(25\).

Ví dụ

Nguồn

IOI 2005, ngày thi thứ hai: Rectangle Game, bản tiếng Anh 1.04. Tác giả đề bài: Jakub Radoszewski và Marcin Kubica. Tập đề bài và lời giải IOI 2005. Mô tả dữ liệu chấm chính thức.

Gần như toàn bộ vương quốc Byteland được bao phủ bởi rừng và sông. Các con sông nhỏ hợp lại thành những con sông lớn hơn; những con sông này lại tiếp tục hợp dòng, cho đến khi tất cả cùng chảy vào một con sông lớn. Con sông lớn đổ ra biển gần Bytetown.

Byteland có \(n\) ngôi làng của những người đốn gỗ, mỗi làng nằm gần một con sông. Hiện tại, Bytetown có một xưởng cưa lớn xử lý toàn bộ cây gỗ được chặt trong vương quốc. Các cây gỗ được thả trôi từ các làng theo dòng sông đến xưởng cưa ở Bytetown. Nhà vua quyết định xây thêm \(k\) xưởng cưa tại các làng để giảm chi phí vận chuyển gỗ xuôi dòng. Sau khi xây các xưởng cưa, gỗ không cần trôi tới Bytetown mà có thể được xử lý tại xưởng cưa đầu tiên gặp trên đường xuôi dòng. Gỗ được chặt gần một làng có xưởng cưa không cần vận chuyển bằng đường sông. Các con sông ở Byteland không phân nhánh theo chiều dòng chảy, nên từ mỗi làng chỉ có đúng một đường xuôi dòng tới Bytetown.

Các kế toán của nhà vua đã tính được số cây gỗ được chặt hằng năm ở mỗi làng. Bạn phải quyết định vị trí xây các xưởng cưa để tổng chi phí vận chuyển gỗ trong một năm nhỏ nhất. Chi phí vận chuyển bằng đường sông là một xu cho mỗi kilômét, đối với mỗi cây gỗ.

Cho số làng, số xưởng cưa cần xây thêm, số cây gỗ được chặt gần mỗi làng và mô tả các dòng sông, hãy viết chương trình tính chi phí vận chuyển nhỏ nhất sau khi xây thêm các xưởng cưa.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(n\) và \(k\): số làng không kể Bytetown và số xưởng cưa cần xây thêm. Các làng được đánh số từ \(1\) đến \(n\); Bytetown mang số \(0\).
• Mỗi dòng trong \(n\) dòng tiếp theo chứa ba số nguyên cách nhau bởi một dấu cách. Dòng thứ \(i+1\) chứa \(w_i\), \(v_i\), \(d_i\), theo thứ tự này.

Trong đó, \(w_i\) là số cây gỗ được chặt gần làng \(i\) mỗi năm; \(v_i\) là ngôi làng đầu tiên, hoặc Bytetown, gặp khi đi xuôi dòng từ làng \(i\); còn \(d_i\) là khoảng cách theo đường sông từ làng \(i\) đến \(v_i\), tính bằng kilômét.

Dữ liệu bảo đảm rằng tổng chi phí thả trôi toàn bộ số cây gỗ được chặt trong một năm tới xưởng cưa ở Bytetown không vượt quá \(2\,000\,000\,000\) xu.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: chi phí vận chuyển gỗ bằng đường sông nhỏ nhất trong một năm, tính bằng xu.

Ràng buộc

• \(2 \le n \le 100\).
• \(1 \le k \le 50\) và \(k \le n\).
• \(0 \le w_i \le 10\,000\) với \(1 \le i \le n\).
• \(0 \le v_i \le n\) với \(1 \le i \le n\).
• \(1 \le d_i \le 10\,000\) với \(1 \le i \le n\).

Phân nhóm

Trong \(50\%\) số bộ dữ liệu kiểm tra, \(n\) không vượt quá \(20\).

Ví dụ

4 2
1 0 1
1 1 10
10 2 5
1 2 3

4

Nguồn

IOI 2005, ngày thi thứ hai: Rivers, bản tiếng Anh 1.04. Tác giả đề bài: Łukasz Kowalik. Tập đề bài và lời giải IOI 2005.