IOI 2006 - Ngày 2

Thành phố Mexico được xây dựng trong một thung lũng đẹp mang tên Thung lũng Mexico, nơi phần lớn diện tích trước kia là một hồ nước. Khoảng năm 1300, các thủ lĩnh tôn giáo Aztec ra lệnh san lấp phần giữa hồ để xây dựng kinh đô của đế chế. Ngày nay, hồ đã bị lấp hoàn toàn.

Trước khi người Aztec đến, có \(c\) thành phố nằm trên bờ, xung quanh hồ. Một số cặp thành phố thiết lập thỏa thuận thương mại và vận chuyển hàng hóa qua lại bằng thuyền. Có thể nối hai thành phố bất kỳ bằng một đoạn thẳng đi qua hồ.

Các vị vua quyết định tổ chức lại hoạt động buôn bán bằng một tuyến đường thương mại nối tất cả các thành phố quanh hồ. Tuyến đường phải thỏa mãn các yêu cầu sau:

• Bắt đầu tại một thành phố bất kỳ, đi qua tất cả các thành phố, rồi kết thúc tại một thành phố khác với thành phố xuất phát.
• Mỗi thành phố được ghé thăm đúng một lần.
• Hai thành phố được ghé thăm liên tiếp phải có thỏa thuận thương mại với nhau.
• Mỗi chặng giữa hai thành phố liên tiếp là một đoạn thẳng.
• Tuyến đường không được tự cắt, nhằm tránh va chạm giữa các thuyền.

Các thành phố được đánh số từ \(1\) đến \(c\) theo chiều kim đồng hồ quanh hồ.

Trong hình, cả nét đậm và nét mảnh đều biểu diễn các thỏa thuận thương mại. Các nét đậm tạo thành một tuyến đường bắt đầu ở thành phố \(2\) và kết thúc ở thành phố \(5\). Tuyến này không tự cắt. Ngược lại, một tuyến đi lần lượt qua \(2,6,5,1\) là không hợp lệ vì các chặng của nó cắt nhau.

Cho số thành phố và danh sách các thỏa thuận thương mại, hãy xây dựng một tuyến đường thỏa mãn tất cả các yêu cầu trên, hoặc xác định rằng không thể xây dựng được.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(c\), là số thành phố.
• Dòng thứ hai chứa số nguyên \(n\), là số thỏa thuận thương mại.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên phân cách bởi một dấu cách, là số hiệu hai thành phố có thỏa thuận với nhau. Mỗi thỏa thuận chỉ xuất hiện một lần.

Dữ liệu ra

Nếu tồn tại tuyến đường hợp lệ, ghi ra đầu ra chuẩn \(c\) dòng, mỗi dòng chứa một số nguyên là số hiệu thành phố được ghé thăm, theo đúng thứ tự của tuyến đường. Nếu không tồn tại, ghi một dòng chứa -1.

Nếu có nhiều tuyến đường hợp lệ, có thể xuất bất kỳ tuyến nào.

Ràng buộc

• \(3\le c\le1000\).
• Các số hiệu thành phố thuộc đoạn từ \(1\) đến \(c\).

Chấm điểm

Trong các bộ dữ liệu có tổng cộng \(40\) điểm, \(3\le c\le20\).

Ví dụ

7
9
1 4
5 1
1 7
5 6
2 3
3 4
2 6
4 6
6 7

2
3
4
1
7
6
5

Nguồn

IOI 2006.

Trò chơi nối điểm dành cho một người được chuẩn bị như sau. Chọn hai số nguyên \(g,r\) lớn hơn \(2\). Vẽ bốn điểm ở bốn đỉnh của một hình vuông: hai đỉnh phía trên màu xanh lá, hai đỉnh phía dưới màu đỏ. Vẽ thêm các điểm xanh lá và đỏ ở bên trong hình vuông cho đến khi có tổng cộng \(g\) điểm xanh lá và \(r\) điểm đỏ. Các điểm phải được đặt sao cho không có ba điểm nào thẳng hàng, kể cả bốn điểm ở các đỉnh ban đầu.

Sau khi chuẩn bị xong, bạn có thể nối hai điểm bằng một đoạn thẳng nếu hai điểm cùng màu và đoạn thẳng đó không giao với bất kỳ đoạn nào đã vẽ, ngoại trừ tại các đầu mút chung.

Hai điểm \(u,v\) thuộc cùng một thành phần liên thông nếu có thể đi từ \(u\) đến \(v\) bằng các đoạn thẳng đã vẽ.

Bạn thắng khi nối tất cả các điểm xanh lá thành một thành phần liên thông bằng đúng \(g-1\) đoạn thẳng, đồng thời nối tất cả các điểm đỏ thành một thành phần liên thông khác bằng đúng \(r-1\) đoạn thẳng. Có thể chứng minh rằng nếu các điểm được đặt theo các điều kiện trên thì luôn tồn tại cách thắng.

Bạn được cho một bảng hình vuông có cạnh \(s\) và tọa độ nguyên \((x_i,y_i)\) của các điểm. Các điểm xanh lá được đánh số riêng từ \(1\) đến \(g\): điểm \(1\) ở góc trên trái \((0,s)\), điểm \(2\) ở góc trên phải \((s,s)\), còn các điểm bên trong mang số từ \(3\) đến \(g\) theo thứ tự bất kỳ. Tương tự, các điểm đỏ được đánh số riêng từ \(1\) đến \(r\): điểm \(1\) ở góc dưới trái \((0,0)\), điểm \(2\) ở góc dưới phải \((s,0)\), còn các điểm bên trong mang số từ \(3\) đến \(r\) theo thứ tự bất kỳ.

Hình minh họa một cách thắng: tất cả các điểm xanh lá thuộc cùng một thành phần liên thông, tất cả các điểm đỏ thuộc một thành phần khác. Không có ba điểm nào thẳng hàng và các đoạn thẳng không giao nhau, ngoại trừ tại đầu mút chung.

Hãy xác định \(g-1\) đoạn thẳng nối các điểm xanh lá và \(r-1\) đoạn thẳng nối các điểm đỏ để thắng trò chơi.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(g\).
• \(g\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i,y_i\) phân cách bởi một dấu cách, là tọa độ điểm xanh lá thứ \(i\), theo thứ tự từ \(1\) đến \(g\).
• Dòng thứ \(g+2\) chứa số nguyên \(r\).
• \(r\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i,y_i\) phân cách bởi một dấu cách, là tọa độ điểm đỏ thứ \(i\), theo thứ tự từ \(1\) đến \(r\).

Giá trị \(s\) không được cho trên một dòng riêng; các điểm ở bốn đỉnh được cho theo đúng quy ước trên.

Dữ liệu ra

Ghi ra đầu ra chuẩn đúng \((g-1)+(r-1)\) dòng, mỗi dòng mô tả một đoạn thẳng được vẽ.

Mỗi dòng chứa hai số nguyên và một ký tự, phân cách bởi dấu cách. Hai số nguyên là số hiệu hai đầu mút trong nhóm điểm cùng màu. Ký tự là g nếu nối hai điểm xanh lá, hoặc r nếu nối hai điểm đỏ.

Thứ tự liệt kê các đoạn thẳng và thứ tự hai đầu mút của mỗi đoạn đều không quan trọng. Các đoạn phải nối mỗi nhóm màu thành một thành phần liên thông và không được giao nhau, ngoại trừ tại các đầu mút chung.

Ràng buộc

• \(3\le g\le50\,000\).
• \(3\le r\le50\,000\).
• \(0 < s \le200\,000\,000\).
• Tất cả tọa độ là số nguyên; ngoài bốn đỉnh đã nêu, các điểm đều nằm bên trong hình vuông.
• Không có ba điểm nào thẳng hàng.

Chấm điểm

Trong các bộ dữ liệu có tổng cộng \(35\) điểm, đồng thời có \(3\le g\le20\) và \(3\le r\le20\).

Ví dụ

6
0 1000
1000 1000
203 601
449 212
620 837
708 537
8
0 0
1000 0
185 300
314 888
416 458
614 622
683 95
838 400

1 3 g
3 1 r
3 5 r
4 6 r
6 5 r
4 6 g
1 2 g
1 2 r
5 2 g
2 6 g
7 8 r
8 2 r

Nguồn

IOI 2006.

Trò chơi sử dụng một hộp đen hình vuông đặt nằm trên bàn. Mỗi cạnh trong bốn cạnh của hộp có \(n\) lỗ, tổng cộng \(4n\) lỗ, để ném một viên bi vào. Viên bi cuối cùng sẽ đi ra qua một trong \(4n\) lỗ, có thể chính là lỗ mà nó đã đi vào.

Bên trong hộp là một lưới \(n\times n\). Các lỗ nằm ở hai đầu của mỗi hàng và mỗi cột. Mỗi ô hoặc để trống, hoặc chứa một bộ đổi hướng. Bộ đổi hướng làm viên bi đổi hướng chuyển động một góc \(90^\circ\).

Hình trên minh họa một hộp \(5\times5\). Nhãn Hole chỉ một lỗ; nhãn Deflectors chỉ các bộ đổi hướng.

Viên bi chuyển động thẳng cho đến khi gặp một bộ đổi hướng hoặc ra khỏi hộp. Khi gặp bộ đổi hướng, viên bi đổi hướng chuyển động, sau đó bộ đổi hướng quay \(90^\circ\), chuyển giữa hai trạng thái / và \.

Ở hình a, viên bi được ném qua một lỗ, gặp bộ đổi hướng và đổi hướng chuyển động. Sau lần ném này, bộ đổi hướng đã chuyển trạng thái. Ở hình b, một viên bi mới được ném vào cùng lỗ, gặp bộ đổi hướng đó và rẽ theo hướng ngược với viên bi đầu tiên. Hình c cho thấy bộ đổi hướng lại chuyển trạng thái sau lần va chạm tiếp theo. Bộ đổi hướng chuyển trạng thái mỗi lần bị viên bi chạm vào.

Mỗi lần bị chạm, bộ đổi hướng phát ra một tiếng bíp. Đếm số tiếng bíp cho biết số lần viên bi đổi hướng. Có thể chứng minh rằng viên bi luôn ra khỏi hộp. Hộp có một nút đưa tất cả bộ đổi hướng về trạng thái ban đầu và một nút chuyển trạng thái đồng thời tất cả bộ đổi hướng.

Đây là bài tương tác thông qua thư viện. Hệ thống chấm giữ kín cấu hình của hộp. Bạn cần viết chương trình khảo sát hộp bằng các hàm được cung cấp và trả về cấu hình ban đầu mà bạn suy ra được. Phiên bản này chuyển bài chỉ nộp kết quả của IOI 2006 thành bài nộp mã nguồn C++; không cần nộp tệp ZIP kết quả hay kết nối tới một dịch vụ bên ngoài.

Yêu cầu cài đặt

Nộp một tệp mã nguồn C++, khai báo #include "cppbblib.h" và cài đặt hàm:

std::vector<std::string> solve_blackbox(int box_id);

Mỗi lần chạy, hệ thống gọi hàm này đúng một lần cho một hộp có số hiệu \(1\le box\_id\le15\). Các hộp được chấm trong những tiến trình độc lập. Không cài đặt hàm main, không đọc đầu vào chuẩn và không ghi đầu ra chuẩn; hệ thống sử dụng các luồng này để liên lạc với thư viện chấm.

Đầu tiên, gọi Initialize(box_id) đúng một lần để nhận kích thước \(n\). Sau đó có thể gọi các hàm khảo sát. Khi đã hoàn tất, trả về một vector gồm đúng \(n\) chuỗi, mỗi chuỗi có đúng \(n\) ký tự. Các chuỗi mô tả các hàng từ trên xuống dưới; ký tự trong mỗi chuỗi tương ứng với các cột từ trái sang phải:

• .: khẳng định ô ban đầu trống.
• /: khẳng định ô ban đầu có bộ đổi hướng /.
• \: khẳng định ô ban đầu có bộ đổi hướng \.
• ?: chưa xác định được trạng thái ban đầu của ô.

Không thêm tiêu đề #FILE, dòng kích thước hay dấu cách vào các chuỗi trả về. Trả về khỏi solve_blackbox kết thúc việc khảo sát; không gọi Finalize hoặc tự kết thúc tiến trình bằng exit.

Các hàm thư viện

Tệp cppbblib.h cung cấp các hàm sau:

int Initialize(int box);
int throwBall(int holeIn, int sideIn, int &holeOut, int &sideOut);
void ResetBox();
void ToggleDeflectors();
long long HowManyThrows();

• Initialize(box) phải được gọi đúng một lần, trước các hàm khảo sát khác, với box bằng tham số box_id. Hàm trả về \(n\), với \(1\le n\le30\).
• throwBall(holeIn, sideIn, holeOut, sideOut) ném một viên bi vào hộp, trả về số lần viên bi chạm bộ đổi hướng và ghi lỗ ra, cạnh ra vào hai tham số tham chiếu. Cạnh \(1\) là trên, \(2\) là phải, \(3\) là dưới, \(4\) là trái. Trên cạnh trên/dưới, lỗ được đánh số từ trái sang phải; trên cạnh trái/phải, lỗ được đánh số từ trên xuống dưới. Mọi số hiệu lỗ nằm trong \([1,n]\).
• ResetBox() khôi phục tất cả bộ đổi hướng về trạng thái ban đầu của hộp.
• ToggleDeflectors() chuyển đồng thời mọi bộ đổi hướng ở trạng thái hiện tại: / thành \ và ngược lại. Ô trống không thay đổi.
• HowManyThrows() trả về số lần gọi throwBall đã hoàn tất kể từ Initialize. ResetBox và ToggleDeflectors không đặt lại bộ đếm này.

Thư viện cũng cung cấp phiên bản throwBall nhận con trỏ int* thay cho hai tham số tham chiếu. Hai phiên bản có cùng ý nghĩa. Trạng thái sau một lần ném được giữ lại cho thao tác tiếp theo. Một bộ đổi hướng chuyển trạng thái sau mỗi lần bị chạm, kể cả khi bị chạm nhiều lần trong cùng một lượt ném.

Số lần chạm được trả về bằng số nguyên có dấu \(32\) bit; giao thức hỗ trợ tối đa \(2^{24}-1\) lần chạm cho một lượt ném. Không có hạn mức riêng cho số lần gọi hàm, nhưng toàn bộ chương trình phải chạy trong giới hạn thời gian và bộ nhớ của bài. Gọi hàm với tham số không hợp lệ hoặc sai thứ tự không được chấp nhận.

Bộ chấm thử

Tệp đính kèm chứa cppbblib.h, bộ chấm thử sample_grader.cpp, lời giải khung và hộp mẫu blackbox.in. Bộ chấm thử đọc một hộp tự tạo từ đầu vào chuẩn và gọi solve_blackbox(0). Lời giải vẫn gọi Initialize(box_id); chỉ bộ chấm thử sử dụng số hiệu \(0\), còn các lần chấm trên hệ thống dùng số hiệu từ \(1\) đến \(15\).

Định dạng hộp tự tạo:

• Dòng đầu chứa \(n\).
• Dòng thứ hai chứa số bộ đổi hướng \(d\).
• Mỗi dòng trong \(d\) dòng tiếp theo chứa cột, hàng, rồi ký tự / hoặc \, phân cách bởi dấu cách. Hàng và cột được đánh số từ \(1\). Các ô không được liệt kê là ô trống; nếu một tọa độ được liệt kê nhiều lần, bản ghi cuối quyết định hướng của bộ đổi hướng.

Đây chỉ là đầu vào của bộ chấm thử, không phải đầu vào mà lời giải được phép đọc khi nộp bài. Cấu hình của \(15\) hộp chấm không được cung cấp cho lời giải.

Ví dụ thử nghiệm

5
3
2 3 \
4 2 /
4 4 /

Chấm điểm

Phiên bản LQDOJ áp dụng điểm theo tỉ lệ ô xác định đúng, thay cho cách chuẩn hóa theo kết quả của người chơi khác trong kỳ thi IOI 2006 gốc. Mỗi hộp có trọng số bằng nhau, chiếm \(100/15\) điểm trong tổng số \(100\) điểm.

Gọi \(B\) là số ô được khẳng định bằng ., / hoặc \; ô trống xác định đúng cũng được tính. Nếu có bất kỳ khẳng định nào sai so với trạng thái ban đầu, cả hộp nhận \(0\) điểm. Kết quả sai số hàng, sai độ dài hàng hoặc chứa ký tự không hợp lệ cũng không được chấp nhận.

Nếu mọi khẳng định đều đúng, phần trăm điểm của hộp là:

Trả về toàn bộ ô là ? cho \(0\) điểm; xác định đúng mọi ô cho đủ điểm. Tổng điểm là tổng của \(p/15\) trên \(15\) hộp, không làm tròn điểm từng hộp về số nguyên. Một hộp bị lỗi không ngăn hệ thống chấm các hộp còn lại.

Trong kỳ thi sử dụng định dạng này, hệ thống lấy điểm cao nhất của từng hộp trên tất cả các lần nộp của bạn, rồi cộng lại. Cả cách chấm theo tỉ lệ ô và cách tổng hợp điểm này là quy tắc của phiên bản chuyển thể, không phải quy tắc lịch sử IOI 2006.

Nguồn

IOI 2006 - Blackbox, bản tiếng Anh 1.6. Chuẩn hóa theo tỉ lệ ô như bản chuyển thể của Pavel Kunyavskiy trên Codeforces; phiên bản này dùng giao diện hàm C++ thay cho nộp tệp kết quả.