Dây thừng

Đề bài

Hai đội trinh sát đang tham gia một cuộc thi trinh sát. Đây là vòng chung kết và cả hai đội đều đã chuẩn bị kỹ lưỡng. Trò chơi diễn ra dọc theo một con sông chảy từ tây sang đông. Có \(4\mathbf{N}\) cây được trồng dọc theo sông, trong đó đúng \(2\mathbf{N}\) cây nằm thành hàng trên bờ bắc và \(2\mathbf{N}\) cây nằm thành hàng trên bờ nam. Hai đội luân phiên thực hiện lượt chơi. Đội của bạn đi trước.

Trong mỗi lượt, đội đang chơi chọn một cây chưa buộc dây ở mỗi bờ rồi buộc một sợi dây giữa hai cây đó, bắc ngang qua sông. Mỗi sợi dây mới được đặt cao hơn tất cả các sợi dây trước đó. Đội đang chơi ghi 1 điểm cho mỗi sợi dây đã được sử dụng trước đó đi bên dưới sợi dây vừa thêm.

Sau \(2\mathbf{N}\) lượt, mỗi cây đều được buộc đúng một sợi dây, vì vậy không còn nước đi nào và trò chơi kết thúc. Điểm của mỗi đội là tổng số điểm họ ghi được trong tất cả các lượt của mình. Nếu điểm của đội bạn lớn hơn hẳn điểm của đội đối phương thì đội bạn thắng. Nếu điểm của đội bạn nhỏ hơn hoặc bằng điểm của đội đối phương thì đội bạn không thắng.

Hoạt ảnh sau minh họa một ván đấu có \(\mathbf{N}=2\). Đội của bạn được biểu diễn bằng màu đỏ và đội kia bằng màu xanh lam.

Đội đối phương tin rằng đi sau là một lợi thế lớn, nên họ đã tiết lộ chiến lược. Trong lượt của mình, họ chọn nước đi đem lại số điểm lớn nhất có thể cho chính lượt đó. Nếu có nhiều nước đi như vậy, họ chọn ngẫu nhiên một nước. Lựa chọn này được sinh ngẫu nhiên đều và độc lập cho từng nước đi, từng bộ test và từng lần nộp bài. Vì vậy, ngay cả khi bạn nộp chính xác cùng một mã nguồn hai lần, đội đối phương vẫn có thể đưa ra các lựa chọn ngẫu nhiên khác nhau.

Bạn chơi tổng cộng \(\mathbf{T}\) ván và đội của bạn phải thắng ít nhất \(\mathbf{W}\) ván.

Dữ liệu vào

Nội dung vào được cung cấp theo giao thức mô tả dưới đây.

Dữ liệu ra

Đây là một bài tương tác. Bạn cần bảo đảm rằng mình đã đọc thông tin trong mục Bài toán tương tác của FAQ.

Ban đầu, chương trình phải đọc một dòng chứa ba số nguyên \(\mathbf{T}\), \(\mathbf{N}\) và \(\mathbf{W}\): lần lượt là số bộ test, số lượt của đội bạn và số ván thắng cần đạt để lời giải được xem là đúng. Lưu ý rằng đội đối phương cũng có \(\mathbf{N}\) lượt, nên mỗi bộ test có tổng cộng \(2\mathbf{N}\) lượt.

Với mỗi bộ test, chương trình phải xử lý \(\mathbf{N}\) lần trao đổi. Mỗi lần trao đổi biểu diễn hai lượt liên tiếp: một lượt của đội bạn và một lượt của đội đối phương.

Trong lần trao đổi thứ \(i\), trước tiên bạn phải in một dòng chứa hai số nguyên \(\mathbf{A_i}\) và \(\mathbf{B_i}\), sau đó đọc một dòng chứa hai số nguyên \(\mathbf{C_i}\) và \(\mathbf{D_i}\). Điều này biểu diễn rằng trong lượt thứ \(i\) của mình, bạn đã buộc dây giữa cây thứ \(\mathbf{A_i}\) tính từ phía tây trên bờ bắc và cây thứ \(\mathbf{B_i}\) tính từ phía tây trên bờ nam. Tương tự, trong lượt thứ \(i\) của đội đối phương, họ dùng cây thứ \(\mathbf{C_i}\) tính từ phía tây trên bờ bắc và cây thứ \(\mathbf{D_i}\) tính từ phía tây trên bờ nam. Các cây được đánh số bắt đầu từ 1.

Sau \(\mathbf{N}\) lần trao đổi, bạn phải đọc một số biểu diễn kết quả của ván đấu. Số này bằng 1 nếu đội bạn thắng, ngược lại bằng 0.

Bộ test tiếp theo bắt đầu ngay lập tức nếu vẫn còn. Nếu đây là bộ test cuối cùng, bộ chấm sẽ không chờ thêm dữ liệu ra và cũng không gửi thêm dữ liệu vào cho chương trình. Ngoài ra, toàn bộ \(\mathbf{T}\) bộ test luôn được xử lý, bất kể tại thời điểm đó đã chắc chắn có thể hay không thể đạt ngưỡng để được chấm đúng. Ngưỡng chỉ được kiểm tra sau khi tất cả bộ test đã được xử lý đúng giao thức.

Nếu tại bất kỳ thời điểm nào bộ chấm nhận được từ chương trình một dòng sai định dạng hoặc một nước đi không hợp lệ (chẳng hạn dùng một cây đã được dùng), bộ chấm sẽ in duy nhất số -1 và không in thêm gì nữa. Nếu chương trình vẫn tiếp tục chờ bộ chấm sau khi nhận -1, chương trình sẽ hết thời gian và nhận kết quả Time Limit Exceeded. Bạn có trách nhiệm để chương trình thoát kịp thời nhằm nhận kết quả Wrong Answer thay vì Time Limit Exceeded. Như thường lệ, nếu chương trình dùng quá giới hạn bộ nhớ hoặc gặp lỗi khi chạy, bạn sẽ nhận kết quả tương ứng.

Ràng buộc

\(\mathbf{T} = 2000\).
\(\mathbf{N} = 50\).

Phân nhóm

Test Set 1 (kết quả chấm hiển thị)

\(\mathbf{W} = 1200\) (\(\mathbf{W} = 0.6 \cdot \mathbf{T}\)).

Test Set 2 (kết quả chấm hiển thị)

\(\mathbf{W} = 1560\) (\(\mathbf{W} = 0.78 \cdot \mathbf{T}\)).

Test Set 3 (kết quả chấm hiển thị)

\(\mathbf{W} = 1720\) (\(\mathbf{W} = 0.86 \cdot \mathbf{T}\)).

Giao thức tương tác

Chương trình phải tuân thủ đầy đủ thứ tự đọc, ghi, phản hồi lỗi và yêu cầu flush được mô tả trong phần dữ liệu vào/ra và công cụ kiểm thử bên dưới.

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử này để kiểm tra cục bộ hoặc trên nền tảng của chúng tôi. Để kiểm tra cục bộ, bạn cần chạy công cụ song song với mã nguồn của mình; bạn có thể dùng trình chạy tương tác của chúng tôi cho việc đó. Để biết thêm thông tin, hãy đọc hướng dẫn trong các chú thích của tệp đó, đồng thời xem mục Bài toán tương tác trong FAQ.

Hướng dẫn dành cho công cụ kiểm thử được ghi trong các chú thích bên trong công cụ. Chúng tôi khuyến khích bạn tự thêm các bộ test. Xin lưu ý rằng mặc dù công cụ kiểm thử được thiết kế để mô phỏng hệ thống chấm, nó KHÔNG phải hệ thống chấm thật và có thể hoạt động khác. Nếu mã nguồn vượt qua công cụ kiểm thử nhưng thất bại trên bộ chấm thật, hãy kiểm tra mục Lập trình trong FAQ để bảo đảm rằng bạn đang dùng cùng trình biên dịch với chúng tôi.

Tải công cụ kiểm thử

Ví dụ

Nguồn

Google Code Jam 2021, Chung kết thế giới, bài Ropes.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.