IOI 2017 - Ngày 1

Vài ngày nữa là tới Nowruz, năm mới của Ba Tư. Ông nội đã mời các thành viên trong gia đình đến khu vườn của mình, trong đó có \(k\) đứa trẻ. Để buổi gặp mặt thêm vui, ông muốn tổ chức một trò chơi trốn tìm.

Khu vườn được biểu diễn bằng một lưới gồm \(m\) hàng và \(n\) cột ô vuông đơn vị. Một số ô, có thể không có ô nào, bị chặn bởi đá; các ô còn lại được gọi là ô tự do. Hai ô được gọi là lân cận nếu chúng có chung cạnh. Mỗi ô có tối đa bốn ô lân cận: hai ô theo chiều ngang và hai ô theo chiều dọc. Ông nội muốn biến khu vườn thành một mê cung bằng cách trồng bụi cây vào một số ô tự do. Những ô được trồng bụi cây không còn là ô tự do nữa.

Một mê cung phải thỏa mãn tính chất sau: với mỗi cặp ô tự do \(a\) và \(b\), có đúng một đường đi đơn giữa chúng. Đường đi đơn từ \(a\) đến \(b\) là một dãy các ô tự do, trong đó ô đầu tiên là \(a\), ô cuối cùng là \(b\), tất cả các ô đều phân biệt và hai ô liên tiếp luôn lân cận nhau.

Một đứa trẻ có thể trốn trong một ô khi và chỉ khi ô đó là ô tự do và có đúng một ô lân cận tự do. Không có hai đứa trẻ nào trốn trong cùng một ô.

Cho bản đồ khu vườn, hãy giúp ông nội tạo ra một mê cung có nhiều chỗ trốn cho trẻ nhỏ.

Cách nộp bài

Đây là bài chỉ nộp kết quả (output-only), có tính điểm thành phần. Bạn được cung cấp \(10\) tệp đầu vào, mỗi tệp mô tả một khu vườn. Với mỗi tệp đầu vào, bạn cần nộp một tệp đầu ra chứa bản đồ mê cung tương ứng. Điểm của từng tệp phụ thuộc vào số đứa trẻ có thể trốn trong mê cung bạn tạo ra.

Bạn không phải nộp mã nguồn cho bài này.

Dữ liệu vào

Mỗi tệp đầu vào có định dạng như sau:

• Dòng \(1\) chứa ba số nguyên \(m\), \(n\), \(k\): số hàng, số cột của khu vườn và số đứa trẻ được mời.
• Dòng \(1+i\), với \(1 \le i \le m\), chứa hàng thứ \(i\) của lưới: một xâu dài \(n\), không chứa ký tự trắng, chỉ gồm . và #.

Ký tự . biểu diễn ô tự do; ký tự # biểu diễn ô có đá.

Dữ liệu ra

Mỗi tệp đầu ra gồm \(m\) dòng. Dòng \(i\), với \(1 \le i \le m\), chứa hàng thứ \(i\) của mê cung sau khi trồng bụi cây: một xâu dài \(n\), không chứa ký tự trắng, gồm các ký tự sau:

• .: ô tự do.
• #: ô có đá.
• X: ô có bụi cây. Chữ X phải viết hoa.

Ràng buộc

• \(1 \le m,n \le 1024\).

Cách tính điểm

Một tệp đầu ra hợp lệ phải thỏa mãn cả hai điều kiện:

• Bản đồ đầu ra giống bản đồ đầu vào, ngoại trừ việc có thể thay một số lượng tùy ý các ký tự . bằng X.
• Bản đồ đầu ra có tính chất của một mê cung như đã định nghĩa ở trên.

Nếu đầu ra không hợp lệ, bạn nhận \(0\) điểm cho bộ dữ liệu đó. Nếu đầu ra hợp lệ, gọi \(l\) là số đứa trẻ có thể trốn trong mê cung, tức số ô tự do có đúng một ô lân cận tự do. Điểm của bộ dữ liệu là

được làm tròn xuống đến hai chữ số sau dấu thập phân. Ở đây, \(k\) là số được cho trong tệp đầu vào.

Bạn nhận đủ \(10\) điểm cho một bộ dữ liệu khi và chỉ khi đầu ra là một mê cung có ít nhất \(k\) chỗ trốn. Với mỗi bộ dữ liệu, luôn tồn tại một phương án đạt \(10\) điểm.

Nếu phương án hợp lệ nhưng điểm sau khi làm tròn xuống vẫn bằng \(0\), hệ thống CMS sẽ hiển thị kết quả Wrong Answer.

Phân nhóm

Mỗi tệp đầu vào chính thức tương ứng với một subtask, có điểm tối đa là \(10\). Tổng điểm tối đa của bài là \(100\).

Ví dụ

Dữ liệu vào

4 5 5
....#
.#..#
...#.
....#

Một đầu ra hợp lệ

.X.X#
.#..#
...#X
XX..#

Mê cung này có \(l=4\) chỗ trốn, nên phương án nhận được

điểm. Các chỗ trốn được đánh dấu bằng O trong lưới dưới đây. Ký tự O chỉ dùng để minh họa, không được dùng trong tệp đầu ra.

OXOX#
.#.O#
...#X
XX.O#

Các đầu ra không hợp lệ

Đầu ra thứ nhất:

.XXX#
.#XX#
...#.
XX..#

Không có đường đi đơn giữa ô tự do ở góc trên bên trái và ô tự do ở cột ngoài cùng bên phải.

Đầu ra thứ hai:

...X#
.#.X#
...#X
XXXX#

Đầu ra thứ ba:

XXXX#
X#XX#
..X#X
..XX#

Trong mỗi đầu ra thứ hai và thứ ba, giữa mỗi cặp ô tự do phân biệt có đúng hai đường đi đơn khác nhau, nên không thỏa mãn tính chất của mê cung.

Maryam là một kỹ sư điện đang thiết kế hệ thống dây nối trên một tháp truyền thông. Trên tháp có các điểm kết nối ở những độ cao khác nhau. Mỗi đoạn dây nối hai điểm kết nối, và mỗi điểm có thể được nối với một số lượng tùy ý các đoạn dây. Có hai loại điểm kết nối: đỏ và xanh.

Trong bài toán này, tháp được xem như một đường thẳng. Các điểm kết nối đỏ và xanh nằm tại những tọa độ nguyên không âm trên đường thẳng đó. Độ dài của một đoạn dây bằng khoảng cách giữa hai điểm mà nó nối.

Hãy giúp Maryam tìm tổng độ dài dây nhỏ nhất trong một sơ đồ kết nối thỏa mãn: mỗi điểm kết nối có ít nhất một đoạn dây nối nó với một điểm kết nối khác màu.

Chi tiết cài đặt

Bạn cần cài đặt hàm C++ sau, được khai báo trong tệp wiring.h:

long long min_total_length(std::vector<int> r, std::vector<int> b);

• r: mảng gồm \(n\) phần tử, chứa tọa độ các điểm kết nối đỏ theo thứ tự tăng dần.
• b: mảng gồm \(m\) phần tử, chứa tọa độ các điểm kết nối xanh theo thứ tự tăng dần.

Hàm phải trả về tổng độ dài dây nhỏ nhất trong tất cả các sơ đồ kết nối hợp lệ. Giá trị trả về là số nguyên \(64\) bit, có kiểu long long trong C++.

Ràng buộc

• \(1 \le n,m \le 100\,000\).
• \(0 \le r[i] \le 10^9\) với mọi \(0 \le i \le n-1\).
• \(0 \le b[i] \le 10^9\) với mọi \(0 \le i \le m-1\).
• Mỗi mảng r và b được sắp xếp theo thứ tự tăng dần.
• Tất cả \(n+m\) giá trị trong hai mảng đôi một khác nhau.

Phân nhóm

Trình chấm mẫu

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

• Dòng \(1\): \(n\ m\).
• Dòng \(2\): \(r[0]\ r[1]\ \ldots\ r[n-1]\).
• Dòng \(3\): \(b[0]\ b[1]\ \ldots\ b[m-1]\).

Trình chấm mẫu in giá trị trả về của min_total_length trên một dòng duy nhất.

Ví dụ

4 5
1 2 3 7
0 4 5 9 10

10

min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10});

Arezou và em trai Borzou là hai chị em sinh đôi. Nhân dịp sinh nhật, họ được tặng một bộ đồ chơi tàu hỏa và dùng nó để xây dựng một hệ thống gồm \(n\) ga tàu cùng \(m\) đường ray một chiều. Các ga được đánh số từ \(0\) đến \(n-1\). Mỗi đường ray xuất phát từ một ga và kết thúc tại chính ga đó hoặc một ga khác. Từ mỗi ga có ít nhất một đường ray đi ra.

Một số ga là ga nạp pin. Khi tàu đến một ga nạp pin, pin của tàu được nạp đầy. Một lần nạp đầy cung cấp đủ năng lượng để tàu đi hết \(n\) đường ray liên tiếp. Nếu không được nạp lại, tàu sẽ hết năng lượng khi vừa bắt đầu đi vào đường ray thứ \(n+1\) kể từ lần nạp gần nhất.

Tại mỗi ga có một nút điều khiển có thể trỏ đến bất kỳ đường ray nào xuất phát từ ga đó. Khi rời một ga, tàu đi theo đường ray mà nút điều khiển tại ga ấy đang trỏ đến.

Hai chị em chơi một trò chơi với chiếc tàu này. Họ chia tất cả các ga cho nhau: mỗi ga thuộc sở hữu của Arezou hoặc Borzou. Chỉ có một chiếc tàu. Khi trò chơi bắt đầu, tàu ở ga \(s\) với pin đã được nạp đầy. Người sở hữu ga \(s\) thiết lập nút điều khiển tại đó, chọn một đường ray đi ra, rồi cho tàu chạy.

Mỗi khi tàu đến một ga lần đầu tiên, người sở hữu ga ấy thiết lập nút điều khiển tại ga. Sau khi được thiết lập, nút điều khiển không được thay đổi trong suốt trò chơi. Vì vậy, khi quay lại một ga đã ghé qua, tàu luôn rời ga bằng đúng đường ray đã chọn trước đó.

Do số ga hữu hạn, cuối cùng hành trình của tàu sẽ lặp lại theo một chu trình. Một chu trình gồm các ga đôi một khác nhau

trong đó tàu đi từ \(c[i]\) đến \(c[i+1]\) với mọi \(0\le i<k-1\), rồi từ \(c[k-1]\) về \(c[0]\). Chu trình có thể chỉ gồm một ga, tức là \(k=1\), nếu đường ray được chọn đi từ \(c[0]\) trở lại chính ga đó.

Arezou thắng nếu tàu có thể chạy mãi mãi; Borzou thắng nếu tàu hết pin. Nói cách khác, nếu chu trình có ít nhất một ga nạp pin thì tàu có thể liên tục nạp pin và chạy vô hạn, nên Arezou thắng. Nếu chu trình không có ga nạp pin, tàu sẽ hết pin, có thể sau khi đi quanh chu trình vài vòng, và Borzou thắng.

Cho mô tả hệ thống đường tàu. Hai chị em sẽ chơi \(n\) trò chơi độc lập; ở trò chơi thứ \(s\), với \(0\le s\le n-1\), tàu bắt đầu tại ga \(s\). Với mỗi trò chơi, hãy xác định liệu Arezou có chiến thuật bảo đảm chiến thắng, bất kể Borzou chơi như thế nào hay không.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau, được khai báo trong tệp train.h:

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v);

• a: mảng độ dài \(n\). Với mỗi \(0\le i\le n-1\), \(a[i]=1\) nếu Arezou sở hữu ga \(i\); \(a[i]=0\) nếu Borzou sở hữu ga đó.
• r: mảng độ dài \(n\). Với mỗi \(0\le i\le n-1\), \(r[i]=1\) nếu ga \(i\) là ga nạp pin; ngược lại, \(r[i]=0\).
• u, v: hai mảng độ dài \(m\). Với mỗi \(0\le i\le m-1\), có một đường ray một chiều từ ga \(u[i]\) đến ga \(v[i]\).

Hàm phải trả về một mảng \(w\) có đúng \(n\) phần tử. Với mỗi \(0\le i\le n-1\), \(w[i]=1\) nếu Arezou có thể bảo đảm chiến thắng khi tàu bắt đầu ở ga \(i\), bất kể cách chơi của Borzou; ngược lại, \(w[i]=0\).

Chương trình chấm sẽ gọi hàm này và nhận kết quả trả về. Bạn không cần cài đặt hàm main.

Ví dụ

Xét lời gọi:

who_wins({0, 1}, {1, 0}, {0, 0, 1, 1}, {0, 1, 0, 1});

Có hai ga tàu. Borzou sở hữu ga \(0\), là ga nạp pin. Arezou sở hữu ga \(1\), không phải ga nạp pin. Bốn đường ray là \((0,0)\), \((0,1)\), \((1,0)\) và \((1,1)\), trong đó \((i,j)\) biểu diễn đường ray một chiều từ ga \(i\) đến ga \(j\).

Nếu tàu bắt đầu tại ga \(0\) và Borzou chọn đường ray \((0,0)\), tàu sẽ chạy mãi trên đường ray này vì ga \(0\) có thể nạp pin, nên Arezou thắng. Nếu Borzou chọn \((0,1)\), Arezou có thể chọn \((1,0)\) tại ga \(1\). Khi đó, tàu chạy vô hạn theo chu trình qua hai ga và được nạp pin mỗi khi về ga \(0\). Vì thế, Arezou luôn có thể thắng khi tàu bắt đầu tại ga \(0\).

Tương tự, khi tàu bắt đầu tại ga \(1\), Arezou chọn \((1,0)\) và vẫn bảo đảm chiến thắng. Do đó, hàm phải trả về \([1,1]\).

Ràng buộc

• \(1\le n\le 5000\).
• \(n\le m\le 20\,000\).
• \(a[i],r[i]\in\{0,1\}\) với mọi \(0\le i\le n-1\).
• Có ít nhất một ga nạp pin.
• Từ mỗi ga có ít nhất một đường ray đi ra.
• Đường ray có thể xuất phát và kết thúc tại cùng một ga, tức là \(u[i]=v[i]\).
• Các đường ray đôi một khác nhau: không tồn tại hai chỉ số \(0\le i<j\le m-1\) sao cho đồng thời \(u[i]=u[j]\) và \(v[i]=v[j]\).
• \(0\le u[i],v[i]\le n-1\) với mọi \(0\le i\le m-1\).

Giới hạn thời gian: \(2\) giây. Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

Chương trình chấm mẫu

Chương trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(n\ m\).
• Dòng \(2\): \(a[0]\ a[1]\ \ldots\ a[n-1]\).
• Dòng \(3\): \(r[0]\ r[1]\ \ldots\ r[n-1]\).
• Dòng \(4+i\), với \(0\le i\le m-1\): \(u[i]\ v[i]\).

Chương trình chấm mẫu in mảng do who_wins trả về trên một dòng, theo thứ tự \(w[0]\ w[1]\ \ldots\ w[n-1]\), các phần tử cách nhau bằng dấu cách.

Dữ liệu vào mẫu

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

Kết quả ra mẫu

1 1