Score là trò chơi hai người cùng di chuyển một quân cờ. Bàn cờ có \(N\) vị trí, đánh số từ \(1\) đến \(N\), và các mũi tên có hướng nối các vị trí. Mỗi vị trí thuộc sở hữu của một người chơi và có một giá trị nguyên dương; tất cả giá trị đôi một khác nhau. Quân cờ bắt đầu ở vị trí 1, điểm ban đầu của mỗi người bằng 0.

Gọi vị trí hiện tại ở đầu một lượt là \(C\). Lượt đi gồm hai bước:

1. Nếu giá trị của \(C\) lớn hơn điểm hiện tại của người sở hữu \(C\), thay điểm của người đó bằng giá trị của \(C\). Nếu không, điểm giữ nguyên. Điểm của người kia không thay đổi.
2. Người sở hữu \(C\) chọn một mũi tên đi ra từ \(C\) và chuyển quân cờ đến đầu kia của mũi tên. Một người có thể đi nhiều lượt liên tiếp.

Trò chơi kết thúc khi quân cờ trở lại vị trí 1. Người có điểm cao hơn thắng. Các mũi tên luôn bảo đảm:

• Ở mỗi vị trí đều chọn được một mũi tên đi ra.
• Từ vị trí 1 có thể đi theo các mũi tên tới mọi vị trí.
• Trò chơi chắc chắn kết thúc sau hữu hạn lượt đi.

Hãy viết chương trình chơi và thắng. Mọi ván dùng để chấm đều có chiến lược thắng cho chương trình của bạn, dù bạn có đi trước hay không. Đối thủ chơi tối ưu: một khi bạn để họ có cơ hội thắng, họ sẽ thắng.

Tương tác

Bạn là người chơi 1, đối thủ là người chơi 2. Trước tiên đọc mô tả bàn cờ từ đầu vào chuẩn:

• Dòng đầu chứa \(N\), với \(1\le N\le1000\).
• \(N\) dòng tiếp theo, mỗi dòng có \(N\) số. Số thứ \(j\) trên dòng thứ \(i\) là 1 nếu có mũi tên từ \(i\) đến \(j\), ngược lại là 0.
• Dòng tiếp theo chứa \(N\) số là chủ sở hữu các vị trí: 1 nếu thuộc bạn, 2 nếu thuộc đối thủ.
• Dòng cuối chứa \(N\) giá trị của các vị trí, đôi một khác nhau, mỗi giá trị từ \(1\) đến \(N\).

Sau đó ván chơi bắt đầu tại vị trí 1. Đến lượt bạn, in vị trí đích \(P\) của một mũi tên đi ra hợp lệ; đến lượt đối thủ, đọc vị trí đích \(P\) của họ. Luôn có \(1\le P\le N\). Thoát chương trình khi quân cờ trở về vị trí 1.

Đẩy dữ liệu sau mỗi nước đi: trong C++, dùng cout << target << endl << flush; và đọc cin >> target;; trong C, dùng printf("%d\n", target); fflush(stdout); và scanf("%d", &target);; trong Pascal, dùng Writeln(target); và Readln(target);.

Công cụ gốc

Công cụ score2 trên Linux, hoặc score2.exe trên Windows, đọc bàn cờ từ score.in theo định dạng trên, rồi in mô tả đó ra đầu ra chuẩn. Sau đó công cụ dùng chiến lược ngẫu nhiên, đọc nước đi của bạn từ đầu vào chuẩn và in nước đi của mình. Công cụ thử này không phải đối thủ tối ưu dùng khi chấm.

Chấm điểm

Có 20 bộ kiểm tra, mỗi bộ tương ứng 5 điểm. Thắng ván chơi và đáp ứng giới hạn thời gian nhận toàn bộ điểm, ngược lại nhận 0 điểm.

Trong quy trình chấm gốc, chương trình trước hết đấu với một chương trình khác với giới hạn thời gian lớn hơn giới hạn chính thức 1 giây; toàn bộ dữ liệu vào và ra được ghi lại. Sau đó chương trình được chạy lại với đầu vào từ tệp ghi đó để đo thời gian chính thức. Kết quả in ra trong hai lần phải giống nhau. Thời gian của tiến trình đối thủ không được cộng vào thời gian chương trình thí sinh.

Ví dụ

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

2
4

Nguồn

Đề gốc IOI 2001. Bảng tổng quan ngày 2.