| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | CEOI 2025 - Boardgame Expo | 100 (p) | 2.0s | 1G |
| 2 | CEOI 2025 - Highest | 100 (p) | 2.0s | 1G |
| 3 | CEOI 2025 - Lawnmower | 100 (p) | 2.0s | 1G |
Hằng năm, một triển lãm trò chơi bàn lớn được tổ chức tại Cluj-Napoca, giới thiệu nhiều trò chơi mới. Điểm nhấn chính của năm nay là trò chơi BoardOina.
Có \(n\) người chơi đứng thành một hàng để chờ chơi thử. Họ được đánh số từ \(0\) đến \(n-1\) theo thứ tự trong hàng; người chơi \(0\) đứng đầu hàng và người chơi \(n-1\) đứng cuối hàng.
Có \(m\) quan hệ bạn bè phân biệt giữa \(m\) cặp người chơi. Với mỗi \(i\) từ \(0\) đến \(m-1\), người chơi \(X[i]\) và người chơi \(Y[i]\) là bạn, trong đó \(0\le X[i]<Y[i]<n\). Quan hệ bạn bè có tính đối xứng.
Xét \(k\) người liên tiếp bắt đầu từ người chơi \(s\), với \(0\le s<n\) và \(1\le k\le n-s\). Dãy người chơi này tạo thành một nhóm bạn kích thước \(k\) nếu mọi cặp người trong nhóm đều được nối với nhau bởi một dãy quan hệ bạn bè chỉ đi qua những người thuộc nhóm. Cụ thể, các người chơi \(s,s+1,\ldots,s+k-1\) tạo thành một nhóm bạn nếu với mọi \(u,v\) thỏa mãn \(s\le u<v<s+k\), tồn tại một dãy người chơi \(p[0],\ldots,p[l-1]\) sao cho:
Khi \(k=1\), riêng người chơi \(s\) cũng tạo thành một nhóm bạn kích thước \(1\).
BoardOina có thể được chơi bởi bất kỳ số người nào, nhưng để trò chơi hấp dẫn hơn, ban tổ chức chỉ cho các nhóm bạn tham gia.
Mỗi lần chỉ có một nhóm được chơi. Trong mỗi ván, một nhóm bạn bắt đầu tại người đang đứng đầu hàng được lập ra và bắt đầu chơi; sau đó những người trong nhóm này rời khỏi hàng. Quá trình lặp lại cho đến khi hàng trống.
Nói một cách chính thức, hàng người có thể được chia thành \(g\) nhóm bạn nếu tồn tại mảng kích thước nhóm
thỏa mãn tất cả các điều kiện sau:
Ban tổ chức muốn số nhóm tham gia là nhỏ nhất. Hãy tìm một cách chia hàng thành số nhóm bạn ít nhất và trả về mảng kích thước các nhóm.
Bạn cần cài đặt hàm sau:
std::vector<int> partition_players(
int n,
int m,
std::vector<int> X,
std::vector<int> Y
);
n: số người chơi trong hàng.m: số quan hệ bạn bè.X, Y: hai mảng độ dài \(m\) mô tả các quan hệ bạn bè.Nếu có nhiều cách chia đạt số nhóm ít nhất, bạn có thể trả về bất kỳ cách nào trong số đó.
Ví dụ 1
partition_players(5, 3, {0, 1, 3}, {1, 4, 4}){2, 1, 2}Trong ví dụ này, các cặp người chơi \((0,1)\), \((1,4)\) và \((3,4)\) là bạn.
Người chơi \(2\) không có người bạn nào trong hàng nên bắt buộc phải tạo thành một nhóm riêng. Do đó cần ít nhất \(3\) nhóm. Mặt khác, hai người chơi \(0,1\) có thể tạo thành một nhóm kích thước \(2\), và hai người chơi \(3,4\) cũng vậy. Vì thế có thể chia hàng thành ba nhóm kích thước \(2,1,2\).
Ví dụ 2
partition_players(7, 6, {0, 4, 2, 1, 2, 3}, {1, 5, 4, 5, 5, 6}){2, 1, 1, 2, 1}Trong ví dụ này, các cặp \((0,1)\), \((4,5)\), \((2,4)\), \((1,5)\), \((2,5)\) và \((3,6)\) là bạn.
Người bạn duy nhất của người chơi \(3\) là người chơi \(6\). Vì vậy, một nhóm bạn chứa người chơi \(3\) hoặc chỉ gồm riêng người chơi \(3\), hoặc phải chứa cả người chơi \(6\). Trường hợp thứ hai còn buộc nhóm chứa cả người chơi \(4\) và \(5\), nhưng người chơi \(6\) chỉ là bạn với người chơi \(3\), nên \(3\) không thể kết nối với \(4,5\) trong nhóm ấy. Do đó người chơi \(3\) phải ở một nhóm riêng. Tương tự, người chơi \(6\) cũng phải ở một nhóm riêng, nên cần ít nhất \(4\) nhóm.
Ba người chơi \(0,1,2\) không tạo thành một nhóm bạn: trong phạm vi nhóm đó, cả \(0\) lẫn \(1\) đều không kết nối được với \(2\). Nếu người chơi \(5\) cũng nằm trong nhóm thì điều này không còn đúng, nhưng do \(3\) và \(4\) chắc chắn thuộc hai nhóm khác nhau nên trường hợp ấy không thể xảy ra. Vì vậy cần ít nhất \(5\) nhóm.
Mặt khác, các cặp người chơi \(0,1\) và \(4,5\) lần lượt tạo thành hai nhóm kích thước \(2\). Do đó có thể chia hàng thành năm nhóm kích thước \(2,1,1,2,1\).
Trình chấm mẫu đọc dữ liệu theo định dạng sau:
n m.X[i] Y[i].Gọi mảng do partition_players trả về là \(K[0],K[1],\ldots,K[g-1]\). Trình chấm mẫu in:
K[0] K[1] ... K[g-1].Trong một vũ trụ khác, Vlad bị mắc kẹt trong một phiên bản tương lai của pháo đài Poenari gồm \(n\) tầng, được đánh số từ \(0\) đến \(n-1\). Từ mỗi tầng \(i\), Vlad chỉ có thể đi lên theo một trong hai cách:
Hai người anh em của Vlad là Radu và Mircea đưa ra \(m\) kịch bản. Mỗi kịch bản gồm hai tầng \(A\) và \(B\) với \(A\le B\). Với mỗi kịch bản, hãy tìm số giọt máu ít nhất Vlad phải trả để đi từ tầng \(A\) đến tầng \(B\).
Bạn cần cài đặt hàm sau:
std::vector<int> solve(
std::vector<int>& v,
std::vector<int>& w,
std::vector<std::pair<int, int>>& queries
);
v: mảng độ dài \(n\); v[i] là số tầng nhiều nhất cầu thang tại tầng \(i\) có thể đưa Vlad đi lên.w: mảng độ dài \(n\); w[i] là số tầng nhiều nhất hệ thống ống thông gió tại tầng \(i\) có thể đưa Vlad đi lên.queries: mảng độ dài \(m\) gồm các cặp \((A,B)\) như mô tả trong đề.Ví dụ 1
solve(
{2, 3, 1, 1, 1, 1, 2},
{3, 4, 1, 2, 1, 2, 2},
{{0, 4}, {0, 5}, {0, 6}}
){2, 3, 4}Ở đây \(n=7\).
Ví dụ 2
solve(
{1, 1, 1, 2, 3, 2, 1, 1, 2, 3},
{2, 4, 1, 4, 1, 4, 1, 3, 2, 3},
{{3, 9}, {0, 9}, {0, 7}, {0, 4}, {3, 5}}
){3, 5, 4, 3, 1}Các đường đi tối ưu tương ứng là:
Trình chấm mẫu đọc dữ liệu theo định dạng sau:
v[0] v[1] ... v[n-1].w[0] w[1] ... w[n-1].A B của truy vấn thứ \(i\).Trình chấm mẫu in \(m\) dòng là các phần tử của mảng do solve trả về.
Sau những cuộc phiêu lưu tại pháo đài Poenari, Vlad trở về nhà và, như một người Romania đích thực, việc đầu tiên anh nghĩ đến là cho ngựa ăn. Con ngựa không quá kén ăn nên Vlad dùng bãi cỏ làm nguồn thức ăn chính cho nó.
Vlad có một máy cắt cỏ với thùng chứa sức chứa \(c\). Anh chia bãi cỏ thành \(n\) luống, đánh số từ \(0\) đến \(n-1\), và phải cắt theo đúng thứ tự này. Luống \(i\) có \(v[i]\) đơn vị cỏ chưa cắt; Vlad mất \(a[i]\) giây để đẩy máy đi hết luống đó.
Sau khi đi qua một số luống, thùng chứa có thể đầy. Khi ấy máy ngừng cắt và để lại phần cỏ còn thừa trên luống đang đi qua. Mỗi lần như vậy, Vlad phải đổ thùng; thao tác này mất \(b\) giây và chỉ có thể thực hiện ở cuối một luống. Nếu thùng đầy khi Vlad đang đi qua luống \(i\), anh vẫn phải đẩy máy đến cuối luống, đổ thùng rồi đi qua luống đó thêm một lần nữa, hoặc nhiều lần nếu cần, để cắt hết phần cỏ còn lại.
Chẳng hạn, nếu cần đi qua luống \(i\) ba lần để cắt hết cỏ, thời gian là
Sau khi cắt xong toàn bộ bãi cỏ, Vlad bắt buộc phải đổ thùng chứa.
Vlad nhận ra đôi khi đổ thùng trước khi nó đầy có thể giúp tiết kiệm thời gian. Hãy tìm chiến lược giúp anh cắt xong toàn bộ bãi cỏ trong thời gian ít nhất.
Bạn cần cài đặt hàm sau:
long long mow(
int n,
int c,
int b,
std::vector<int>& a,
std::vector<int>& v
);
n: số luống cỏ.c: sức chứa của thùng gom cỏ.b: số giây cần để đổ thùng.a: mảng độ dài \(n\); a[i] là thời gian đi hết luống \(i\).v: mảng độ dài \(n\); v[i] là lượng cỏ trên luống \(i\).Ví dụ 1
mow(3, 5, 2, {2, 10, 3}, {2, 4, 6})24Vlad đi qua luống đầu tiên trong \(2\) giây, khi đó thùng chứa \(2\) đơn vị cỏ, rồi chủ động đổ thùng trong \(2\) giây. Tổng thời gian dành cho luống đầu là \(4\) giây.
Sau đó anh đi qua luống thứ hai, cắt \(4\) đơn vị cỏ trong \(10\) giây và không đổ thùng.
Ở luống thứ ba, sau khi cắt thêm \(1\) đơn vị cỏ thì thùng đầy. Vlad vẫn đi đến cuối luống, đổ thùng, rồi đi qua luống này lần nữa. Sau khi toàn bộ bãi cỏ đã được cắt, anh lại phải đổ thùng. Thời gian dành cho luống thứ ba là \(3+2+3+2=10\) giây.
Tổng thời gian là \(4+10+10=24\) giây và đây là phương án tối ưu.
Ví dụ 2
mow(4, 10, 4, {1, 2, 1, 4}, {3, 2, 6, 7})17Phương án tối ưu là đi qua ba luống đầu tiên. Khi đó thùng đầy và lượng cỏ còn lại trên các luống là \([0,0,1,7]\). Vlad đổ thùng, rồi đi qua hai luống cuối và đổ thùng lần nữa khi hoàn tất.
Tổng thời gian là
Trình chấm mẫu đọc dữ liệu theo định dạng sau:
n c b.a[0] a[1] ... a[n-1].v[0] v[1] ... v[n-1].Trình chấm mẫu in kết quả của lời gọi mow với các tham số tương ứng.