APIO 2013

Viện Robot Voltron đã chế tạo \(n\) robot, đánh số từ \(1\) đến \(n\). Hai robot tương thích khi các nhãn của chúng là hai khoảng số nguyên liên tiếp. Ban đầu mỗi robot chỉ mang một nhãn. Khi nhiều robot hợp nhất, robot tổng hợp mang hai nhãn là nhãn nhỏ nhất và lớn nhất của các robot thành phần. Chẳng hạn, robot \(2\) có thể hợp nhất với robot \(1\) hoặc \(3\); robot \(2\)-\(3\) có thể hợp nhất với robot \(4\)-\(6\) để tạo robot \(2\)-\(6\). Mục tiêu cuối cùng là robot \(1\)-\(n\).

Các robot ở trong một căn phòng dạng lưới \(w\times h\), bao quanh bởi tường. Một số ô bị chặn và robot không thể đi vào. Mỗi robot chiếm đúng một ô, nhưng một ô có thể chứa nhiều robot. Ban đầu các robot ở những ô khác nhau.

Khi được đẩy theo một trong bốn hướng, robot đi thẳng theo hàng hoặc cột cho đến khi bị tường hay ô bị chặn cản lại. Sau khi dừng, nó hợp nhất với mọi robot tương thích cùng ô; quá trình tiếp tục cho tới khi không thể hợp nhất thêm.

Một số ô có bàn xoay theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ. Khi robot đi vào ô có bàn xoay, hướng chuyển động của nó lập tức quay \(90\) độ theo chiều của bàn. Nếu robot đang đứng trên bàn xoay khi được đẩy, nó quay \(90\) độ trước rồi mới rời ô, do đó hướng chuyển động vuông góc với hướng đẩy.

Tại mỗi thời điểm chỉ một robot được di chuyển. Hãy tìm số lần đẩy ít nhất để hợp nhất tất cả \(n\) robot, hoặc xác định rằng điều đó không thể thực hiện.

Dữ liệu vào

• Dòng đầu chứa \(n,w,h\).
• \(h\) dòng tiếp theo, mỗi dòng gồm \(w\) ký tự mô tả căn phòng:
• chữ số từ 1 đến 9: robot có nhãn tương ứng;
• x: ô bị chặn;
• A: bàn xoay ngược chiều kim đồng hồ;
• C: bàn xoay theo chiều kim đồng hồ;
• .: ô trống.

Dữ liệu ra

In số lần đẩy nhỏ nhất, hoặc -1 nếu không thể hợp nhất tất cả robot.

Ví dụ

4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...

5

Giải thích

Một phương án tối ưu gồm năm bước:

1. Đẩy robot \(3\) sang phải. Robot gặp bàn xoay ngược chiều kim đồng hồ, chuyển hướng lên trên và dừng trước tường.
2. Đẩy robot \(4\) lên trên. Nó dừng trước tường và hợp nhất với robot \(3\) thành robot \(3\)-\(4\).
3. Đẩy robot \(2\) lên trên. Nó gặp bàn xoay, rẽ ngược chiều kim đồng hồ rồi dừng trước tường.
4. Đẩy robot \(2\) sang phải. Vì đang ở trên bàn xoay, nó chuyển hướng lên trên, dừng ở góc và hợp nhất với robot \(1\) thành robot \(1\)-\(2\).
5. Đẩy robot \(3\)-\(4\) sang trái. Nó dừng ở góc và hợp nhất với robot \(1\)-\(2\).

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2013, bài Robots.

Happyland có \(N\) thị trấn, đánh số từ \(1\) đến \(N\), ban đầu được nối bởi \(M\) con đường hai chiều. Thị trấn \(1\) là trung tâm và có thể đi từ đó đến mọi thị trấn khác. Đường cũ thứ \(i\) thu phí \(c_i\) xu; mọi \(c_i\) đôi một khác nhau.

Gần đây có thêm \(K\) con đường mới do tỷ phú Greedy sở hữu. Ông được tự chọn phí cho các đường mới, các mức phí này không nhất thiết khác nhau.

Trong lễ hội sắp tới, có \(p_j\) người đi từ thị trấn \(j\) về thị trấn \(1\). Theo truyền thống, Greedy phải chọn một tập đường có tổng phí nhỏ nhất nhưng vẫn nối được mọi thị trấn với thị trấn \(1\), tức một cây khung nhỏ nhất theo mức phí. Nếu có nhiều cây khung nhỏ nhất, ông được chọn bất kỳ cây nào trong số đó.

Doanh thu trên một đường bằng phí của đường nhân với số người đi qua đường đó. Greedy chỉ nhận doanh thu từ \(K\) đường mới. Ông muốn đồng thời chọn mức phí cho các đường mới và chọn một cây khung nhỏ nhất sao cho tổng doanh thu từ các đường mới là lớn nhất. Hãy tính doanh thu tối đa này.

Dữ liệu vào

• Dòng đầu chứa \(N,M,K\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa \(a_i,b_i,c_i\), mô tả đường cũ hai chiều nối \(a_i\) với \(b_i\) có phí \(c_i\).
• \(K\) dòng tiếp theo, dòng thứ \(i\) chứa \(x_i,y_i\), mô tả một đường mới nối \(x_i\) với \(y_i\).
• Dòng cuối chứa \(N\) số \(p_1,p_2,\ldots,p_N\).

Dữ liệu ra

In tổng doanh thu lớn nhất Greedy có thể thu được.

Ràng buộc

• \(1\le N\le100\,000\).
• \(1\le M\le300\,000\).
• \(1\le K\le20\).
• \(1\le c_i,p_j\le10^6\).
• Các giá trị \(c_i\) đôi một khác nhau.
• Giữa hai thị trấn bất kỳ có nhiều nhất một con đường, tính cả đường cũ và đường mới.
• Có thể đi từ thị trấn \(1\) đến mọi thị trấn khác bằng các đường cũ.

Ví dụ

5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50

400

Giải thích

Greedy đặt phí đường mới \((1,3)\) bằng \(5\). Ông có thể chọn các đường \((3,5)\), \((1,2)\), \((2,4)\) và \((1,3)\), có tổng phí nhỏ nhất là \(14\). Có \(30+50\) người đi qua đường mới, nên doanh thu là \((30+50)\times5=400\).

Nếu đặt phí đường mới bằng \(10\), cây khung nhỏ nhất duy nhất dùng đường cũ \((2,3)\) thay cho \((1,3)\), nên đường mới không tạo doanh thu.

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2013, bài Toll.

Trong bài này, bạn đóng vai người ra đề và phải tạo dữ liệu để phân biệt hai chương trình. Ban tổ chức cung cấp hai bài toán đồ thị, tám phân nhóm và một số chương trình tưởng như giải được các bài đó. Với mỗi phân nhóm, hãy tạo một dữ liệu \(X\) sao cho:

1. Chương trình A không bị quá thời gian trên \(X\).
2. Chương trình B bị quá thời gian trên \(X\).

Mỗi chương trình duy trì biến counter xấp xỉ số phép toán. Một chương trình được xem là quá thời gian ngay khi counter vượt quá \(1\,000\,000\). Ban tổ chức ưu tiên dữ liệu nhỏ, với mục tiêu chứa không quá \(T\) số nguyên có dấu.

Mã nguồn C, C++ và Pascal của các thuật toán được cung cấp trong tệp đính kèm. Hệ thống chấm sử dụng đúng hành vi của bản C++.

Cách nộp bài

Đây là bài output-only. Nộp một tệp ZIP chứa tám tệp sau ở ngay thư mục gốc của tệp nén:

tasksauthor1.out
tasksauthor2.out
tasksauthor3.out
tasksauthor4.out
tasksauthor5.out
tasksauthor6.out
tasksauthor7.out
tasksauthor8.out

Tệp tasksauthorX.out là dữ liệu vào do bạn thiết kế cho phân nhóm \(X\). Nếu thiếu tệp, sai định dạng, vi phạm ràng buộc, chương trình A bị quá thời gian, hoặc chương trình B không bị quá thời gian thì phân nhóm đó được \(0\) điểm.

Nếu dữ liệu hợp lệ và phân biệt được hai chương trình, gọi \(F\) là số số nguyên trong tệp, \(S\) là điểm của phân nhóm và \(T\) là kích thước mục tiêu. Điểm nhận được là:

Do đó, nếu \(F\le T\) thì nhận đủ \(S\) điểm.

Các phân nhóm

Bài toán SSSP

Cho đồ thị có hướng có trọng số \(G\) và hai đỉnh \(s,t\). Gọi \(p(s,t)\) là trọng số đường đi ngắn nhất từ \(s\) đến \(t\). Nếu không thể đi từ \(s\) đến \(t\), quy ước \(p(s,t)=1\,000\,000\,000\). Dữ liệu gồm đồ thị và \(Q\) truy vấn \((s_k,t_k)\).

Tệp bắt đầu bằng số đỉnh \(V\). Các đỉnh được đánh số từ \(0\) đến \(V-1\). Sau đó có \(V\) dòng mô tả danh sách kề; dòng của đỉnh \(i\) bắt đầu bằng \(n_i\), tiếp theo là \(n_i\) cặp \((j,w)\) mô tả cạnh có hướng \(i\to j\) trọng số \(w\). Khối thứ hai bắt đầu bằng \(Q\), rồi đến \(Q\) dòng chứa \(s_k,t_k\).

Các số liên tiếp trên cùng dòng phải cách nhau bởi ít nhất một dấu cách. Dữ liệu phải thỏa mãn:

• \(0<V\le300\).
• \(n_i\ge0\).
• \(0\le j<V\).
• \(|w|<10^6\).
• \(0\le\sum_{i=0}^{V-1}n_i\le5\,000\).
• \(0<Q\le10\).
• \(0\le s_k,t_k<V\).
• Đồ thị không có chu trình âm.

Ví dụ minh họa dưới đây chứa \(15\) số nguyên, nhưng không phải tệp cần nộp cho một phân nhóm cụ thể.

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

Kết quả SSSP tương ứng là 3 và 1000000000; counter của ModifiedDijkstra bằng \(5\).

{{asset:apio13-tasksauthor-sssp}}

Bài toán Mystery

Cho đồ thị vô hướng \(G\) có \(V\) đỉnh và \(E\) cạnh. Hãy gán cho mỗi đỉnh một nhãn nguyên trong \([0,X-1]\) sao cho hai đầu mút của mọi cạnh có nhãn khác nhau, với \(X\) nhỏ nhất có thể.

Tệp bắt đầu bằng \(V,E\), sau đó là \(E\) dòng, mỗi dòng chứa một cạnh vô hướng \((a,b)\). Dữ liệu phải thỏa mãn:

• \(70<V<1\,000\).
• \(1\,500<E<10^6\).
• Với mọi cạnh: \(a\ne b\), \(0\le a,b<V\).
• Mỗi cạnh xuất hiện đúng một lần.

Ví dụ dưới đây chỉ để minh họa và không hợp lệ làm dữ liệu nộp vì \(V,E\) quá nhỏ. Tệp có \(12\) số nguyên; counter của RecursiveBacktracking bằng \(18\).

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

Một cách tô tối ưu dùng \(X=3\) với nhãn 0 1 2 1.

{{asset:apio13-tasksauthor-mystery}}

Hành vi các thuật toán

• FloydWarshall: thực hiện đúng \(V^3\) lượt lặp, mỗi lượt tăng counter một đơn vị, rồi trả lời các truy vấn.
• OptimizedBellmanFord: với mỗi truy vấn, lặp tối đa \(V-1\) lần trên toàn bộ danh sách cạnh; mỗi cạnh được xét làm tăng counter một đơn vị. Dừng sớm nếu một lượt không cập nhật khoảng cách.
• ModifiedDijkstra: với mỗi truy vấn, mỗi lần lấy một phần tử khỏi hàng đợi ưu tiên làm tăng counter một đơn vị. Thuật toán vẫn chạy đúng theo mã được cung cấp, kể cả khi đồ thị có trọng số âm nhưng không có chu trình âm.
• Gamble1: gán nhãn đỉnh \(i\) bằng \(i\) và đặt counter=0.
• Gamble2: gán nhãn đỉnh \(i\) bằng \(i\) và đặt counter=1000001.
• RecursiveBacktracking: thử \(X\) từ \(2\) đến \(V\), tô đỉnh \(0\) bằng \(0\), rồi thử các nhãn theo thứ tự nhỏ nhất cho các đỉnh kề; vị trí tăng counter được xác định chính xác bởi mã nguồn đính kèm.

Phân nhóm

Bảng Các phân nhóm ở trên là bảng điểm chính thức; tổng điểm là \(100\).

Nguồn

Asia-Pacific Informatics Olympiad 2013, bài Tasks Author. Tên tệp nộp được đổi từ định dạng .tgz của hệ thống gốc sang ZIP và tên tệp chuẩn của LQDOJ; bài toán, ràng buộc, bộ đếm và công thức điểm được giữ nguyên.