APIO 2017

Koala đã tạo ra một trò chơi mới và thách đấu bạn! Cô ấy bắt đầu bằng cách đặt xuống \(N\) vật phẩm, được đánh số từ \(0\) đến \(N-1\). Sau đó, cô bí mật gán cho mỗi vật phẩm một giá trị nguyên từ \(1\) đến \(N\) sao cho không có hai vật phẩm nào nhận cùng một giá trị. Vật phẩm \(i\) có giá trị \(P_i\). Cô thách bạn xác định một số tính chất của dãy giá trị \(P = P_0,P_1,\ldots,P_{N-1}\).

Để làm điều đó, bạn sẽ yêu cầu Koala chơi một số vòng. Trong mỗi vòng, bạn có \(W\) viên đá xanh lam và Koala có \(W\) viên đá đỏ. Bạn đi trước bằng cách đặt một số (có thể là tất cả) đá của mình cạnh những vật phẩm tùy chọn. Sau khi nhìn thấy cách sắp xếp của bạn, Koala cũng đặt một số (có thể là tất cả) đá của cô ấy cạnh các vật phẩm. Koala giành được tất cả các vật phẩm có số đá đỏ đặt cạnh nhiều hơn số đá xanh lam. Koala luôn phân phối đá sao cho tổng giá trị các vật phẩm cô giành được là lớn nhất. Nếu có nhiều cách đạt tổng giá trị lớn nhất, cô chọn cách giành được tổng số vật phẩm lớn nhất. Nếu vẫn còn nhiều cách, cô chọn một cách bất kỳ trong số đó.

Koala rất lười và sẽ ngủ quên nếu bạn yêu cầu cô chơi quá nhiều vòng. Nhiệm vụ của bạn là nhận biết các tính chất trong dãy \(P\) của Koala bằng cách chơi càng ít vòng càng tốt.

Chi tiết cài đặt

Thí sinh được khuyến nghị dùng mã mẫu của ngôn ngữ mình chọn làm điểm bắt đầu. Thí sinh phải cài đặt cả bốn hàm sau, kể cả khi chỉ làm một số subtasks; những hàm không dùng đến có thể để trống. Chương trình không được đọc từ đầu vào chuẩn, ghi ra đầu ra chuẩn hoặc tương tác với bất kỳ tệp nào.

Trong mỗi hàm, tham số N là số vật phẩm và W là số đá mà cả bạn lẫn Koala có trong mỗi vòng.

int minValue(int N, int W);

• Trả về số hiệu \(i\) của vật phẩm có giá trị nhỏ nhất, tức là \(P_i = 1\).

int maxValue(int N, int W);

• Trả về số hiệu \(i\) của vật phẩm có giá trị lớn nhất, tức là \(P_i = N\).

int greaterValue(int N, int W);

• So sánh giá trị của vật phẩm \(0\) và \(1\), rồi trả về số hiệu của vật phẩm có giá trị lớn hơn. Cụ thể, trả về \(0\) nếu \(P_0 > P_1\), ngược lại trả về \(1\).

void allValues(int N, int W, int *P);

• Xác định toàn bộ dãy và ghi vào mảng P: với mọi \(0 \le i \le N-1\), P[i] phải chứa giá trị \(P_i\) của vật phẩm \(i\).
• Hàm không trả về giá trị.

Trong mỗi testcase, trình chấm gọi chính xác một trong bốn hàm trên một hoặc nhiều lần. Mỗi lời gọi hàm được coi là một ván chơi riêng. Hàm nào được gọi và số lần tối đa hàm đó có thể được gọi phụ thuộc vào subtask. Có thể giả sử Koala đã cố định dãy \(P\) trước mỗi lời gọi hàm và dãy không thay đổi trong suốt lời gọi đó. Cô ấy có thể thay đổi dãy trước lời gọi hàm tiếp theo.

Mỗi hàm do thí sinh cài đặt có thể gọi hàm sau để lấy thông tin về dãy của Koala:

void playRound(int *B, int *R);

• Hàm này yêu cầu Koala chơi một vòng với bạn và không trả về giá trị.
• Mảng B mô tả số đá xanh lam bạn đặt cạnh từng vật phẩm. Với mọi \(0 \le i \le N-1\), B[i] viên đá xanh lam được đặt cạnh vật phẩm \(i\). Mỗi B[i] phải là số nguyên không âm và B[0] + B[1] + ... + B[N-1] không được vượt quá \(W\).
• Trình chấm điền vào mảng R để mô tả câu trả lời của Koala. Với mọi \(0 \le i \le N-1\), Koala đặt R[i] viên đá đỏ cạnh vật phẩm \(i\).
• Mỗi subtask quy định một giới hạn cứng cho số lần gọi playRound trong mỗi ván. Dùng ít lời gọi hơn giới hạn này có thể đem lại điểm cao hơn.

Phân nhóm

Gọi \(C_{max}\) là số lần gọi playRound lớn nhất trong tất cả các ván của một testcase, và \(C\) là số lần gọi playRound trong ván duy nhất của testcase thuộc Subtask 5.

Trong công thức trên, \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Trong mỗi testcase, chương trình phải luôn chạy trong giới hạn thời gian và bộ nhớ. Điều này bao gồm cả thời gian và bộ nhớ mà trình chấm sử dụng khi thiết lập, kết thúc và trả lời các lời gọi playRound. Khi ước lượng phần chi phí này, có thể giả sử trình chấm dùng để chấm có chức năng giống hệt và cách cài đặt tương tự trình chấm mẫu được cung cấp.

Nếu gọi playRound với mảng B không hợp lệ, hoặc số lời gọi playRound vượt giới hạn cứng của bất kỳ ván nào trong testcase, toàn bộ testcase bị chấm Not Correct và nhận \(0\) điểm.

Nếu một hàm không xác định đúng tính chất được yêu cầu của dãy \(P\) trong một ván bất kỳ của testcase, toàn bộ testcase bị chấm Not Correct và nhận \(0\) điểm.

Cả Subtask 4 và Subtask 5 đều yêu cầu cài đặt allValues, nhưng có giá trị \(W\) khác nhau. Có thể dùng điều này để phân biệt hai subtasks trong chương trình.

Bạn được nộp bài tối đa \(60\) lần và khoảng cách giữa hai lần nộp liên tiếp phải ít nhất \(2\) phút.

Ví dụ

Xét dãy \(P\) sau:

Dưới đây là một số lời gọi mẫu đến playRound và một câu trả lời hợp lệ của trình chấm cho mỗi lời gọi. Có thể có nhiều hơn một câu trả lời hợp lệ cho một lời gọi playRound.

Phản hồi cho từng hàm mà trình chấm gọi dưới đây (đúng một hàm trong mỗi testcase) được cung cấp theo thứ tự dưới dạng "Sample Data" khi nộp bài. Trong mỗi testcase này, được gọi playRound nhiều nhất \(3200\) lần.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

• Dòng \(1\): hai số nguyên \(F\), \(G\).
• Các dòng từ \(2\) đến \(G+1\): mỗi dòng chứa hai số nguyên \(N\), \(W\), theo sau bởi \(N\) số nguyên \(P_0,P_1,\ldots,P_{N-1}\) mô tả một ván.

Số nguyên \(F\) xác định hàm mà trình chấm mẫu sẽ gọi:

Số nguyên \(G\) xác định số lần gọi hàm đã chọn. Mỗi dòng sau đó mô tả một ván với dãy của Koala.

Với mỗi lời gọi hàm, trình chấm mẫu ghi hai dòng ra đầu ra chuẩn. Dòng đầu chứa số lần gọi playRound.

• Nếu \(F=4\), dòng thứ hai chứa nội dung mà hàm allValues đã ghi vào mảng P.
• Nếu \(F=1\), \(2\) hoặc \(3\), dòng thứ hai chứa một số nguyên duy nhất là giá trị trả về của hàm tương ứng.

Ví dụ, testcase thứ tư trong "Sample Data", gọi allValues với \(N=6\) và \(W=12\), có thể được mô tả bằng tệp đầu vào mẫu sau:

4 1
6 12 5 3 2 1 6 4

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2017: Koala Game.

Sau nhiều ngày băng qua vùng hoang dã rộng lớn của nước Úc, cuối cùng bạn đã đến thành phố Cobar tráng lệ với hành trang chỉ là một chiếc ba lô nhỏ. Say mê trước vẻ đẹp và sự kỳ diệu của các khu chợ nơi đây, bạn quyết định trở thành một thương gia và chọn Cobar làm quê hương mới. Cobar có \(N\) khu chợ, được đánh số từ \(1\) đến \(N\), nối với nhau bởi \(M\) đường đi bộ một chiều, mỗi đường cần một số phút nhất định để đi qua.

Các khu chợ ở Cobar giao dịch \(K\) mặt hàng khác nhau, được đánh số từ \(1\) đến \(K\). Mỗi khu chợ có một mức giá cố định để mua hoặc bán từng mặt hàng. Không phải khu chợ nào cũng giao dịch mọi mặt hàng; với một mặt hàng nhất định, một khu chợ có thể chỉ cho phép mua mà không cho phép bán, hoặc ngược lại. Có thể giả sử mỗi khu chợ bán một mặt hàng nào đó luôn có số lượng vô hạn, và tương tự, nếu một khu chợ muốn mua một mặt hàng thì khu chợ đó sẵn sàng mua đi mua lại mãi mãi.

Để kiếm tiền nhanh nhất có thể, bạn muốn tìm một chu trình sinh lời hiệu quả nhất. Một chu trình sinh lời là một hành trình trong Cobar, bắt đầu tại một khu chợ \(v\) với ba lô rỗng, tiếp tục dọc theo các đường đi bộ và qua các khu chợ của Cobar (có thể mua và bán các mặt hàng trên đường đi), rồi cuối cùng quay lại \(v\) với ba lô lại rỗng. Hành trình có thể ghé một khu chợ và/hoặc đi qua một đường đi bộ nhiều lần. Khi mua một mặt hàng, bạn phải lập tức đặt nó vào ba lô; vì ba lô nhỏ nên tại mọi thời điểm nó chỉ có thể chứa tối đa một mặt hàng. Có thể giả sử rằng bạn luôn mua được một mặt hàng nếu mặt hàng đó có bán, bất kể số tiền hiện có của bạn, và bạn không được phép bán một mặt hàng mà mình không sở hữu.

Lợi nhuận của một chu trình như vậy bằng tổng số tiền thu được từ việc bán hàng trừ đi tổng số tiền đã chi để mua hàng. Thời lượng của chu trình là tổng số phút đi bộ trên các đường đi tạo nên chu trình. Hiệu suất của một chu trình sinh lời bằng lợi nhuận của nó chia cho thời lượng. Lưu ý rằng một chu trình sinh lời không mua hoặc bán bất kỳ mặt hàng nào có hiệu suất bằng \(0\).

Nhiệm vụ của bạn là tìm hiệu suất lớn nhất trong tất cả các chu trình sinh lời có thời lượng dương. Hãy ghi giá trị này sau khi làm tròn xuống số nguyên gần nhất. Nếu không tồn tại chu trình sinh lời như vậy, hãy ghi \(0\).

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(K\): lần lượt là số khu chợ, số đường đi bộ và số mặt hàng.

\(N\) dòng tiếp theo mô tả các khu chợ. Dòng thứ \(i\) chứa \(2K\) số nguyên \(B_{i,1}, S_{i,1}, B_{i,2}, S_{i,2}, \ldots, B_{i,K}, S_{i,K}\). Với mọi \(1 \le j \le K\), cặp số nguyên \(B_{i,j}\) và \(S_{i,j}\) lần lượt mô tả mức giá mà bạn có thể mua và bán mặt hàng \(j\) tại khu chợ \(i\). Nếu không thể mua hoặc bán một mặt hàng, giá trị tương ứng được thay bằng \(-1\).

\(M\) dòng tiếp theo mô tả các đường đi bộ. Dòng thứ \(p\) chứa ba số nguyên \(V_p\), \(W_p\) và \(T_p\), mô tả một đường đi bộ một chiều từ khu chợ \(V_p\) đến khu chợ \(W_p\), cần \(T_p\) phút để đi qua.

Dữ liệu ra

In ra một số nguyên duy nhất là hiệu suất lớn nhất trong tất cả các chu trình sinh lời, được làm tròn xuống số nguyên gần nhất.

Phân nhóm

Trong tất cả các subtasks:

• \(1 \le N \le 100\);
• \(1 \le M \le 9900\);
• \(1 \le K \le 1000\);
• với mọi mặt hàng có thể được mua/bán, \(0 \le S_{i,j} \le B_{i,j} \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\) và \(1 \le j \le K\);
• \(V_p \ne W_p\) và \(1 \le T_p \le 10\,000\,000\) với mọi \(1 \le p \le M\);
• không tồn tại hai cạnh \(1 \le p < q \le M\) sao cho \((V_p, W_p) = (V_q, W_q)\).

Ví dụ

Phản hồi cho ví dụ sau sẽ được cung cấp dưới dạng "Sample Data" khi nộp bài.

4 5 2
10 9 5 2
6 4 20 15
9 7 10 9
-1 -1 16 11
1 2 3
2 3 3
1 4 1
4 3 1
3 1 1

2

Giải thích

Trong ví dụ, xét hai chu trình "1 đến 2 đến 3 đến 1" và "1 đến 4 đến 3 đến 1".

Với chu trình "1 đến 2 đến 3 đến 1", thời gian đi hết chu trình là \(7\) phút, bằng \(3 + 3 + 1\). Cách giao dịch có lợi nhất trên chu trình này là mua mặt hàng \(2\) tại khu chợ \(1\) (tốn \(5\)), bán nó tại khu chợ \(2\) (thu \(15\)), ngay lập tức mua mặt hàng \(1\) tại khu chợ \(2\) (tốn \(6\)), mang mặt hàng \(1\) qua khu chợ \(3\), rồi bán nó tại khu chợ \(1\) (thu \(9\)). Vì vậy lợi nhuận trên chu trình này là \(-5 + 15 - 6 + 9 = 13\). Giá trị \(13/7\) làm tròn xuống cho hiệu suất bằng \(1\).

Với chu trình "1 đến 4 đến 3 đến 1", thời gian đi hết chu trình là \(3\) phút, bằng \(1 + 1 + 1\). Cách giao dịch có lợi nhất trên chu trình này là mua mặt hàng \(2\) tại khu chợ \(1\) (tốn \(5\)), bán nó tại khu chợ \(4\) (thu \(11\)), rồi đi qua khu chợ \(3\) và trở lại khu chợ \(1\). Vì vậy lợi nhuận trên chu trình này là \(-5 + 11 = 6\). Giá trị \(6/3\) làm tròn xuống cho hiệu suất bằng \(2\).

Do đó, hiệu suất tốt nhất của một chu trình sinh lời tại Cobar là \(2\).

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2017: Travelling Merchant.

Ngày xửa ngày xưa, trong Thời Đại Mộng Mơ, nước Úc là một lưới phẳng gồm \(R\) hàng và \(C\) cột, và mỗi ô lưới đều là đất. Các hàng được đánh số từ \(1\) đến \(R\) theo hướng Bắc xuống Nam, còn các cột được đánh số từ \(1\) đến \(C\) theo hướng Tây sang Đông. Ô ở hàng \(r\), cột \(c\) được ký hiệu là \((r,c)\). Một ngày nọ, con rắn cầu vồng vĩ đại trồi lên từ mặt đất tại \((s_r,s_c)\) rồi trườn khắp nước Úc, tạo ra sông ở mọi nơi nó đi qua. Con rắn thực hiện \(M\) bước di chuyển liên tiếp; tại mỗi bước, nó đi đến ô kề ngay phía Bắc (N), Nam (S), Đông (E) hoặc Tây (W) và biến ô đó thành sông. Ô \((s_r,s_c)\) cũng được biến thành sông.

Hàng triệu năm sau, bạn muốn mua một khối ô hình chữ nhật để tưởng niệm việc con rắn cầu vồng tạo ra những dòng sông. Bạn sẽ chọn một màu cho mỗi ô đất bên trong khối chữ nhật. Bạn muốn sử dụng nhiều màu khác nhau nhất có thể, nhưng yêu cầu mọi cặp ô đất kề nhau bên trong khối đều có cùng màu. Hai ô được coi là kề nhau nếu chúng có chung một cạnh. Bạn không tô màu cho bất kỳ ô đất nào bên ngoài khối, cũng không tô màu cho các ô sông bên trong khối.

Biết các bước di chuyển của con rắn cầu vồng, với mỗi trong số \(Q\) khối ô hình chữ nhật, hãy xác định số màu khác nhau lớn nhất có thể dùng để tô các ô đất.

Chi tiết cài đặt

Thí sinh phải cài đặt hai hàm sau:

void init(int R, int C, int sr, int sc, int M, char *S);

• Trình chấm gọi hàm này đầu tiên và đúng một lần.
• R, C: số hàng và số cột của lưới.
• sr, sc: hàng và cột nơi con rắn trồi lên từ mặt đất.
• M: số bước di chuyển của con rắn.
• S: chuỗi độ dài \(M\); với mọi \(0 \le i \le M - 1\), S[i] là một trong các ký tự N, S, E, W, cho biết bước thứ \(i\) của con rắn đi đến ô kề ngay phía Bắc, Nam, Đông hoặc Tây so với vị trí hiện tại. Có thể giả sử con rắn không bao giờ rời khỏi lưới.
• Hàm này không trả về giá trị.

int colour(int ar, int ac, int br, int bc);

• Sau khi gọi init một lần, trình chấm gọi hàm này liên tiếp đúng \(Q\) lần.
• ar, ac: hàng và cột của góc Tây Bắc của khối chữ nhật.
• br, bc: hàng và cột của góc Đông Nam của khối chữ nhật.
• Có thể giả sử \(1 \le ar \le br \le R\) và \(1 \le ac \le bc \le C\).
• Hàm phải trả về một số nguyên duy nhất: số màu khác nhau lớn nhất có thể dùng cho các ô đất trong khối chữ nhật từ góc Tây Bắc \((ar,ac)\) đến góc Đông Nam \((br,bc)\) theo các quy tắc trên.

Hãy tham khảo các tệp mã mẫu được cung cấp để biết thêm chi tiết về cách cài đặt lời giải bằng ngôn ngữ lập trình đã chọn.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

• Dòng \(1\): bốn số nguyên \(R\), \(C\), \(M\) và \(Q\).
• Dòng \(2\): hai số nguyên \(s_r\) và \(s_c\).
• Dòng \(3\): chuỗi \(S\) gồm \(M\) ký tự, mỗi ký tự là N, S, E hoặc W; để trống dòng này nếu \(M = 0\).
• Các dòng từ \(4\) đến \(Q + 3\): bốn số nguyên \(a_r\), \(a_c\), \(b_r\) và \(b_c\).

Phiên làm việc mẫu và giải thích

Các hình sau tương ứng với phiên làm việc mẫu trên. Những ô màu xanh lam có hoa văn là ô sông.

{{asset:apio17rainbow/sample-diagrams.png}}

6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3

0
2
1
3

Phản hồi cho testcase mẫu này sẽ được cung cấp dưới dạng "Sample Data" khi nộp bài.

Phân nhóm

Trong tất cả các subtasks, \(0 \le M \le 100\,000\) và \(R,C,Q \ge 1\).

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2017: Land of the Rainbow Gold.