IOI 2010 - Ngày 2

Trò chơi Memory sử dụng 50 lá bài. Trên mỗi lá bài in một chữ cái từ A đến Y (mã ASCII từ 65 đến 89), mỗi chữ xuất hiện trên đúng hai lá bài. Các lá bài được xáo trộn và đặt úp trên bàn.

Jack lật ngửa hai lá bài để xem chữ trên đó. Với mỗi chữ trong 25 chữ cái, lần đầu tiên Jack lật ngửa đồng thời cả hai lá mang chữ ấy, mẹ sẽ cho Jack một viên kẹo. Ví dụ, lần đầu tiên Jack lật hai lá mang chữ M, Jack nhận được một viên kẹo. Sau đó, dù hai chữ có giống nhau hay không, cả hai lá đều được úp lại. Trò chơi tiếp tục đến khi Jack nhận đủ 25 viên kẹo, mỗi chữ một viên.

Yêu cầu cài đặt

Bạn phải cài đặt hàm sau, không viết main:

void play();

Gọi hàm do trình chấm cung cấp để lật bài:

char faceup(int C);

C là số hiệu lá bài, từ 1 đến 50. Lá bài này phải đang úp. Hàm trả về chữ in trên lá bài C. Sau mỗi hai lần gọi faceup, trình chấm tự động úp lại cả hai lá vừa lật. Chỉ được kết thúc play khi Jack đã nhận đủ 25 viên kẹo. Bạn được phép tiếp tục gọi faceup sau khi Jack nhận viên kẹo cuối cùng; các lần gọi đó vẫn được tính.

Dữ liệu vào

Đây là bài chấm qua giao diện hàm; chương trình của bạn không đọc dữ liệu vào. Trình chấm mẫu chính thức đọc một dòng gồm 50 ký tự, lần lượt là chữ trên các lá bài từ 1 đến 50.

Dữ liệu ra

Chương trình của bạn không ghi dữ liệu ra; hãy tương tác qua faceup. Khi lời giải đúng, trình chấm mẫu chính thức ghi OK n, trong đó n là số lần gọi faceup.

Ràng buộc

Có đúng 50 lá bài; mỗi chữ từ A đến Y xuất hiện đúng hai lần. Mỗi lượt phải lật hai lá khác nhau. Một cặp đã từng đem lại kẹo sẽ không đem lại thêm kẹo.

Phân nhóm

Mốc số lần gọi được nêu trong nhóm 1 của đề gốc là:

Mỗi nhóm chỉ có điểm khi vượt qua toàn bộ các bộ kiểm tra của nhóm.

Ví dụ

Chi tiết triển khai

Gói LQDOJ nhận một tệp C++ cài đặt play, sử dụng memory.h (bao gồm khai báo faceup). Tệp mẫu được cung cấp trong templates.zip. Đề gốc hỗ trợ memory.c, memory.cpp hoặc memory.pas, dùng giao diện memory.h/memory.pas và grader.h/graderlib.pas, trong thư mục /home/ioi2010-contestant/memory/. Các lệnh runc grader.cpp, submit grader.cpp và phím Control-R/Control-J thuộc môi trường thi năm 2010; trên LQDOJ, nộp tệp lời giải qua giao diện nộp bài.

Nguồn

IOI 2010, ngày 2, bài 1 — Memory. Đề chính thức, PDF tiếng Anh.

Canada là một quốc gia rộng lớn, nhưng nhiều vùng không có người ở và phần lớn dân cư sống gần biên giới phía nam. Đường cao tốc xuyên Canada, hoàn thành năm 1962, nối St. John's ở phía đông với Victoria ở phía tây, dài 7821 km.

Người Canada yêu thích khúc côn cầu. Sau một trận đấu, hàng nghìn người hâm mộ lái xe về nhà, gây ùn tắc nghiêm trọng. Một doanh nhân giàu có muốn mua một đội khúc côn cầu và xây sân đấu mới. Hãy giúp ông chọn vị trí sân đấu để giảm ùn tắc sau trận đấu.

Các thành phố được nối bởi mạng lưới đường hai chiều. Giữa mỗi cặp thành phố có đúng một tuyến đường. Tuyến đường từ thành phố \(c_0\) đến \(c_k\) là một dãy các thành phố phân biệt \(c_0,\ldots,c_k\), trong đó có đường nối \(c_{i-1}\) với \(c_i\) với mọi \(1\le i\le k\).

Sân đấu phải được xây trong một thành phố. Sau trận đấu, mọi người hâm mộ đi từ thành phố có sân đấu về thành phố mình sinh sống, ngoại trừ những người đã sống tại thành phố có sân đấu. Mức ùn tắc trên một con đường tỷ lệ với số người đi qua đường đó. Hãy chọn thành phố sao cho mức ùn tắc trên con đường đông nhất nhỏ nhất có thể. Nếu có nhiều thành phố tốt như nhau, được chọn bất kỳ thành phố nào trong số đó.

Yêu cầu cài đặt

int LocateCentre(int N, int P[], int S[], int D[]);

N là số thành phố, được đánh số từ 0 đến N-1. Mảng P gồm N số nguyên dương; P[i] là số người hâm mộ sống tại thành phố i. Hai mảng S và D có N-1 phần tử: đường thứ i nối S[i] với D[i]. Hàm trả về số hiệu thành phố được chọn để xây sân đấu. Không viết main.

Dữ liệu vào

Lời giải nhận dữ liệu qua các tham số của LocateCentre, không đọc đầu vào chuẩn. Trình chấm mẫu đọc N ở dòng đầu; N dòng tiếp theo chứa P[0] đến P[N-1]; N-1 dòng cuối chứa các cặp S[i] D[i].

Dữ liệu ra

Trả về số hiệu thành phố tối ưu; không in kết quả. Trình chấm mẫu sẽ in giá trị trả về.

Ràng buộc

\(1\le N\le 1\,000\,000\); \(P[i]\ge1\); tổng số người hâm mộ không vượt quá \(2\,000\,000\,000\). Có đúng \(N-1\) đường hai chiều và đúng một tuyến đường giữa hai thành phố bất kỳ. Các đầu mút nằm trong khoảng từ 0 đến \(N-1\).

Phân nhóm

Mỗi nhóm chỉ có điểm khi vượt qua toàn bộ các bộ kiểm tra của nhóm. Có thể có lời giải vượt qua nhóm 3 nhưng không vượt qua nhóm 2. Trong kỳ thi gốc, điểm của toàn bài được quyết định bởi một bài nộp duy nhất.

Ví dụ

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

3

Chi tiết triển khai

Gói LQDOJ nhận một tệp C++ dùng traffic.h; tải templates.zip để lấy giao diện và mã khung. Đề gốc hỗ trợ traffic.c, traffic.cpp hoặc traffic.pas, giao diện traffic.h hoặc traffic.pas, không có hàm gọi ngược từ trình chấm. Thư mục làm bài gốc là /home/ioi2010-contestant/traffic/; các trình chấm mẫu là grader.c, grader.cpp, grader.pas, với đầu vào grader.in.* và kết quả grader.expect.*. Lệnh runc/submit cùng phím Control-R/Control-J thuộc môi trường thi gốc; trên LQDOJ, nộp tệp cài đặt hàm.

Nguồn

IOI 2010, ngày 2, bài 2 — Traffic Congestion. Đề chính thức, PDF tiếng Anh.

Ở miền nam Ontario, nhiều nông dân trồng ngô tạo ra mê cung bằng thân cây ngô vào mùa thu, sau khi thu hoạch hạt. Bạn vẫn còn thời gian giúp thiết kế mê cung tuyệt vời nhất cho năm 2010.

Cánh đồng phủ đầy thân cây ngô, trừ một số chướng ngại như cây cối, công trình, nơi ngô không mọc được. Những thân cây rất cao tạo thành tường mê cung. Lối đi được tạo trên lưới ô vuông bằng cách giẫm đổ ngô trong các ô kích thước \(1\text{ m}\times1\text{ m}\). Một ô ở biên là lối vào, và một ô là tâm mê cung.

Jack tới mê cung ngô hằng năm và đã rất giỏi tìm đường nhanh nhất từ lối vào tới tâm. Bạn phải chọn những ô ngô cần giẫm đổ để số ô Jack buộc phải đi qua lớn nhất có thể. Trình chấm tự xác định lối vào (ô lối đi duy nhất trên biên) và tâm (ô mà Jack phải đi xa nhất để tới được).

Bản đồ cánh đồng hình chữ nhật được biểu diễn bằng văn bản. Ký tự # là ô ngô còn đứng; X là chướng ngại không thể giẫm đổ. Chỉ được thay một số # bằng dấu chấm . để tạo lối đi. Đúng một ô . phải nằm trên biên; mọi ô . còn lại nằm bên trong. Chỉ được đi giữa hai ô . có chung cạnh.

Độ dài \(P\) là số ô trên đường đi ngắn nhất từ lối vào tới ô có khoảng cách lớn nhất mà có thể đi tới, tính cả lối vào và ô cuối. Mục tiêu là làm \(P\) lớn nhất. Theo trình chấm chính thức, khoảng cách được tính trong phần có thể đi tới từ lối vào; chu trình không bị cấm và các ô không thể đi tới không làm tăng \(P\).

Dữ liệu vào

Đây là bài chỉ nộp kết quả. Tải fields.zip, gồm mười cánh đồng cố định field1.txt, …, field9.txt, fieldA.txt. Mỗi tệp chỉ chứa các hàng của bản đồ, không có dòng ghi kích thước. Không có dữ liệu ngẫu nhiên hay bộ kiểm tra ẩn ngoài mười cánh đồng này.

Dữ liệu ra

Nộp một tệp ZIP chứa tệp maze.txt. Tệp này gồm lần lượt kết quả cho field1.txt, …, field9.txt, fieldA.txt, viết liền nhau theo đúng thứ tự và không có dòng phân cách. Kích thước của mười phần lần lượt là 6, 100, 100, 100, 100, 11, 20, 20, 11, 200 dòng. templates.zip chứa sẵn một tệp maze.txt hợp lệ theo đúng định dạng này.

Trong mỗi phần, phải giữ nguyên số ký tự trên mỗi dòng và mọi vị trí X. Chỉ được thay # thành . hoặc giữ nguyên #; không thêm ký tự, khoảng trắng, hàng trống hoặc nội dung sau bản đồ. Đúng một ô biên phải là .. Nếu bất kỳ phần nào không hợp lệ, bài nộp nhận 0 điểm.

Ràng buộc

Các kích thước và tham số chấm được nêu đầy đủ trong bảng dưới. Chỉ có ba ký tự #, X, . trong kết quả; tệp đầu vào chỉ có #, X. Hai ô kề chéo không nối với nhau.

Phân nhóm

Mỗi cánh đồng là một nhóm độc lập. Với kết quả hợp lệ có độ dài \(P\), điểm gốc của nhóm có tham số \(T\) là:

Trong kỳ thi gốc, kiểm tra công khai cho 1 điểm mỗi nhóm nếu kết quả hợp lệ, bất kể độ dài; kiểm tra chính thức cho phần điểm còn lại. Tổng điểm gốc được làm tròn tới số nguyên gần nhất trong khoảng 0 đến 110. Công thức \(s\) ở trên đã bao gồm phần điểm cho tính hợp lệ, không cộng thêm 1 lần nữa.

Trên LQDOJ, cả mười cánh đồng được chấm trong cùng một lượt để phần thưởng của cánh đồng này vẫn có thể bù cho cánh đồng khác như cách cộng điểm gốc. Gọi \(S\) là tổng mười giá trị \(s(P,T)\). Điểm LQDOJ là \(\min(100,S)\), không làm tròn. Vì vậy bài vẫn dùng nguyên công thức gốc và phần thưởng lịch sử trên 100 được chặn ở 100.

Ví dụ

##X#######
###X######
####X##X##
##########
##XXXX####
##########

#.X#######
#.#X#...##
#...X#.X.#
#.#......#
#.XXXX##.#
##########

#EX#######
#+#X#C+.##
#+++X#+X.#
#.#++++..#
#.XXXX##.#
##########

Chi tiết triển khai

Bài không có giao diện hàm, không nộp mã nguồn. Trong môi trường gốc, các tệp nằm trong /home/ioi2010-contestant/maze/. Trình chấm mẫu grader.c/.cpp/.pas đọc bản đồ qua grader.in.*, ghi OK N P khi đó là mê cung hợp lệ của nhóm N với độ dài P. Các tệp maze*.txt mẫu rất đơn giản có thể chép thành grader.in.* để thử. Môi trường IOI gốc nộp mười tệp riêng; LQDOJ ghép đúng mười nội dung đó vào một tệp maze.txt trong ZIP để toàn bộ điểm được tính chung.

Nguồn

IOI 2010, ngày 2, bài 3 — Maze. Đề chính thức, PDF tiếng Anh.

Công ty chuyển phát Xedef vận chuyển kiện hàng bằng máy bay giữa một số thành phố. Một số thành phố là trung tâm của Xedef, có cơ sở xử lý hàng chuyên dụng. Mỗi máy bay bay qua lại giữa một cặp thành phố và có thể chở hàng theo cả hai chiều.

Để chuyển một kiện hàng giữa hai thành phố, cần đưa nó qua một chuỗi chặng bay; mỗi chặng nối hai thành phố có máy bay phục vụ. Chuỗi này phải đi qua ít nhất một trung tâm của Xedef. Để định tuyến, Xedef muốn ghi trên nhãn của mỗi kiện hàng thông tin mã hóa về số chặng ít nhất từ mỗi thành phố tới mỗi trung tâm. Số chặng từ một trung tâm đến chính nó bằng 0. Thông tin phải được biểu diễn thật gọn.

Yêu cầu cài đặt

Bạn phải cài đặt hai hàm sau:

void encode(int N, int H, int P, int A[], int B[]);
void decode(int N, int H);

N là số thành phố, đánh số từ 0 đến N-1; H là số trung tâm, chính là các thành phố từ 0 đến H-1. Có P cặp thành phố được nối bằng máy bay. Các cặp không thứ tự đều khác nhau. Hai mảng A, B có P phần tử, với cặp thứ i là (A[i], B[i]).

encode phải tạo một dãy bit để từ đó decode xác định được số chặng ít nhất từ mọi thành phố đến mọi trung tâm. Các hàm sau do trình chấm cung cấp:

void encode_bit(int b);
int decode_bit();
void hops(int h, int c, int d);

encode gửi từng bit bằng encode_bit(b), với b bằng 0 hoặc 1. Lần gọi decode_bit() thứ \(i\) trả về bit được gửi trong lần gọi encode_bit thứ \(i\). Số lần gọi decode_bit không được vượt quá số bit đã gửi; không bắt buộc phải đọc hết các bit.

Sau khi giải mã, decode phải gọi hops(h,c,d) cho mọi cặp trung tâm h và thành phố c, kể cả c=h, với d là số chặng ít nhất từ h đến c. Phải có đúng N*H lời gọi, mỗi cặp đúng một lần; thứ tự tùy ý. Bảo đảm có thể đi từ mỗi trung tâm tới mọi thành phố.

Hai hàm chỉ được truyền thông tin qua giao diện quy định. Cấm dùng biến chung giữa hai giai đoạn, truy cập tệp hoặc mạng để truyền thông tin. Trong C/C++, có thể dùng biến static để giữ dữ liệu riêng của bộ mã hóa hoặc giải mã; trong Pascal có thể khai báo trong phần implementation. Trên LQDOJ, hai hàm chạy trong hai tiến trình riêng biệt: bộ giải mã không nhận mạng đường bay hay trạng thái bộ nhớ của bộ mã hóa.

Dữ liệu vào

Chương trình nhận dữ liệu qua tham số hàm và decode_bit, không đọc đầu vào chuẩn. Trong trình chấm mẫu chính thức, dòng đầu chứa N P H; P dòng tiếp theo chứa các cặp A[i] B[i]; H*N dòng sau là các khoảng cách đúng, theo thứ tự trung tâm rồi thành phố. Khoảng cách từ trung tâm i tới thành phố j nằm ở dòng thứ i*N+j+1 của phần này. Các khoảng cách đúng chỉ dành cho trình chấm.

Dữ liệu ra

Không in kết quả. encode gửi bit bằng encode_bit; decode báo kết quả bằng hops. Trình chấm mẫu chính thức ghi OK 1, OK 2, OK 3, OK 4 tương ứng với các nhóm mà lời giải vượt qua.

Ràng buộc

\(1\le N\le1000\); \(1\le H\le\min(N,36)\); các thành phố trong A, B thuộc \([0,N-1]\). Không có cặp trùng lặp hoặc cặp nối một thành phố với chính nó. Đồ thị liên thông, do đó \(N-1\le P\le N(N-1)/2\). Mỗi lần gọi hops phải có \(0\le h<H\), \(0\le c<N\) và khoảng cách đúng \(0\le d<N\).

Phân nhóm

Mọi nhóm có cùng ràng buộc về mạng đường bay. Mỗi nhóm chỉ có điểm khi giải mã đúng toàn bộ các bộ kiểm tra và không vượt giới hạn bit trên bất kỳ bộ nào.

Ví dụ

5 7 3
0 1
0 2
0 3
0 4
1 2
1 3
1 4

Chi tiết triển khai

Gói LQDOJ nhận một tệp C++ cài đặt cả encode và decode, không viết main. saveit.h khai báo đầy đủ các hàm; các tên encoder.h, decoder.h, grader.h trong templates.zip cũng giữ giao diện chính thức. Trình chấm biên dịch cùng stub.cpp và khởi chạy riêng bộ mã hóa, bộ giải mã.

Trong môi trường gốc, thư mục là /home/ioi2010-contestant/saveit/; thí sinh cài đặt encoder.c/.cpp/.pas và decoder.c/.cpp/.pas, với các giao diện encoder.h/.pas, decoder.h/.pas, grader.h hoặc graderlib.pas. Trình chấm mẫu là grader.c/.cpp/.pas cùng graderlib.pas. Lệnh runc/submit và phím Control-R/Control-J thuộc môi trường năm 2010; trên LQDOJ nộp tệp C++ như trên.

Nguồn

IOI 2010, ngày 2, bài 4 — Saveit. Đề chính thức, PDF tiếng Anh.