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.