IOI 2000 - Ngày 1

Một xâu đối xứng là xâu đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Cho một xâu, hãy xác định số ký tự ít nhất cần chèn vào xâu để thu được một xâu đối xứng.

Ví dụ, bằng cách chèn \(2\) ký tự, xâu Ab3bd có thể trở thành xâu đối xứng dAb3bAd hoặc Adb3bdA. Không thể thu được xâu đối xứng bằng cách chèn ít hơn \(2\) ký tự.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\), độ dài xâu, với \(3 \le N \le 5000\). Dòng thứ hai chứa xâu có đúng \(N\) ký tự. Mỗi ký tự là chữ cái in hoa từ A đến Z, chữ cái thường từ a đến z, hoặc chữ số từ 0 đến 9. Chữ hoa và chữ thường được xem là khác nhau.

Dữ liệu ra

In một số nguyên là số ký tự ít nhất cần chèn.

Ví dụ

5
Ab3bd

2

Một bãi đỗ xe gần Vạn Lý Trường Thành có một hàng dài các chỗ đỗ, với một đầu được gọi là bên trái và đầu kia là bên phải. Tất cả các chỗ đều có xe. Mỗi xe thuộc một loại được biểu diễn bằng một số nguyên; nhiều xe có thể cùng loại. Các công nhân muốn sắp xếp xe theo thứ tự loại không giảm từ trái sang phải.

Việc sắp xếp được thực hiện qua các lượt. Trong một lượt, mỗi công nhân có thể đồng thời lái một xe ra khỏi chỗ đỗ, rồi đỗ xe đó vào một chỗ mà một xe đã rời đi trong chính lượt ấy. Một số công nhân có thể không di chuyển xe trong một lượt. Để làm việc hiệu quả, số lượt nên nhỏ.

Gọi \(N\) là số xe và \(W\) là số công nhân. Cho các loại xe theo thứ tự ban đầu và số công nhân, hãy tìm cách sắp xếp sử dụng không quá \(\left\lceil N/(W-1)\right\rceil\) lượt, tức là \(N/(W-1)\) làm tròn lên. Số lượt ít nhất cần thiết không bao giờ vượt quá giới hạn này.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(N\), \(M\), \(W\): số xe, số loại xe và số công nhân. Các giới hạn là \(2 \le N \le 20000\), \(2 \le M \le 50\) và \(2 \le W \le M\). Các loại được đánh số từ \(1\) đến \(M\), và mỗi loại có ít nhất một xe.

Dòng thứ hai chứa \(N\) số nguyên; số thứ \(i\) là loại của xe ở vị trí thứ \(i\) tính từ trái sang phải.

Dữ liệu ra

Dòng đầu chứa số nguyên \(R\), số lượt trong phương án. Tiếp theo là \(R\) dòng mô tả các lượt từ \(1\) đến \(R\). Mỗi dòng bắt đầu bằng số xe \(C\) được di chuyển trong lượt đó, tiếp theo là \(2C\) số nguyên chia thành \(C\) cặp. Mỗi cặp mô tả một xe: số đầu là vị trí trước lượt di chuyển, số sau là vị trí sau lượt di chuyển. Các vị trí được đánh số từ \(1\) đến \(N\) từ trái sang phải. Chỉ cần in một phương án hợp lệ nếu có nhiều phương án.

Chấm điểm

Đặt \(Q=\left\lceil N/(W-1)\right\rceil\). Nếu mô tả \(R\) lượt không hợp lệ hoặc không đưa các xe về đúng thứ tự yêu cầu, điểm của lần chạy đó là \(0\). Ngược lại, điểm được tính theo tỷ lệ của điểm tối đa cho lần chạy:

Ví dụ

10 4 4
2 3 3 4 4 2 1 1 3 1

3
4 2 7 3 8 7 2 8 3
3 4 9 9 6 6 4
3 1 5 5 10 10 1

2 1 1 4 4 2 3 3 3 1
2 1 1 2 4 3 3 3 4 1
1 1 1 2 2 3 3 3 4 4

Một thí nghiệm không gian mới sử dụng \(N\) vật thể, được gắn nhãn từ \(1\) đến \(N\), trong đó \(N\) là số lẻ. Mỗi vật thể có một độ mạnh là số nguyên dương chưa biết, nằm trong đoạn từ \(1\) đến \(N\). Độ mạnh của các vật thể đôi một khác nhau. Vật thể có độ mạnh trung vị là vật thể mà số vật thể có độ mạnh nhỏ hơn nó bằng số vật thể có độ mạnh lớn hơn nó.

Hãy viết chương trình xác định nhãn của vật thể có độ mạnh trung vị. Cách duy nhất để so sánh độ mạnh là dùng một thiết bị: với ba vật thể khác nhau, thiết bị cho biết vật thể có độ mạnh trung vị trong ba vật thể đó.

Giao diện thư viện

Bạn nộp một chương trình C++ hoàn chỉnh có hàm int main(), dùng #include "device.h" và gọi các hàm dưới đây. Không tự cài đặt các hàm của thư viện device.

Chương trình sử dụng thư viện device cung cấp ba thao tác:

• GetN: gọi đúng một lần ở đầu chương trình, không có tham số, trả về \(N\).
• Med3(x, y, z): nhận nhãn của ba vật thể đôi một khác nhau, trả về nhãn của vật thể có độ mạnh ở giữa trong ba vật thể đó.
• Answer(m): gọi đúng một lần ở cuối chương trình để báo nhãn \(m\) của vật thể có độ mạnh trung vị trong toàn bộ \(N\) vật thể. Lời gọi này kết thúc chương trình.

Với C/C++, dùng #include "device.h". Các khai báo là:

int GetN(void);
int Med3(int x, int y, int z);
void Answer(int m);

Với Pascal, dùng uses device;. Các khai báo là:

function GetN: integer;
function Med3(x, y, z: integer): integer;
procedure Answer(m: integer);

Giới hạn

Có \(5 \le N \le 1499\) và \(N\) lẻ. Mọi nhãn \(i\) thỏa mãn \(1 \le i \le N\). Mọi độ mạnh \(Y\) thỏa mãn \(1 \le Y \le N\), và các độ mạnh đôi một khác nhau. Trong mỗi lần chạy, chương trình được gọi Med3 không quá \(7777\) lần. Chương trình không được đọc hoặc ghi bất kỳ tệp nào; mọi trao đổi với thiết bị phải thông qua ba thao tác của thư viện.

Thử nghiệm cục bộ

Trong giao diện thử nghiệm của đề gốc, bạn tự tạo tệp DEVICE.IN gồm đúng hai dòng: dòng đầu chứa \(N\); dòng thứ hai chứa một hoán vị của các số từ \(1\) đến \(N\), trong đó số thứ \(i\) là độ mạnh của vật thể mang nhãn \(i\). Thư viện ghi hai tệp: dòng đầu của MEDIAN.OUT là nhãn được truyền cho Answer, dòng thứ hai là số lần chương trình đã gọi Med3; MEDIAN.LOG ghi lại cuộc trao đổi giữa chương trình và thư viện.

Tệp đính kèm median-template.zip cung cấp device.h, khung chương trình template.cpp, mã kết nối device_stub.cpp và trình thử local_test.py. Trình thử đọc DEVICE.IN do bạn chọn, trả lời các lời gọi thư viện và tạo MEDIAN.OUT, MEDIAN.LOG theo ý nghĩa trên. Xem README.md trong tệp ZIP để biên dịch và chạy thử. Chỉ ghép device_stub.cpp vào chương trình khi chạy thử trên máy của bạn; khi nộp bài, chỉ nộp mã C++ của bạn có hàm main, hệ thống sẽ cung cấp các hàm thư viện. Không đưa độ mạnh của các vật thể vào mã nộp bài và không đọc trực tiếp DEVICE.IN từ chương trình. Mã kết nối không tự mô phỏng thiết bị: cần chạy chương trình thông qua local_test.py, không chuyển thẳng nội dung DEVICE.IN vào đầu vào chuẩn của chương trình.

Ví dụ

Dữ liệu mô tả thiết bị gồm hai dòng: dòng đầu là \(N\), dòng thứ hai là một hoán vị của các số từ \(1\) đến \(N\), trong đó số thứ \(i\) là độ mạnh của vật thể mang nhãn \(i\). Đây là dữ liệu của thiết bị, không phải dữ liệu để chương trình của bạn đọc trực tiếp.

5
2 5 4 3 1

GetN() -> 5
Med3(1, 2, 3) -> 3
Med3(3, 4, 1) -> 4
Med3(4, 2, 5) -> 4
Answer(4)