IOI 2010 - Ngày 1

Tiến sĩ Black đã bị sát hại. Thám tử Jill cần xác định thủ phạm, địa điểm và hung khí. Có 6 nghi phạm được đánh số từ 1 đến 6, 10 địa điểm được đánh số từ 1 đến 10 và 6 hung khí được đánh số từ 1 đến 6.

Jill liên tục đưa ra một bộ phỏng đoán gồm thủ phạm, địa điểm và hung khí. Mỗi bộ như vậy được gọi là một giả thuyết. Trợ lý Jack sẽ xác nhận hoặc bác bỏ từng giả thuyết. Nếu giả thuyết đúng, Jill hoàn tất công việc. Nếu giả thuyết sai, Jack chỉ ra rằng một trong ba thành phần thủ phạm, địa điểm hoặc hung khí không đúng.

Bạn cần cài đặt hàm Solve đóng vai Jill. Bộ chấm gọi Solve nhiều lần, mỗi lần với một vụ án mới. Trong mỗi lần gọi, Solve phải gọi hàm Theory(M, L, W) do bộ chấm cung cấp:

• M là số hiệu nghi phạm, 1 <= M <= 6;
• L là số hiệu địa điểm, 1 <= L <= 10;
• W là số hiệu hung khí, 1 <= W <= 6.

Theory(M, L, W) trả về:

• 0 nếu cả ba thành phần đều đúng;
• 1 nếu thủ phạm sai;
• 2 nếu địa điểm sai;
• 3 nếu hung khí sai.

Nếu có nhiều thành phần sai, Jack có thể tùy ý chọn một thành phần sai để báo lại; lựa chọn này không nhất thiết giống nhau giữa các lần gọi. Ngay khi Theory trả về 0, hàm Solve phải kết thúc.

Ví dụ

Giả sử thủ phạm là 2, địa điểm là 3 và hung khí là 4. Một chuỗi lời gọi hợp lệ có thể là:

Các nhóm điểm

Trong mỗi lượt chấm, Solve có thể được gọi tối đa 100 lần với các đáp án khác nhau. Mọi biến trạng thái dùng trong Solve phải được khởi tạo lại cho từng lần gọi.

Chi tiết cài đặt

Bạn cần nộp một tệp C++ cài đặt hàm sau:

void Solve();

Tệp của bạn được biên dịch cùng cluedo.h. Tệp tiêu đề khai báo hàm do bộ chấm cung cấp:

int Theory(int M, int L, int W);

Chương trình của bạn không được định nghĩa hàm main.

Jack và Jill chơi trò Nóng hơn, Lạnh hơn. Jill bí mật chọn một số nguyên từ 1 đến N, còn Jack liên tục đoán số đó.

Mỗi giá trị Jack đoán phải nằm trong đoạn từ 1 đến N. Với lần đoán đầu tiên, Jill luôn trả lời bằng nhau. Từ lần đoán thứ hai trở đi, Jill trả lời:

• nóng hơn nếu lần đoán hiện tại gần số bí mật hơn lần đoán trước;
• lạnh hơn nếu lần đoán hiện tại xa số bí mật hơn lần đoán trước;
• bằng nhau nếu hai khoảng cách bằng nhau.

Bạn cần cài đặt hàm HC(N) đóng vai Jack. Hàm này có thể gọi Guess(G) nhiều lần, với 1 <= G <= N. Hàm Guess trả về 1, -1 hoặc 0, lần lượt tương ứng với nóng hơn, lạnh hơn và bằng nhau. Hàm HC phải trả về đúng số Jill đã chọn.

Ví dụ

Giả sử N = 5 và Jill chọn số 2:

Sau các lời gọi trên, HC phải trả về 2.

Các nhóm điểm

Trong nhóm 4, gọi W là số nguyên lớn nhất thỏa mãn

Với mỗi lần gọi HC, đặt q là số lần gọi Guess. Điểm của nhóm được xác định bởi trường hợp tệ nhất:

• 0 điểm nếu q >= 2W;
• \(25\alpha\) điểm nếu \(0 < \alpha < 1\) là giá trị lớn nhất sao cho \(q \le 2W - \alpha W\);
• 25 điểm nếu q <= W.

Mọi biến trạng thái của HC phải được khởi tạo lại cho từng lần gọi.

Chi tiết cài đặt

Bạn cần nộp một tệp C++ cài đặt:

int HC(int N);

Tệp của bạn được biên dịch cùng hottercolder.h, trong đó có khai báo:

int Guess(int G);

Chương trình của bạn không được định nghĩa hàm main.

Các thành phố ở Alberta thường được quy hoạch thành một lưới chữ nhật gồm nhiều khu phố. Hàng được đánh số từ 0 đến R - 1 theo hướng bắc xuống nam, còn cột được đánh số từ 0 đến C - 1 theo hướng tây sang đông.

Mỗi khu phố có một hạng chất lượng sống riêng biệt từ 1 đến R * C; hạng 1 là tốt nhất và hạng R * C là tệ nhất.

Sở quy hoạch muốn chọn một hình chữ nhật gồm H hàng và W cột sao cho trung vị của các hạng chất lượng trong hình chữ nhật là tốt nhất, tức nhỏ nhất có thể. H và W đều là số lẻ, lần lượt không vượt quá R và C.

Với một tập có số phần tử lẻ, trung vị là phần tử m sao cho số phần tử tốt hơn m bằng số phần tử tệ hơn m.

Bạn cần cài đặt hàm rectangle(R, C, H, W, Q). Trong đó Q[a][b] là hạng chất lượng của khu phố ở hàng a, cột b. Hàm phải trả về trung vị nhỏ nhất có thể trong mọi hình chữ nhật kích thước H nhân W.

Bộ chấm chỉ gọi rectangle một lần trong mỗi test.

Ví dụ 1

Với R = C = 5, H = W = 3 và

5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15

Hình chữ nhật 3 nhân 3 ở giữa bên phải có trung vị 9, và không có hình chữ nhật hợp lệ nào có trung vị tốt hơn. Do đó hàm trả về 9.

Ví dụ 2

Với R = 2, C = 6, H = 1, W = 5 và

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

Đáp án là 5.

Các nhóm điểm

Trong mọi nhóm, 1 <= H <= R, 1 <= W <= C, H và W là số lẻ, và Q là một hoán vị của các số từ 1 đến R * C.

Chi tiết cài đặt

Bạn cần nộp một tệp C++ cài đặt:

int rectangle(int R, int C, int H, int W, int Q[3001][3001]);

Tệp của bạn được biên dịch cùng quality.h. Chương trình của bạn không được định nghĩa hàm main.

Bạn cần viết một chương trình tương tác để lần lượt đoán ngôn ngữ của 10000 đoạn trích Wikipedia. Sau mỗi lần đoán, chương trình được biết đáp án đúng và có thể dùng thông tin đó để cải thiện các lần đoán tiếp theo.

Mỗi ngôn ngữ được biểu diễn bởi một số nguyên L từ 0 đến 55. Mỗi đoạn trích có đúng 100 ký hiệu, được biểu diễn bằng mảng E gồm 100 số nguyên từ 1 đến 65535. Các mã ký hiệu này được gán ngẫu nhiên và không tương ứng với bất kỳ bảng mã chuẩn nào.

Bạn cần cài đặt hàm excerpt(E). Trong đúng một lần gọi hàm này, chương trình phải gọi language(L) đúng một lần để đưa ra dự đoán. Bộ chấm trả về ngôn ngữ thật của đoạn trích; dự đoán đúng khi giá trị trả về bằng L.

Độ chính xác \(\alpha\) là tỉ lệ trong 10000 đoạn trích mà chương trình đoán đúng.

Bạn có thể sử dụng bất kỳ phương pháp nào. Chẳng hạn, phương pháp Rocchio so sánh tập ký hiệu phân biệt trong đoạn hiện tại với các ký hiệu đã xuất hiện ở từng ngôn ngữ trước đó và đạt độ chính xác xấp xỉ 0.4.

Dữ liệu được lấy từ các bài viết Wikipedia thật nên có thể chứa một số ký tự hỏng hoặc mảnh văn bản bất thường. Đây là một phần bình thường của dữ liệu.

Dữ liệu chấm

56 ngôn ngữ là các ngôn ngữ mẹ đẻ được khai báo trong dữ liệu đăng ký IOI 2010. Mỗi đoạn trích được chọn ngẫu nhiên từ đoạn đầu của một bài viết thuộc một trong 56 phiên bản Wikipedia.

Dữ liệu mẫu chính thức đi kèm gồm mã ISO hai ký tự, 100 mã số và phần văn bản UTF-8 dễ đọc. Phần văn bản chỉ có tác dụng minh họa và không được truyền vào hàm của thí sinh. Tệp PDF tiếng Anh đính kèm chứa đầy đủ 56 ví dụ minh họa đa ngôn ngữ của đề gốc.

Dữ liệu chấm sử dụng 10000 đoạn khác được tạo theo cùng quy trình. Bộ chấm gán lại độc lập các số từ 0 đến 55 cho ngôn ngữ và các số từ 1 đến 65535 cho ký hiệu, vì vậy không thể mã hóa sẵn kiến thức về một ngôn ngữ cụ thể.

Các nhóm điểm

Đề IOI 2010 gốc cho phép tổng điểm thưởng tối đa là 110. Trên LQDOJ, điểm của bài được chuẩn hóa về 100: 30 điểm đầu được giữ nguyên, còn phần thưởng của nhóm 2 được giữ nguyên công thức đến 70 điểm và được chặn tại đó.

Chi tiết cài đặt

Bạn cần nộp một tệp C++ cài đặt:

void excerpt(int E[100]);

Tệp của bạn được biên dịch cùng language.h, trong đó có khai báo:

int language(int L);

Trong mỗi lần gọi excerpt, bạn phải gọi language đúng một lần. Chương trình của bạn không được định nghĩa hàm main.