CEOI 2023 - Ngày 2

Đề bài

Sau khi sự nghiệp trộm tranh không hào nhoáng như mong đợi, bạn chuyển sang một mục tiêu mới: lấy trộm một huy chương tại CEOI năm nay. Kế hoạch đang diễn ra thuận lợi, nhưng giai đoạn tiếp theo cần một trợ lý và hiện tại bạn chưa đủ tiền thuê người.

Một cửa hàng ở Berlin bán \(N\) rô-bốt hút bụi có thể lập trình, đánh số từ \(1\) đến \(N\). Rô-bốt \(i\) có giá \(c_i\) euro. Người bán chỉ chấp nhận bán một đoạn liên tiếp đầy đủ: nếu mua rô-bốt \(i\) và \(j\), bạn phải mua mọi rô-bốt \(k\) với \(i\le k\le j\).

Các thí sinh khác rất thích rô-bốt, nên bạn hứa bán cho họ đúng \(K\) chiếc (\(1\le K\le N\)). Họ sẽ trả \(s_i\) euro cho rô-bốt \(i\).

Hãy:

• Tính lợi nhuận lớn nhất có thể đạt được khi mua một đoạn gồm ít nhất \(K\) rô-bốt rồi bán đúng \(K\) rô-bốt trong đoạn đó.
• Xác định những rô-bốt có thể được bán trong ít nhất một giao dịch đạt lợi nhuận lớn nhất.

Lợi nhuận của một giao dịch bằng tổng số tiền nhận được từ \(K\) rô-bốt đã bán trừ tổng giá mua của toàn bộ đoạn rô-bốt.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(K\).

Dòng thứ hai chứa \(N\) số nguyên \(c_1,c_2,\ldots,c_N\).

Dòng thứ ba chứa \(N\) số nguyên \(s_1,s_2,\ldots,s_N\).

Dữ liệu ra

Dòng đầu in một số nguyên là lợi nhuận lớn nhất có thể đạt được.

Dòng thứ hai in một xâu nhị phân độ dài \(N\). Ký tự thứ \(i\) là 1 nếu rô-bốt \(i\) có thể được bán trong một giao dịch nào đó đạt lợi nhuận lớn nhất, và là 0 nếu không.

Ràng buộc

• \(1\le N\le250\,000\).
• \(1\le K\le N\).
• \(1\le c_i,s_i\le10^9\) với mọi \(1\le i\le N\).

Phân nhóm

Mỗi subtask gồm hai nhóm. Nhóm thứ nhất cho điểm khi lợi nhuận lớn nhất được tính đúng; nhóm thứ hai cho thêm điểm khi toàn bộ dữ liệu ra, bao gồm xâu nhị phân, đúng.

• Subtask 1 (5 + 5 điểm): \(N\le200\).
• Subtask 2 (5 + 5 điểm): \(N\le6\,000\).
• Subtask 3 (5 + 5 điểm): \(K=2\).
• Subtask 4 (10 + 15 điểm): \(K\le200\).
• Subtask 5 (25 + 20 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 3
3 5 2 3 6
2 1 5 2 3

-1
00111

5 2
1 6 1 5 2
4 1 6 2 4

2
10111

Đề bài

Sau khi dùng lợi nhuận bán rô-bốt để thuê một trợ lý, bạn đã sẵn sàng tìm chiếc két chứa huy chương CEOI.

Két nằm trong một tòa nhà đại học gồm \(N\) phòng và \(N-1\) cánh cửa nối các phòng. Từ mọi phòng đều có thể đến mọi phòng khác, và mỗi phòng có nhiều nhất \(3\) cửa. Bạn và trợ lý đều có sơ đồ của cùng tòa nhà, nhưng hai bản sơ đồ có thể đánh số các phòng và các cửa khác nhau.

Trợ lý sẽ tìm căn phòng chứa két rồi để lại dấu hiệu bí mật giúp bạn tìm đến đó. Dấu hiệu là những chiếc cà vạt giống hệt nhau, nên thông tin duy nhất tại một phòng là số cà vạt được để lại trong phòng ấy. Để tránh gây chú ý, số cà vạt lớn nhất trong một phòng cần càng nhỏ càng tốt theo phần chấm điểm.

Sau đó, bạn bắt đầu từ một phòng nào đó và phải dùng các dấu hiệu để tìm phòng chứa két. Bản thân chiếc két bị giấu nên bạn không thể nhận ra nó chỉ bằng cách bước vào phòng. Bạn phải đi qua nhiều nhất \(d+30\) cánh cửa, trong đó \(d\) là số cửa trên đường đi trực tiếp từ vị trí bắt đầu đến phòng chứa két. Mỗi lần đi qua một cánh cửa đều được tính, kể cả khi đi qua cùng một cửa nhiều lần.

Hãy viết chương trình:

• Chỉ dẫn trợ lý số cà vạt cần để lại trong mỗi phòng.
• Sau đó dẫn bạn đến phòng chứa két.

Giao tiếp

Đây là bài giao tiếp mà chương trình được chạy hai lần riêng biệt cho mỗi bộ kiểm thử. Bạn phải nộp mã nguồn C++ cài đặt hai hàm sau, đồng thời khai báo giao diện bằng cách #include "incursion.h":

std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe);
void locate(std::vector<std::pair<int, int>> F, int curr, int t);

Hàm do trình chấm cung cấp:

int visit(int v);

Lần chạy thứ nhất: mark

std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe);

• F chứa \(N-1\) cặp \((u,v)\) với \(1\le u,v\le N\) và \(u\ne v\). Mỗi cặp biểu thị một cánh cửa nối phòng \(u\) và phòng \(v\).
• safe là số hiệu căn phòng chứa két theo cách đánh số trong bản sơ đồ của trợ lý.

Hàm phải trả về một vector T gồm đúng \(N\) số nguyên T[0], T[1], ..., T[N-1]. Giá trị T[i] là số cà vạt trợ lý để lại trong phòng \(i+1\) và phải thỏa mãn

Trong lần chạy này, không được gọi visit.

Lần chạy thứ hai: locate

void locate(std::vector<std::pair<int, int>> F, int curr, int t);

• F mô tả cùng một cây phòng, nhưng số hiệu phòng và thứ tự các cửa có thể khác hoàn toàn so với lần chạy thứ nhất.
• curr là phòng hiện tại của bạn theo cách đánh số trong bản sơ đồ thứ hai.
• t là số cà vạt được tìm thấy trong phòng curr.

Trong hàm này, bạn có thể gọi:

int visit(int v);

Lời gọi này di chuyển từ phòng hiện tại đến phòng \(v\) theo cách đánh số của bản sơ đồ thứ hai, rồi trả về số cà vạt trợ lý đã để trong phòng đó. Phải có một cánh cửa nối trực tiếp phòng hiện tại với \(v\), và \(1\le v\le N\).

Khi locate kết thúc, vị trí hiện tại phải là phòng chứa két. Tổng số lời gọi visit không được vượt quá \(d+30\), với \(d\) được định nghĩa ở trên.

Nếu gọi visit quá nhiều lần, gọi với đối số không hợp lệ, gọi trong lần chạy thứ nhất, trả về vector không hợp lệ từ mark, hoặc kết thúc locate ở sai phòng, chương trình bị dừng và bộ kiểm thử đó bị chấm sai.

Không được đọc từ đầu vào chuẩn hoặc ghi ra đầu ra chuẩn. Làm vậy có thể nhận kết quả Security violation!. Bạn được phép ghi ra luồng lỗi chuẩn (stderr).

Trình chấm chính thức có tính thích nghi: cách tương ứng giữa hai cách đánh số có thể phụ thuộc vào hành vi của chương trình trong lần chạy hiện tại cũng như các lần chạy trước.

Ràng buộc

• \(2\le N\le45\,000\).
• Mỗi phòng có bậc không quá \(3\).

Phân nhóm

Gọi

• Subtask 1 (30 điểm): Không có phòng nào có \(3\) cửa.
• Subtask 2 (30 điểm): Có đúng một phòng có \(2\) cửa.
• Subtask 3 (40 điểm): Không có ràng buộc bổ sung.

Trong mỗi subtask, phần điểm thực nhận phụ thuộc vào \(T_{\max}\):

Ví dụ giao tiếp

Xét tòa nhà có \(N=3\) với sơ đồ dưới đây. Trong mỗi phòng, số thứ nhất là số hiệu trên sơ đồ của trợ lý và số thứ hai là số hiệu trên sơ đồ của bạn. Phòng lớn phía dưới, tô màu vàng, chứa két; phòng phía trên bên phải, có viền đậm, là vị trí bắt đầu.

![Hai cách đánh số phòng trong ví dụhttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_f62a8e6f.png

Trong lần chạy thứ nhất, trình chấm gọi:

mark({{1, 2}, {2, 3}}, 1)

Giả sử hàm trả về {2, 2, 0}: trợ lý để hai cà vạt trong phòng \(1\) và \(2\), không để cà vạt trong phòng \(3\).

Trong lần chạy thứ hai, trình chấm gọi:

locate({{1, 3}, {2, 3}}, 1, 0)

Một phiên giao tiếp có thể diễn ra như sau:

Bạn đã đi qua bốn cánh cửa, trong khi khoảng cách trực tiếp \(d\) từ vị trí bắt đầu đến két là \(2\).

Trình chấm mẫu

Để thử chương trình cục bộ, liên kết lời giải với sample_grader.cpp và incursion.h. Để đơn giản, trình chấm mẫu không chạy chương trình trong hai tiến trình riêng mà gọi mark rồi locate đúng một lần trong cùng một lần chạy.

Trình chấm mẫu đọc \(N\) và safe, sau đó đọc \(N-1\) cặp mô tả F. Nó gọi mark(F, safe) và in vector trả về. Tiếp theo, nó đọc vị trí bắt đầu curr, gọi locate(F, curr, T[curr-1]) và in biên bản các lời gọi visit. Trình chấm mẫu không thay đổi cách đánh số phòng và cửa giữa hai hàm.

Khi kết thúc, trình chấm mẫu in một trong các thông báo:

• Invalid input: dữ liệu cho trình chấm không đúng định dạng.
• Invalid call to visit: visit được gọi từ mark hoặc với đối số không hợp lệ.
• Invalid return value of mark: vector trả về không có đúng \(N\) phần tử hoặc có giá trị ngoài đoạn \([0,10^9]\).
• Correct: at most Tmax tie(s) per room: locate kết thúc ở phòng chứa két và giá trị lớn nhất trong vector là \(T_{\max}\).
• Not correct: current position is curr: locate kết thúc ở một phòng khác phòng chứa két.

Trình chấm chính thức chỉ trả về Not correct, Security violation!, Partially correct hoặc Correct. Cả trình chấm mẫu lẫn trình chấm chính thức đều tự động dừng chương trình ngay khi phát hiện lỗi. Các giới hạn tài nguyên được áp dụng riêng cho từng lần chạy chính thức.

Đề bài

Bạn đang đứng trước chiếc két mở, tay cầm một tấm huy chương. Nhưng niềm vui nhanh chóng biến thành tuyệt vọng: một thông điệp trên chiếc cà vạt trong phòng tiết lộ rằng trợ lý đã báo kế hoạch của bạn cho Ủy ban Khoa học. Hai chủ tịch Ủy ban đang ẩn trong tòa nhà để ngăn bạn trốn thoát.

May mắn là bạn còn \(R\) rô-bốt hút bụi sau giao dịch với các thí sinh khác. Bạn muốn dùng chúng để xác định vị trí của hai chủ tịch trong số \(1\,000\) vị trí có thể có. Mỗi rô-bốt có thể được giao thăm dò nhiều vị trí, nhưng chỉ cho biết liệu có ít nhất một chủ tịch ở một trong các vị trí đã thăm dò hay không.

Mỗi rô-bốt cần trọn một giờ để thăm dò rồi quay lại. Vì pin sẽ cạn, mỗi rô-bốt chỉ được cử đi đúng một lần. Bạn muốn biết vị trí hai chủ tịch sau không quá \(H\) giờ; do đó, có thể phải cử nhiều rô-bốt đi cùng lúc trước khi các rô-bốt trước đó trở về. Hai chủ tịch không thay đổi vị trí trong suốt quá trình.

Hãy lập kế hoạch thăm dò và xác định vị trí của cả hai chủ tịch.

Giao tiếp

Đây là bài giao tiếp. Bạn phải nộp mã nguồn C++ cài đặt hàm scout và khai báo giao diện bằng cách #include "avoid.h":

std::pair<int, int> scout(int R, int H);

Với mỗi bộ kiểm thử, trình chấm gọi scout(R, H) đúng một lần. Hàm phải trả về cặp \((a,b)\) với \(1\le a,b\le1\,000\), là vị trí của hai chủ tịch. Hai chủ tịch được phép ở cùng một vị trí, tức là có thể có \(a=b\); thứ tự của \(a\) và \(b\) không quan trọng.

Trong scout, bạn có thể gọi hai hàm do trình chấm cung cấp.

Hàm send

void send(std::vector<int> P);

Hàm này cử một rô-bốt thăm dò các vị trí \(P[0],P[1],\ldots,P[k-1]\), trong đó \(k\) là độ dài của P.

• Mỗi phần tử của P phải nằm trong đoạn từ \(1\) đến \(1\,000\).
• Các phần tử của P phải đôi một khác nhau.
• Có thể gọi send nhiều nhất \(R\) lần trong mỗi bộ kiểm thử.
• Một rô-bốt được cử đi sẽ trở về sau đúng một lời gọi wait tiếp theo.

Hàm wait

std::vector<int> wait();

Hàm này chờ một giờ và trả về một mảng chứa đúng một phần tử cho mỗi rô-bốt đã được cử đi trong giờ vừa qua, tức là bởi các lời gọi send sau lời gọi wait trước đó hoặc sau khi chương trình bắt đầu.

Phần tử thứ \(i\) bằng 1 nếu rô-bốt thứ \(i+1\) trong nhóm đó phát hiện ít nhất một chủ tịch tại các vị trí nó thăm dò, và bằng 0 nếu không. Có thể gọi wait nhiều nhất \(H\) lần trong mỗi bộ kiểm thử.

Nếu một lời gọi không thỏa các yêu cầu trên, chương trình bị dừng ngay và bộ kiểm thử đó bị chấm sai.

Không được đọc từ đầu vào chuẩn hoặc ghi ra đầu ra chuẩn. Làm vậy có thể nhận kết quả Security violation!. Bạn được phép ghi ra luồng lỗi chuẩn (stderr).

Phân nhóm

• Subtask 1 (10 điểm): \(R=10\), \(H=1\) và hai chủ tịch ở cùng một vị trí.
• Subtask 2 (5 điểm): \(R=H=20\).
• Subtask 3 (10 điểm): \(R=30\), \(H=2\).
• Subtask 4 (75 điểm): \(R=75\), \(H=1\).

Trong Subtask 4, điểm thực nhận phụ thuộc vào số rô-bốt lớn nhất \(r_{\max}\) được cử đi trên mọi bộ kiểm thử của subtask. Điểm là hàm tuyến tính từng đoạn đi qua các mốc sau:

Với \(r_{\max}\le26\), bạn nhận đủ \(75\) điểm. Giữa hai mốc liên tiếp, điểm giảm tuyến tính; số điểm chính xác cho từng giá trị nguyên được cung cấp trong tệp score_table.txt của bộ đính kèm chính thức.

![Đồ thị điểm thành phần theo số rô-bốt lớn nhấthttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_ce6afdb9.png

Ví dụ giao tiếp

Xét một bộ kiểm thử có \(R=75\), \(H=20\), trong đó hai chủ tịch ở vị trí \(13\) và \(37\). Trình chấm gọi scout(75, 20). Một phiên giao tiếp có thể diễn ra như sau:

Trả về {37, 13} cũng được chấp nhận.

Các truy vấn trong ví dụ thực ra chưa đủ để xác định chắc chắn hai vị trí: chẳng hạn, cả hai chủ tịch cùng ở vị trí \(37\), hoặc một người ở \(13\) và người kia ở \(100\), đều phù hợp với mọi kết quả wait. Vì vậy, trình chấm cũng có thể bác bỏ chiến lược này bằng cách lựa chọn vị trí thích nghi khác.

Trình chấm mẫu

Để thử chương trình cục bộ, liên kết lời giải với sample_grader.cpp và avoid.h.

Trình chấm mẫu đọc bốn số nguyên \(R\), \(H\), \(a\), \(b\), trong đó \(a,b\) là hai vị trí cố định, rồi gọi scout(R,H) và in biên bản mọi hàm mà chương trình gọi. Khi kết thúc, nó in một trong các thông báo:

• Invalid input: dữ liệu cho trình chấm không đúng định dạng.
• Invalid send: đối số của send không hợp lệ.
• Out of robots: chương trình gọi send quá \(R\) lần.
• Out of time: chương trình gọi wait quá \(H\) lần.
• Wrong answer: cặp trả về không phải hai vị trí của chủ tịch.
• Correct: r robot(s) used, h hour(s) passed: câu trả lời đúng, chương trình đã gọi send \(r\) lần và wait \(h\) lần.

Trình chấm chính thức chỉ trả về Not correct, Security violation! hoặc thông báo thành công. Trình chấm chính thức có tính thích nghi: vị trí hai chủ tịch có thể phụ thuộc vào hành vi của chương trình trong lần chạy hiện tại cũng như các lần chạy trước. Cả trình chấm mẫu lẫn trình chấm chính thức đều tự động dừng chương trình ngay khi phát hiện lỗi.