BOI 2014 - Ngày 1

Tình hình tội phạm ở thành phố Bytemore đang trở nên nghiêm trọng. Những vụ cướp xảy ra hằng ngày, và một cảnh sát tuần tra phải đuổi theo tên cướp qua các con hẻm nối những góc phố. Vì thuộc đường hơn cảnh sát, những tên cướp thường trốn thoát. Sở cảnh sát đã lập bản đồ thành phố và muốn dùng máy tính để tìm chiến lược truy đuổi.

Cuộc truy đuổi giữa một cảnh sát và một tên cướp được mô hình hóa như sau:

1. Cảnh sát chọn một góc phố để tuần tra.
2. Tên cướp biết vị trí cảnh sát và chọn một góc phố để thực hiện vụ cướp. Kể từ đây, cả hai luôn biết vị trí của nhau.
3. Trong lượt của mình, cảnh sát có thể đi đến một góc phố kề, tức là được nối với vị trí hiện tại bằng một con hẻm, hoặc đứng yên.
4. Trong lượt của mình, tên cướp phải đi đến một góc phố kề. Khác với cảnh sát, tên cướp không được đứng yên.
5. Hai bên lần lượt đi, bắt đầu bằng cảnh sát. Nếu sau lượt đi của một trong hai bên, họ ở cùng một góc phố, cảnh sát bắt được tên cướp. Nếu một trạng thái lặp lại, tên cướp trốn thoát. Một trạng thái gồm vị trí của cả hai người và bên sẽ đi tiếp; trạng thái lặp lại tương ứng với việc tên cướp có thể tránh cảnh sát mãi mãi.

Cho bản đồ thành phố, hãy xác định liệu cảnh sát có thể bảo đảm bắt được tên cướp hay không. Nếu có, chương trình phải thực hiện các nước đi của cảnh sát để bắt hắn. Luôn giả sử tên cướp chơi tối ưu.

Cài đặt

Đây là bài lập trình theo giao diện hàm. Với giao diện C++, nộp tệp mã nguồn có #include "coprobber.h" và cài đặt hai hàm sau; không viết hàm main:

int start(int N, bool A[MAX_N][MAX_N]);
int nextMove(int R);

Hằng MAX_N bằng \(500\).

Hàm start nhận:

• \(N\): số góc phố, được đánh số từ \(0\) đến \(N-1\).
• \(A\): ma trận kề. Với \(0 \le i,j<N\), A[i][j] bằng true nếu có con hẻm nối \(i\) và \(j\), và bằng false nếu không có.

Mọi con hẻm đều đi được theo hai chiều: A[i][j] == A[j][i]. Không có hẻm nối một góc phố với chính nó, nên A[i][i] luôn bằng false. Có thể đi từ một góc phố bất kỳ đến mọi góc phố khác qua các con hẻm.

Nếu có thể bảo đảm bắt được tên cướp, start phải trả về số hiệu góc phố mà cảnh sát chọn làm vị trí ban đầu. Nếu không thể, hàm phải trả về \(-1\).

Hàm nextMove(R) nhận vị trí hiện tại \(R\) của tên cướp và phải trả về góc phố mà cảnh sát đứng sau lượt đi của mình.

start được gọi đúng một lần, trước mọi lần gọi nextMove. Nếu start trả về \(-1\), nextMove không được gọi. Ngược lại, nextMove được gọi nhiều lần cho đến khi một trong các trường hợp sau xảy ra: trả về nước đi không hợp lệ, trạng thái lặp lại, hoặc tên cướp bị bắt.

Gói thử nghiệm kèm theo cung cấp giao diện C++ và một chương trình chấm mẫu được dựng lại từ mô tả này. Chương trình chấm mẫu dùng để thử trên máy cá nhân.

Ràng buộc

• \(2 \le N \le 500\).
• Ma trận \(A\) mô tả một đồ thị vô hướng liên thông, không có khuyên.
• Tên cướp phải di chuyển trong mỗi lượt; cảnh sát được phép đứng yên.

Phân nhóm

1. 16 điểm: \(2 \le N \le 500\). Giữa mỗi cặp góc phố có đúng một đường đi đơn qua các con hẻm; mạng lưới là một cây.

2. 14 điểm: \(2 \le N \le 500\). Mạng lưới có dạng lưới chữ nhật với ít nhất hai hàng và hai cột. Các góc phố được đánh số liên tiếp từ trái sang phải trong mỗi hàng, các hàng từ trên xuống dưới. Cụ thể, với lưới có \(w\) cột, góc ở hàng \(r\), cột \(c\) có số hiệu \(rw+c\) (hàng và cột bắt đầu từ \(0\)); hai góc nối nhau khi kề theo chiều ngang hoặc dọc.

   

3. 30 điểm: \(2 \le N \le 100\).

4. 40 điểm: \(2 \le N \le 500\).

Bài làm cần đáp ứng hai yêu cầu: xác định đúng liệu cảnh sát có thể bắt được tên cướp hay không; và nếu có thể thì thực sự bắt được tên cướp bằng các nước đi đã trả về.

Trong phân nhóm 1 và 2, phải đáp ứng cả hai yêu cầu mới được điểm. Trong phân nhóm 3 và 4, nếu chỉ đáp ứng yêu cầu thứ nhất, bài làm được 30% số điểm của phân nhóm. Để chỉ lấy điểm phần xác định, có thể kết thúc bằng cách trả về một nước đi không hợp lệ, chẳng hạn trả về \(-1\) trong nextMove.

Muốn được bất kỳ số điểm nào, chương trình vẫn phải đáp ứng các giới hạn thực thi và không xảy ra lỗi khi chạy.

Ví dụ

start(4, [[0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]) -> 3
nextMove(1) -> 3
nextMove(0) -> 0

Thử nghiệm

Chương trình chấm mẫu đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu chứa \(N\).
• \(N\) dòng tiếp theo chứa ma trận \(A\), mỗi dòng gồm \(N\) số \(0\) hoặc \(1\). Ma trận đối xứng và các phần tử trên đường chéo chính bằng \(0\).
• Dòng tiếp theo chứa \(1\) nếu cảnh sát có thể bắt được tên cướp, hoặc \(0\) nếu không thể.
• Nếu giá trị trên bằng \(1\), có thêm \(N\) dòng mô tả chiến lược tên cướp, mỗi dòng gồm \(N+1\) số nguyên từ \(0\) đến \(N-1\).

Trong bảng chiến lược, chỉ số hàng và cột bắt đầu từ \(0\). Giá trị tại hàng \(c\), cột \(r<N\) là góc phố mà tên cướp đi tới khi đến lượt hắn, cảnh sát ở \(c\) và tên cướp ở \(r\). Các phần tử đường chéo bị bỏ qua vì khi đó tên cướp đã bị bắt. Giá trị cuối cùng trên hàng \(c\) là vị trí ban đầu của tên cướp khi cảnh sát bắt đầu ở \(c\).

Tệp sample1.in mô tả ba góc phố đôi một nối với nhau:

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

Tệp sample2.in tương ứng với ví dụ gọi hàm ở trên:

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

Với chương trình chấm mẫu kèm theo, kết quả OK biểu thị hoàn thành yêu cầu; PARTFAIL biểu thị xác định đúng khả năng bắt nhưng chưa bắt được tên cướp; FAIL biểu thị không đạt. Điểm phần xác định còn phụ thuộc phân nhóm như đã nêu ở trên. Đây là kết quả của chương trình chấm mẫu; hai hàm bạn cài đặt chỉ cần trả về các giá trị theo giao diện.

Ba người bạn thích chơi trò chơi sau. Người thứ nhất chọn một xâu \(S\). Người thứ hai tạo xâu \(T\) bằng cách ghép hai bản sao của \(S\). Cuối cùng, người thứ ba chèn đúng một chữ cái vào đầu, cuối hoặc một vị trí bất kỳ bên trong \(T\), tạo thành xâu \(U\).

Cho xâu \(U\), hãy khôi phục xâu \(S\) ban đầu.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\), độ dài của xâu \(U\).

Dòng thứ hai chứa xâu \(U\) gồm \(N\) chữ cái tiếng Anh in hoa từ A đến Z.

Dữ liệu ra

In ra xâu \(S\) ban đầu. Có hai trường hợp ngoại lệ:

• Nếu không thể tạo ra \(U\) bằng cách trên, in NOT POSSIBLE.
• Nếu có nhiều xâu \(S\) khác nhau có thể tạo ra \(U\), in NOT UNIQUE.

Ràng buộc

• \(2 \le N \le 2\,000\,001\).
• Mọi ký tự của \(U\) là chữ cái tiếng Anh in hoa.

Phân nhóm

1. 35 điểm: \(2 \le N \le 2001\).
2. 65 điểm: \(2 \le N \le 2\,000\,001\).

Ví dụ

7
ABXCABC

ABC

6
ABCDEF

NOT POSSIBLE

9
ABABABABA

NOT UNIQUE

Adam viết lên bảng một dãy gồm \(K\) số nguyên dương liên tiếp, bắt đầu từ \(N\). Khi Adam rời đi, Billy xóa các chữ số của mỗi số, chỉ giữ lại đúng một chữ số. Như vậy, Billy tạo ra một dãy gồm \(K\) chữ số.

Cho dãy chữ số còn lại trên bảng, hãy tìm giá trị nhỏ nhất của \(N\) có thể là số đầu tiên trong dãy ban đầu.

Dữ liệu vào

Dòng đầu chứa số nguyên \(K\), độ dài của dãy.

Dòng thứ hai chứa \(K\) số nguyên \(B_1, B_2, \ldots, B_K\) theo thứ tự trên bảng. Chữ số \(B_i\) phải xuất hiện trong cách viết thập phân của số \(N+i-1\).

Dữ liệu ra

In ra một số nguyên: giá trị nhỏ nhất của \(N\) có thể là số đầu tiên trong dãy ban đầu.

Ràng buộc

• \(1 \le K \le 100\,000\).
• \(0 \le B_i \le 9\) với mọi \(1 \le i \le K\).
• \(N\) là số nguyên dương.

Phân nhóm

1. 9 điểm: \(1 \le K \le 1000\) và đáp án không vượt quá \(1000\).
2. 33 điểm: \(1 \le K \le 1000\).
3. 25 điểm: \(1 \le K \le 100\,000\) và tất cả phần tử của dãy đã cho bằng nhau.
4. 33 điểm: \(1 \le K \le 100\,000\).

Ví dụ

6
7 8 9 5 1 2

47