APIO 2021

Pak Dengklek đang đứng tại một ô, được gọi là ô xuất phát, trên một lưới hình lục giác vô hạn. Hai ô trong lưới hình lục giác được gọi là lân cận nếu chúng có chung một cạnh. Trong một bước, Pak Dengklek có thể đi từ một ô sang một trong các ô lân cận của nó theo một trong sáu hướng có thể, được đánh số từ \(1\) đến \(6\) như trong hình dưới đây.

{{asset:apio21hexagon/hexagon-directions.png}}

Pak Dengklek sẽ tạo ra một lãnh thổ bằng cách đi theo một lộ trình gồm dãy các ô được thăm bởi \(N\) phép dịch chuyển. Ở phép dịch chuyển thứ \(i\), Pak Dengklek chọn hướng \(D[i]\), sau đó thực hiện \(L[i]\) bước theo hướng đã chọn. Lộ trình có các tính chất sau:

• Lộ trình đóng, nghĩa là ô ở cuối dãy trùng với ô ở đầu dãy.
• Lộ trình đơn, nghĩa là mỗi ô được thăm nhiều nhất một lần, ngoại trừ ô xuất phát được thăm đúng hai lần (lúc bắt đầu và lúc kết thúc).
• Lộ trình lộ ra, nghĩa là mỗi ô trên lộ trình lân cận với ít nhất một ô không nằm trên lộ trình và không nằm bên trong.
• Một ô được gọi là bên trong nếu nó không nằm trên lộ trình và từ ô đó chỉ có thể thăm được hữu hạn ô bằng bất kỳ dãy bước đi nào không đi qua ô nào trên lộ trình.

Dưới đây là một ví dụ về lộ trình Pak Dengklek có thể đi:

• Ô được đánh số \(1\) (tô màu hồng) là ô xuất phát (và kết thúc).
• Các ô được đánh số (tô màu xanh lam nhạt) là các ô trên lộ trình, được đánh số theo thứ tự được thăm.
• Các ô được gạch chéo (tô màu xanh lam đậm) là các ô bên trong.

{{asset:apio21hexagon/hexagon-path.png}}

Lãnh thổ được hình thành gồm tất cả các ô nằm trên lộ trình hoặc nằm bên trong. Khoảng cách của một ô \(c\) trong lãnh thổ là số bước ít nhất cần thiết để đi từ ô xuất phát đến ô \(c\) mà chỉ đi qua các ô trong lãnh thổ. Điểm của một ô trong lãnh thổ được định nghĩa là \(A + d \times B\), trong đó \(A\) và \(B\) là các hằng số do Pak Dengklek xác định trước, còn \(d\) là khoảng cách của ô đó. Hình dưới đây minh họa khoảng cách của mỗi ô trong lãnh thổ được tạo bởi lộ trình ở ví dụ trên.

{{asset:apio21hexagon/hexagon-distances.png}}

Hãy giúp Pak Dengklek tính tổng điểm của tất cả các ô trong lãnh thổ được hình thành bởi \(N\) phép dịch chuyển mà Pak Dengklek sẽ thực hiện. Vì tổng điểm có thể rất lớn, hãy tính kết quả theo modulo \(10^9 + 7\).

Chi tiết cài đặt

Thí sinh cần cài đặt hàm sau:

int draw_territory(int N, int A, int B, std::vector<int> D,
                   std::vector<int> L);

• \(N\): số phép dịch chuyển.
• \(A\), \(B\): các hằng số dùng để tính điểm.
• \(D\): mảng độ dài \(N\), trong đó \(D[i]\) là hướng của phép dịch chuyển thứ \(i\).
• \(L\): mảng độ dài \(N\), trong đó \(L[i]\) là số bước được thực hiện trong phép dịch chuyển thứ \(i\).
• Hàm phải trả về tổng điểm của tất cả các ô trong lãnh thổ theo modulo \(10^9 + 7\).
• Hàm được gọi đúng một lần.

Ví dụ

Xét lời gọi sau:

draw_territory(17, 2, 3,
               {1, 2, 3, 4, 5, 4, 3, 2, 1, 6, 2, 3, 4, 5, 6, 6, 1},
               {1, 2, 2, 1, 1, 1, 1, 2, 3, 2, 3, 1, 6, 3, 3, 2, 1});

Các phép dịch chuyển chính là các phép dịch chuyển được minh họa trong phần mô tả. Bảng sau liệt kê điểm của mỗi ô ứng với mọi khoảng cách có thể có trong lãnh thổ.

Tổng điểm là \(2 + 20 + 40 + 66 + 56 + 51 + 80 + 92 + 130 + 87 + 128 + 175 + 76 = 1003\). Vì vậy, hàm draw_territory phải trả về \(1003\).

Ràng buộc

• \(3 \le N \le 200\,000\).
• \(0 \le A, B \le 10^9\).
• \(1 \le D[i] \le 6\) với mọi \(0 \le i \le N - 1\).
• \(1 \le L[i]\) với mọi \(0 \le i \le N - 1\).
• Tổng tất cả các phần tử của \(L\) không vượt quá \(10^9\).
• Lộ trình là đóng, đơn và lộ ra.

Phân nhóm

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\): \(N\ A\ B\).
• Dòng \(2 + i\) (\(0 \le i \le N - 1\)): \(D[i]\ L[i]\).

Trình chấm mẫu ghi kết quả theo định dạng sau:

• Dòng \(1\): giá trị trả về của hàm draw_territory.

17 2 3
1 1
2 2
3 2
4 1
5 1
4 1
3 1
2 2
1 3
6 2
2 3
3 1
4 6
5 3
6 3
6 2
1 1

1003

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2021: Hexagonal Territory.

Trong rừng mưa nhiệt đới Sumatra, có \(N\) cây nằm liên tiếp trên một hàng, được đánh số từ \(0\) đến \(N - 1\) theo thứ tự từ trái sang phải. Tất cả các cây có chiều cao đôi một khác nhau; cây \(i\) có chiều cao \(H[i]\).

Pak Dengklek đang huấn luyện một con đười ươi nhảy từ cây này sang cây khác. Trong một lần nhảy, đười ươi có thể nhảy từ ngọn cây hiện tại sang ngọn cây gần nhất ở bên trái hoặc bên phải có chiều cao lớn hơn cây hiện tại. Cụ thể, nếu đười ươi đang ở cây \(x\), nó có thể nhảy sang cây \(y\) khi và chỉ khi một trong hai điều sau được thỏa mãn:

• \(y\) là số nguyên không âm lớn nhất nhỏ hơn \(x\) sao cho \(H[y] > H[x]\); hoặc
• \(y\) là số nguyên không âm nhỏ nhất lớn hơn \(x\) sao cho \(H[y] > H[x]\).

Pak Dengklek có \(Q\) phương án tập nhảy. Mỗi phương án được biểu diễn bằng bốn số nguyên \(A\), \(B\), \(C\) và \(D\) (\(A \le B < C \le D\)). Với mỗi phương án, Pak Dengklek muốn biết liệu đười ươi có thể bắt đầu tại một cây \(s\) nào đó (\(A \le s \le B\)) và kết thúc tại một cây \(e\) nào đó (\(C \le e \le D\)) bằng một dãy các bước nhảy hay không. Nếu có thể, Pak Dengklek muốn biết số bước nhảy ít nhất mà đười ươi cần thực hiện cho phương án đó.

Chi tiết cài đặt

Thí sinh cần cài đặt hai hàm sau:

void init(int N, std::vector<int> H);

• \(N\): số lượng cây.
• \(H\): mảng độ dài \(N\), trong đó \(H[i]\) là chiều cao của cây \(i\).
• Hàm này được gọi đúng một lần, trước mọi lời gọi đến hàm minimum_jumps.
• Hàm này không trả về giá trị.

int minimum_jumps(int A, int B, int C, int D);

• \(A\), \(B\): phạm vi các cây mà đười ươi được phép bắt đầu.
• \(C\), \(D\): phạm vi các cây mà đười ươi được phép kết thúc.
• Hàm phải trả về số bước nhảy ít nhất để hoàn thành phương án, hoặc trả về \(-1\) nếu không thể hoàn thành.
• Hàm này được gọi đúng \(Q\) lần.

Ví dụ

Xét lời gọi sau:

init(7, {3, 2, 1, 6, 4, 5, 7});

Sau khi khởi tạo, xét lời gọi:

minimum_jumps(4, 4, 6, 6);

Đười ươi phải bắt đầu tại cây \(4\) (cao \(4\)) và kết thúc tại cây \(6\) (cao \(7\)). Một cách đạt số bước nhảy ít nhất là trước tiên nhảy đến cây \(3\) (cao \(6\)), rồi nhảy đến cây \(6\). Một cách khác là nhảy đến cây \(5\) (cao \(5\)), rồi nhảy đến cây \(6\). Vì vậy, hàm minimum_jumps phải trả về \(2\).

Xét một lời gọi khác:

minimum_jumps(1, 3, 5, 6);

Đười ươi phải bắt đầu tại cây \(1\) (cao \(2\)), cây \(2\) (cao \(1\)) hoặc cây \(3\) (cao \(6\)), và phải kết thúc tại cây \(5\) (cao \(5\)) hoặc cây \(6\) (cao \(7\)). Cách duy nhất đạt số bước nhảy ít nhất là bắt đầu từ cây \(3\), sau đó nhảy đến cây \(6\) chỉ bằng một lần nhảy. Vì vậy, hàm minimum_jumps phải trả về \(1\).

Xét một lời gọi khác:

minimum_jumps(0, 1, 2, 2);

Đười ươi phải bắt đầu tại cây \(0\) (cao \(3\)) hoặc cây \(1\) (cao \(2\)), và phải kết thúc tại cây \(2\) (cao \(1\)). Vì cây \(2\) là cây thấp nhất nên không thể nhảy đến cây này từ bất kỳ cây nào cao hơn nó. Vì vậy, hàm minimum_jumps phải trả về \(-1\).

Ràng buộc

• \(2 \le N \le 200\,000\).
• \(1 \le Q \le 100\,000\).
• \(1 \le H[i] \le N\) với mọi \(0 \le i \le N - 1\).
• \(H[i] \ne H[j]\) với mọi \(0 \le i < j \le N - 1\).
• \(0 \le A \le B < C \le D \le N - 1\).

Phân nhóm

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\): \(N\ Q\).
• Dòng \(2\): \(H[0]\ H[1]\ \ldots\ H[N - 1]\).
• Dòng \(3 + i\) (\(0 \le i \le Q - 1\)): \(A\ B\ C\ D\) cho lời gọi thứ \(i\) đến hàm minimum_jumps.

Trình chấm mẫu ghi kết quả theo định dạng sau:

• Dòng \(1 + i\) (\(0 \le i \le Q - 1\)): giá trị trả về của lời gọi thứ \(i\) đến hàm minimum_jumps.

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

2
1
-1

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2021: Rainforest Jumps.

Thành phố Surabaya có \(N\) nút giao thông, được đánh số từ \(0\) đến \(N - 1\). Các nút giao thông được nối với nhau bởi \(N - 1\) con đường hai chiều, được đánh số từ \(0\) đến \(N - 2\), sao cho có đúng một đường đi giữa hai nút giao thông bất kỳ qua các con đường này. Con đường \(i\) (\(0 \le i \le N - 2\)) nối nút giao thông \(U[i]\) và \(V[i]\).

Để nâng cao nhận thức về môi trường, Pak Dengklek, với vai trò là thị trưởng thành phố Surabaya, dự định tổ chức một Ngày Không Ô tô. Để khuyến khích sự kiện này, Pak Dengklek sẽ tổ chức đóng đường. Đầu tiên, Pak Dengklek chọn một số nguyên không âm \(k\), sau đó đóng một số con đường sao cho mỗi nút giao thông được nối trực tiếp với không quá \(k\) con đường chưa bị đóng. Chi phí để đóng con đường \(i\) là \(W[i]\).

Hãy giúp Pak Dengklek tìm tổng chi phí nhỏ nhất để đóng đường cho mỗi số nguyên không âm \(k\) có thể có (\(0 \le k \le N - 1\)).

Chi tiết cài đặt

Thí sinh cần cài đặt hàm sau:

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W);

• \(N\): số lượng nút giao thông của thành phố Surabaya.
• \(U\) và \(V\): hai mảng độ dài \(N - 1\), trong đó nút giao thông \(U[i]\) và \(V[i]\) được nối với nhau bởi con đường \(i\).
• \(W\): mảng độ dài \(N - 1\), trong đó \(W[i]\) là chi phí để đóng con đường \(i\).
• Hàm phải trả về đúng một mảng độ dài \(N\). Với mỗi \(k\) (\(0 \le k \le N - 1\)), phần tử thứ \(k\) là tổng chi phí nhỏ nhất để đóng đường sao cho mỗi nút giao thông được nối trực tiếp với không quá \(k\) con đường chưa bị đóng.
• Hàm được gọi đúng một lần.

Ví dụ

Ví dụ 1

Xét lời gọi sau:

minimum_closure_costs(5, {0, 0, 0, 2}, {1, 2, 3, 4}, {1, 4, 3, 2});

Lời gọi này biểu diễn \(5\) nút giao thông và \(4\) con đường nối các cặp nút giao thông \((0, 1)\), \((0, 2)\), \((0, 3)\) và \((2, 4)\), với chi phí đóng đường lần lượt là \(1\), \(4\), \(3\) và \(2\).

{{asset:apio21roads/roads-1.png}}

Để đạt được chi phí nhỏ nhất:

• Nếu Pak Dengklek chọn \(k = 0\), tất cả các con đường phải bị đóng, với tổng chi phí \(1 + 4 + 3 + 2 = 10\).
• Nếu Pak Dengklek chọn \(k = 1\), con đường \(0\) và con đường \(1\) phải bị đóng, với tổng chi phí \(1 + 4 = 5\).
• Nếu Pak Dengklek chọn \(k = 2\), con đường \(0\) phải bị đóng, với tổng chi phí \(1\).
• Nếu Pak Dengklek chọn \(k = 3\) hoặc \(k = 4\), không cần đóng con đường nào.

Vì vậy, hàm minimum_closure_costs phải trả về \([10, 5, 1, 0, 0]\).

Ví dụ 2

Xét lời gọi sau:

minimum_closure_costs(4, {0, 2, 0}, {1, 0, 3}, {5, 10, 5});

Lời gọi này biểu diễn \(4\) nút giao thông và \(3\) con đường nối các cặp nút giao thông \((0, 1)\), \((2, 0)\) và \((0, 3)\), với chi phí đóng đường lần lượt là \(5\), \(10\) và \(5\).

{{asset:apio21roads/roads-2.png}}

Để đạt được chi phí nhỏ nhất:

• Nếu Pak Dengklek chọn \(k = 0\), tất cả các con đường phải bị đóng, với tổng chi phí \(5 + 10 + 5 = 20\).
• Nếu Pak Dengklek chọn \(k = 1\), con đường \(0\) và con đường \(2\) phải bị đóng, với tổng chi phí \(5 + 5 = 10\).
• Nếu Pak Dengklek chọn \(k = 2\), con đường \(0\) hoặc con đường \(2\) phải bị đóng, với tổng chi phí \(5\).
• Nếu Pak Dengklek chọn \(k = 3\), không cần đóng con đường nào.

Vì vậy, hàm minimum_closure_costs phải trả về \([20, 10, 5, 0]\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(0 \le U[i], V[i] \le N - 1\) với mọi \(0 \le i \le N - 2\).
• Có thể di chuyển giữa mọi cặp nút giao thông qua các con đường này.
• \(1 \le W[i] \le 10^9\) với mọi \(0 \le i \le N - 2\).

Phân nhóm

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\): \(N\).
• Dòng \(2 + i\) (\(0 \le i \le N - 2\)): \(U[i]\ V[i]\ W[i]\).

Trình chấm mẫu ghi ra một dòng duy nhất chứa mảng do hàm minimum_closure_costs trả về.

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

10 5 1 0 0

4
0 1 5
2 0 10
0 3 5

20 10 5 0

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2021: Road Closures.