JOI 2020 - Trại huấn luyện mùa xuân - Ngày 3

JOI-kun chụp một bức ảnh phong cảnh ban đêm. Bức ảnh gồm \(N \times N\) điểm ảnh, tức là có \(N\) điểm ảnh theo mỗi chiều ngang và dọc. Điểm ảnh ở cột thứ \(x\) từ trái sang và hàng thứ \(y\) từ dưới lên (\(1 \le x,y \le N\)) được gọi là điểm ảnh \((x,y)\).

Mỗi điểm ảnh thể hiện một tòa nhà, bầu trời đêm hoặc ngôi sao, lần lượt có màu trắng, đen hoặc vàng. Với mỗi \(1 \le i \le N\), trong cột thứ \(i\), các điểm ảnh từ hàng dưới cùng đến hàng thứ \(A_i\) từ dưới lên đều có màu trắng, thể hiện các tòa nhà. Có \(M\) điểm ảnh màu vàng thể hiện các ngôi sao; điểm ảnh vàng thứ \(j\) (\(1 \le j \le M\)) ở vị trí \((X_j,Y_j)\). Tất cả điểm ảnh còn lại đều màu đen, thể hiện bầu trời đêm.

Một vùng hình chữ nhật trong ảnh được gọi là thể hiện một chòm sao nếu thỏa mãn cả hai điều kiện:

• Không có điểm ảnh màu trắng trong vùng đó.
• Có ít nhất hai điểm ảnh màu vàng trong vùng đó.

JOI-kun đã chán ngắm các chòm sao. Cậu muốn tô đen một số điểm ảnh vàng sao cho không còn vùng hình chữ nhật nào thể hiện một chòm sao. Tuy nhiên, tô đen nhiều điểm ảnh vàng sẽ khiến bức ảnh mất tự nhiên. Cụ thể, nếu tô đen điểm ảnh vàng thứ \(j\), mức độ thiếu tự nhiên của ảnh tăng thêm \(C_j\). Ban đầu, mức độ thiếu tự nhiên bằng \(0\).

Cho thông tin bức ảnh và chi phí tô đen từng điểm ảnh vàng, hãy tính mức độ thiếu tự nhiên nhỏ nhất có thể sau khi tô sao cho không còn vùng hình chữ nhật nào thể hiện một chòm sao.

Dữ liệu vào

Đọc từ đầu vào chuẩn. Tất cả giá trị đều là số nguyên, theo định dạng:

N
A_1 ... A_N
M
X_1 Y_1 C_1
...
X_M Y_M C_M

Dữ liệu ra

In ra một dòng chứa mức độ thiếu tự nhiên nhỏ nhất sau khi tô đen một số điểm ảnh vàng để không còn vùng hình chữ nhật nào thể hiện một chòm sao.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le A_i \le N\) với \(1 \le i \le N\).
• \(1 \le M \le 200\,000\).
• \(1 \le X_j,Y_j \le N\) với \(1 \le j \le M\).
• \(1 \le C_j \le 1\,000\,000\,000\) với \(1 \le j \le M\).
• \(A_{X_j}<Y_j\) với \(1 \le j \le M\).
• \((X_j,Y_j)\ne(X_k,Y_k)\) với \(1 \le j<k \le M\).

Phân nhóm

Các ràng buộc chung áp dụng cho mọi nhóm.

1. \(14\) điểm: \(N \le 300\), \(M \le 300\)
2. \(21\) điểm: \(N \le 2000\), \(M \le 2000\)
3. \(65\) điểm: Không có

Ví dụ

5
1 3 4 2 3
3
1 5 3
4 3 2
2 4 2

2

7
5 6 2 3 6 7 6
5
7 7 5
3 3 7
3 7 10
1 7 6
4 7 8

16

8
6 8 5 7 3 4 2 1
10
8 2 9
6 6 7
8 3 18
5 8 17
8 5 3
5 5 3
5 4 8
1 8 13
1 7 5
7 4 13

44

Nguồn

JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi 3. Đề gốc của Ủy ban Olympic Tin học Nhật Bản, được cung cấp theo giấy phép CC BY-SA 4.0. Bản tiếng Việt được dịch từ đề tiếng Anh chính thức.

Trang trại IOI trồng táo và nổi tiếng vì nằm quanh một hồ nước lớn hình tròn. Trang trại có \(N\) nhân viên, đánh số từ \(1\) đến \(N\), và \(M\) cây táo, đánh số từ \(1\) đến \(M\). Chu vi hồ là \(L\) mét.

Ban đầu, nhân viên thứ \(i\) (\(1 \le i \le N\)) đứng cách điểm cực bắc của hồ \(A_i\) mét theo chiều kim đồng hồ. Các giá trị \(A_i\) đôi một khác nhau. Cây táo thứ \(j\) (\(1 \le j \le M\)) nằm cách điểm cực bắc của hồ \(B_j\) mét theo chiều kim đồng hồ. Các giá trị \(B_j\) đôi một khác nhau, và không có cây táo nào ở vị trí ban đầu của một nhân viên.

Nhờ cải tiến giống đặc biệt, mỗi cây có nhiều nhất một quả táo tại mỗi thời điểm. Sau khi một quả được hái, đúng \(C\) giây sau cây sẽ có một quả mới. Tại thời điểm \(0\), mỗi cây đều có một quả táo, và mọi nhân viên bắt đầu đi quanh hồ theo chiều kim đồng hồ với tốc độ \(1\) mét mỗi giây. Khi đến một cây đang có quả, nhân viên luôn hái quả đó. Nếu cây vừa có quả mới đúng lúc nhân viên đến, người đó cũng hái được quả. Bỏ qua thời gian hái táo.

Ngài K là cổ đông của trang trại IOI. Bạn là người quản lý trang trại, và ngài K yêu cầu bạn báo cáo hiệu suất của các nhân viên. Cụ thể, với mỗi truy vấn thứ \(k\) (\(1 \le k \le Q\)), hãy tính số quả táo nhân viên \(V_k\) hái được tính đến thời điểm \(T_k\), bao gồm cả quả hái đúng tại thời điểm \(T_k\) nếu có.

Cho số nhân viên, số cây táo, chu vi hồ, thời gian mọc quả mới, vị trí các nhân viên và cây táo cùng \(Q\) truy vấn, hãy trả lời từng truy vấn.

Dữ liệu vào

Đọc từ đầu vào chuẩn. Tất cả giá trị đều là số nguyên, theo định dạng:

N M L C
A_1 ... A_N
B_1 ... B_M
Q
V_1 T_1
...
V_Q T_Q

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa đáp án cho truy vấn thứ \(k\).

Ràng buộc

• \(1 \le N,M \le 200\,000\).
• \(N+M \le L \le 1\,000\,000\,000\).
• \(1 \le C \le 1\,000\,000\,000\).
• \(0 \le A_i<L\) với \(1 \le i \le N\).
• \(A_i<A_{i+1}\) với \(1 \le i \le N-1\).
• \(0 \le B_j<L\) với \(1 \le j \le M\).
• \(B_j<B_{j+1}\) với \(1 \le j \le M-1\).
• \(A_i\ne B_j\) với \(1 \le i \le N\), \(1 \le j \le M\).
• \(1 \le Q \le 200\,000\).
• \(1 \le V_k \le N\) với \(1 \le k \le Q\).
• \(1 \le T_k \le 10^{18}\) với \(1 \le k \le Q\).

Phân nhóm

Các ràng buộc chung áp dụng cho mọi nhóm.

1. \(5\) điểm: \(N \le 3000\), \(M \le 3000\), \(Q \le 3000\)
2. \(20\) điểm: \(T_k \ge 10^{15}\) với mọi \(1 \le k \le Q\)
3. \(75\) điểm: Không có

Ví dụ

3 2 7 3
1 4 6
0 5
3
1 7
2 3
3 8

2
1
1

5 3 20 6
0 4 8 12 16
2 11 14
9
4 1932
2 93787
1 89
5 98124798
1 2684
1 137598
3 2
3 8375
4 237

146
7035
7
7359360
202
10320
0
628
18

8 15 217 33608
0 12 71 96 111 128 152 206
4 34 42 67 76 81 85 104 110 117 122 148 166 170 212
14
2 223544052420046341
3 86357593875941375
4 892813012303440034
1 517156961659770735
7 415536186438473633
6 322175014520330760
7 557706040951533058
6 640041274241532527
5 286263974600593111
8 349405886653104871
1 987277313830536091
5 989137777159975413
2 50689028127994215
7 445686748471896881

33230868503053
3
5
1
123542793648997
8
165811220737767
8
7
1
1
7
7535161012043
132506837660717

Nguồn

JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi 3. Đề gốc của Ủy ban Olympic Tin học Nhật Bản, được cung cấp theo giấy phép CC BY-SA 4.0. Bản tiếng Việt được dịch từ đề tiếng Anh chính thức.

Anthony là một chú kiến sống ở thành phố JOI. Thành phố có \(N\) thị trấn, đánh số từ \(0\) đến \(N-1\). Anthony sống ở thị trấn \(0\). Có \(M\) con đường, đánh số từ \(0\) đến \(M-1\). Đường thứ \(i\) nối hai thị trấn \(U_i,V_i\) và đi được theo cả hai chiều. Hai con đường khác nhau không nối cùng một cặp thị trấn. Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác qua các con đường.

Catherine là một cô mèo, bạn của Anthony. Cô định đến thăm thành phố JOI nhưng không biết thông tin đường sá và thường bị lạc. Anthony quyết định đánh dấu các con đường từ trước. Có \(A\) loại dấu, đánh số từ \(0\) đến \(A-1\).

Catherine đã đến một thị trấn trong thành phố. Mỗi khi ở một thị trấn khác \(0\), với từng loại dấu, cô có thể đếm số đường mang dấu đó đi ra từ thị trấn hiện tại, không tính con đường vừa đi qua nếu có. Sau đó cô chọn một con đường để đi. Ngoại trừ con đường vừa đi qua, cô chỉ phân biệt được các đường dựa trên loại dấu.

Gọi \(d\) là số đường ít nhất cần đi qua để từ thị trấn xuất phát đến thị trấn \(0\). Catherine muốn đến thị trấn \(0\) sau nhiều nhất \(d+B\) lần chọn đường.

Hãy viết chương trình thực hiện chiến lược đánh dấu đường của Anthony khi biết thông tin các con đường, và chương trình thực hiện chiến lược chọn đường của Catherine.

Giao diện giao tiếp

Bạn cần nộp hai tệp.

Tệp Anthony.cpp thực hiện chiến lược của Anthony, phải khai báo sử dụng Anthony.h và cài đặt hàm:

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V);

Hàm này được gọi đúng một lần lúc bắt đầu.

• \(N\) là số thị trấn; \(M\) là số con đường.
• \(A\) là số loại dấu; \(B\) là số lần chọn đường được phép thêm so với đường đi ngắn nhất.
• U và V là hai mảng dài \(M\); U[i] và V[i] là hai đầu của đường thứ \(i\), với \(0 \le i \le M-1\).
• Giá trị trả về x phải là mảng dài \(M\). Nếu độ dài khác \(M\), bài làm bị chấm Wrong Answer [1].
• x[i] là loại dấu đặt trên đường thứ \(i\), phải thỏa mãn \(0 \le\) x[i] \(\le A-1\). Nếu không, bài làm bị chấm Wrong Answer [2].

Tệp Catherine.cpp thực hiện chiến lược của Catherine, phải khai báo sử dụng Catherine.h và cài đặt hai hàm:

void Init(int A, int B);
int Move(std::vector<int> y);

Hàm Init được gọi đúng một lần lúc bắt đầu. \(A\) là số loại dấu, còn \(B\) là số lần chọn đường được phép thêm so với đường đi ngắn nhất.

Hàm Move được gọi mỗi khi Catherine đến một thị trấn khác \(0\).

• y là mảng dài \(A\). Với \(0 \le j \le A-1\), y[j] là số đường đi ra từ thị trấn hiện tại mang dấu \(j\), không tính đường vừa đi qua nếu có.
• Giá trị trả về \(z\) phải thỏa mãn \(-1 \le z \le A-1\); nếu không, bài làm bị chấm Wrong Answer [3].
• Nếu \(z=-1\), Catherine quay lại theo đường vừa đi qua. Trả về \(-1\) trong lần gọi Move đầu tiên sẽ bị chấm Wrong Answer [4].
• Nếu \(0 \le z \le A-1\), Catherine chọn một đường mang dấu \(z\) trong số các đường được đếm trong y[z]. Nếu y[z] = 0, bài làm bị chấm Wrong Answer [5].

Khi Catherine chọn một đường khác đường vừa đi qua, đường thực tế cô đi sẽ là một trong các đường mang loại dấu đã chỉ định. Việc chọn đường này không nhất thiết là ngẫu nhiên.

Nếu sau \(d+B\) lần đi qua đường, Catherine vẫn chưa đến thị trấn \(0\) (tức là đã gọi Move \(d+B\) lần), bài làm bị chấm Wrong Answer [6].

Có thể cài đặt thêm hàm nội bộ hoặc dùng biến toàn cục. Các tệp nộp được biên dịch cùng trình chấm thành một tệp thực thi. Hãy đặt các hàm nội bộ và biến toàn cục trong namespace không tên để tránh trùng tên với các tệp khác. Khi chấm, Anthony và Catherine chạy trong hai tiến trình riêng, không chia sẻ biến toàn cục.

Chương trình của bạn không được sử dụng đầu vào chuẩn hoặc đầu ra chuẩn, cũng không được giao tiếp với các tệp khác bằng bất kỳ phương thức nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Trình chấm mẫu

Gói tệp mẫu chứa trình chấm mẫu grader.cpp, các tệp khởi đầu và các tệp tiêu đề. Để dùng trình chấm mẫu, đặt grader.cpp, Anthony.cpp, Catherine.cpp, Anthony.h và Catherine.h trong cùng thư mục.

Trình chấm thật khác trình chấm mẫu. Trình chấm mẫu chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào

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

N M A B S
U_0 V_0
...
U_{M-1} V_{M-1}

Ở đây \(S\) là số hiệu thị trấn xuất phát của Catherine.

Dữ liệu ra

Khi kết thúc bình thường, trình chấm mẫu in ra:

• Nếu phát hiện một trong các lỗi Wrong Answer [1] đến Wrong Answer [5], in loại lỗi tương ứng, chẳng hạn Wrong Answer [1].
• Nếu Catherine vẫn chưa đến thị trấn \(0\) sau \(N+B\) lần di chuyển, in Wrong Answer; Number of moves > N + B.
• Ngược lại, in số lần di chuyển (số lần gọi Move), chẳng hạn Number of moves = 4. Trình chấm mẫu không kiểm tra kết quả là đúng hay thuộc lỗi Wrong Answer [6].

Nếu có nhiều loại lỗi, trình chấm mẫu chỉ thông báo một loại.

Trong trình chấm mẫu, khi Catherine không quay lại đường vừa đi qua, đường tiếp theo được chọn ngẫu nhiên đều trong số các đường có dấu yêu cầu bằng bộ sinh số giả ngẫu nhiên với hạt giống cố định. Có thể đổi hạt giống bằng đối số nguyên đầu tiên khi chạy trình chấm mẫu, chẳng hạn:

./grader 2020

Ràng buộc

• \(2 \le N \le 20\,000\).
• \(1 \le M \le 20\,000\).
• \(1 \le S \le N-1\), với \(S\) là thị trấn xuất phát của Catherine.
• \(0 \le U_i<V_i \le N-1\) với \(0 \le i \le M-1\).
• \((U_i,V_i)\ne(U_j,V_j)\) với \(0 \le i<j \le M-1\).
• Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác qua các con đường.

Phân nhóm

Các ràng buộc chung áp dụng cho mọi nhóm.

1. \(2\) điểm: \(A=4\), \(B=0\), \(M=N-1\)
2. \(2\) điểm: \(A=4\), \(B=0\)
3. \(2\) điểm: \(A=3\), \(B=0\), \(M=N-1\)
4. \(9\) điểm: \(A=3\), \(B=0\)
5. \(5\) điểm: \(A=2\), \(B=2N\), \(M=N-1\), \(6 \le N \le 500\)
6. \(71\) điểm: \(A=2\), \(B=12\), \(M=N-1\)
7. \(9\) điểm: \(A=2\), \(B=6\), \(M=N-1\)

Ví dụ giao tiếp

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

Trình chấm mẫu ghi ra:

Number of moves = 4

Đây là một chuỗi lời gọi và giá trị trả về tương ứng với dữ liệu mẫu:

Trong chuỗi giao tiếp này, Catherine lần lượt thăm các thị trấn \(1,5,1,2,0\). Ta có \(d=2\) và Catherine di chuyển \(4\) lần; đầu ra ở trên là kết quả của trình chấm mẫu cho chuỗi giao tiếp này.

Dữ liệu này thỏa mãn ràng buộc của nhóm \(7\). Trong các tệp mẫu được đề gốc nhắc tới, sample-02.txt thỏa mãn ràng buộc của nhóm \(4\).

Nguồn

JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi 3. Đề gốc của Ủy ban Olympic Tin học Nhật Bản, được cung cấp theo giấy phép CC BY-SA 4.0. Bản tiếng Việt được dịch từ đề tiếng Anh chính thức.