JOI 2013 Final Camp - Ngày 4

A và B được chọn vào đội tuyển Nhật Bản dự thi Olympic Tin học Quốc tế. Để rèn luyện khả năng xử lý thông tin, họ chơi trò truyền tin với chủ tịch K.

A, B và K ở ba phòng riêng biệt. Mỗi phòng có điện thoại nội bộ, nhưng chỉ K được gọi điện. A và B không có cách liên lạc nào khác và chỉ được rời phòng khi K gọi. Khi bắt đầu trò chơi, K thông báo riêng cho A một số nguyên dương \(X\). Mục tiêu của A và B là khiến B xác định đúng \(X\) mà không liên lạc trực tiếp với nhau.

Trong phòng K có một bàn cờ \(4 \times 4\). Ô \((i,j)\) nằm ở hàng \(i\) từ trên xuống, cột \(j\) từ trái sang, với \(1 \le i,j \le 4\). Các ô \((1,1)\), \((1,4)\), \((4,1)\) và \((4,4)\) lần lượt là bốn góc trên trái, trên phải, dưới trái và dưới phải. Ban đầu, một quân cờ được đặt ở một ô bất kỳ. K không di chuyển quân cờ trong suốt trò chơi.

K liên tục gọi A hoặc B đến phòng mình. Mỗi lần đến, người được gọi phải di chuyển quân cờ sang một ô kề cạnh ở phía trên, dưới, trái hoặc phải, rồi trở về phòng. Riêng B, nếu đã xác định được \(X\), có thể trả lời K thay cho việc di chuyển. Nếu câu trả lời đúng, hai người thắng; nếu sai, họ thua ngay.

Thứ tự gọi được K chọn trước khi trò chơi bắt đầu, nhưng A và B không biết thứ tự đó, cũng không biết đối phương đã được gọi bao nhiêu lần giữa hai lượt của mình. Bảo đảm K không gọi cùng một người quá \(100\) lần liên tiếp. Nếu sau tổng cộng \(10\,000\) lượt gọi, người được gọi đã di chuyển xong mà B vẫn chưa trả lời, trò chơi kết thúc với kết quả sai.

Yêu cầu

Cài đặt hai chương trình mô tả chiến lược của A và B để B luôn xác định đúng \(X\) trong giới hạn lượt gọi.

Giao diện của phía A

Nộp tệp playerA.c hoặc playerA.cpp, định nghĩa đúng hai hàm:

void InitA(int T, int X);
int GameA(int I, int J);

• InitA(T, X) được gọi đúng một lần lúc khởi tạo. T là số hiệu bài toán con; X là số nguyên dương cần truyền cho B. Hàm không trả về giá trị.
• GameA(I, J) được gọi mỗi khi A đến phòng K. I và J là hàng và cột hiện tại của quân cờ, với \(1 \le I,J \le 4\). Hàm phải trả về một trong bốn số nguyên -1, -2, -3, -4, biểu thị một bước di chuyển.

Giao diện của phía B

Nộp tệp playerB.c hoặc playerB.cpp, định nghĩa đúng hai hàm:

void InitB(int T);
int GameB(int I, int J);

• InitB(T) được gọi đúng một lần lúc khởi tạo. T là số hiệu bài toán con. Phía B không được cung cấp X. Hàm không trả về giá trị.
• GameB(I, J) được gọi mỗi khi B đến phòng K. I và J là hàng và cột hiện tại của quân cờ, với \(1 \le I,J \le 4\). Hàm phải trả về một trong bốn số -1, -2, -3, -4 để di chuyển, hoặc một số nguyên dương Y để trả lời rằng \(X=Y\).

Các giá trị trả về biểu thị di chuyển có cùng ý nghĩa ở cả hai phía:

Mỗi lượt phải thực hiện đúng một bước di chuyển hợp lệ, trừ lượt B trả lời. Không được đứng yên hoặc đưa quân cờ ra ngoài bàn. Số nguyên dương do GameB trả về là đáp án gửi cho K và làm trò chơi kết thúc ngay, không phải một thông điệp gửi cho A.

Thứ tự gọi và cách ly hai phía

Hai tệp phải dùng cùng một ngôn ngữ. Trình chấm cung cấp main và khai báo trực tiếp bốn hàm trên; không có header giao tiếp riêng phải đưa vào mã dự thi.

Khi khởi tạo, grader mẫu gọi InitA(T, X), rồi InitB(T). Sau khi hoàn thành khởi tạo, các lời gọi GameA và GameB diễn ra theo thứ tự K đã chọn. Mỗi lời gọi nhận vị trí quân cờ sau tất cả những bước di chuyển trước đó. Mỗi bên chỉ quan sát được tham số của các lời gọi dành cho mình và có thể giữ trạng thái riêng qua các lượt gọi.

Không hàm nào trong hai hàm GameA, GameB được gọi quá \(100\) lần liên tiếp. Tổng số lời gọi hai hàm không vượt quá \(10\,000\). B phải trả về đáp án dương trong một lời gọi GameB nằm trong giới hạn đó; trả lời ở lượt thứ \(10\,000\) vẫn hợp lệ.

Hai tệp được liên kết cùng trình chấm thành một tệp thực thi, nhưng khi chấm bài, phía A và phía B chạy trong hai tiến trình riêng biệt. Hai phía không chia sẻ biến toàn cục hay bộ nhớ. Bạn được viết các hàm phụ và biến toàn cục, nhưng mọi hàm phụ và biến toàn cục nội bộ trong mỗi tệp phải được khai báo static để tránh xung đột khi liên kết. Bốn hàm giao diện phải giữ nguyên khả năng được trình chấm gọi.

Mã dự thi không được tương tác với đầu vào chuẩn, đầu ra chuẩn hoặc bất kỳ tệp nào bằng bất kỳ cách nào. Kênh truyền thông tin duy nhất giữa hai phía là vị trí quân cờ được quan sát và thay đổi qua những lời gọi nói trên; không có hàm gửi chuỗi, gửi bit hoặc gọi trực tiếp sang phía còn lại.

Dữ liệu vào

Dữ liệu dành cho mã dự thi được truyền qua InitA, InitB, GameA và GameB. Chỉ A được nhận \(X\); thứ tự gọi đầy đủ được giữ trong trình chấm.

Để thử chương trình, grader mẫu đọc đầu vào chuẩn theo định dạng:

• Dòng đầu tiên chứa bốn số nguyên \(T,X,I_0,J_0\), phân cách bằng dấu cách: số hiệu bài toán con, số cần truyền và vị trí ban đầu của quân cờ.
• Dòng thứ hai chứa một chuỗi dài đúng \(10\,000\) ký tự, chỉ gồm A và B. Ký tự thứ \(k\) cho biết lời gọi thứ \(k\) sau khi khởi tạo là GameA hay GameB.

Chuỗi gọi thỏa mãn giới hạn không có quá \(100\) ký tự giống nhau liên tiếp và các điều kiện của bài toán con tương ứng. Grader mẫu đọc dữ liệu, đóng luồng đầu vào, khởi tạo hai phía rồi lần lượt thực hiện các lời gọi. Nó dừng ngay khi có đáp án hoặc hành động không hợp lệ.

Dữ liệu ra

Mã dự thi thực hiện hành động bằng giá trị trả về từ GameA hoặc GameB; B báo đáp án bằng giá trị nguyên dương trả về từ GameB.

Grader mẫu ghi một dòng ra đầu ra chuẩn:

Grader mẫu kết thúc với mã thoát \(0\) khi chấp nhận, hoặc mã thoát bằng số lỗi khi chấm sai.

Biên dịch và chạy thử

Biên dịch bằng một trong hai lệnh:

gcc -O2 -lm grader.c playerA.c playerB.c -o grader

g++ -O2 -lm grader.cpp playerA.cpp playerB.cpp -o grader

Chạy ./grader, cung cấp dữ liệu cho grader qua đầu vào chuẩn và nhận kết quả của grader qua đầu ra chuẩn. Grader mẫu chạy trong một tiến trình để thử các lời gọi. Khi chấm chính thức, hai phía chạy cách ly trong hai tiến trình như đã mô tả; chiến lược phải tuân thủ sự cách ly này cả khi thử bằng grader mẫu.

Giới hạn

• \(1 \le X \le 1\,000\,000\,000\).
• \(T \in \{1,2,3\}\).
• \(1 \le I_0,J_0 \le 4\).
• Không gọi cùng một phía quá \(100\) lần liên tiếp.
• Nhiều nhất \(10\,000\) lượt gọi GameA và GameB cộng lại.
• Thời gian: 1 giây. Bộ nhớ: 256 MB.

Chấm điểm

Mỗi nhóm kiểm thử gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi hai chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm, tuân thủ giao diện, cách ly, giới hạn lượt gọi, thời gian và bộ nhớ.

• Bài toán con 1 (20 điểm): \(T=1\). A được gọi trước, sau đó hai bên được gọi luân phiên: lượt lẻ gọi GameA, lượt chẵn gọi GameB.
• Bài toán con 2 (20 điểm): \(T=2\). Vị trí ban đầu của quân cờ là \((I_0,J_0)=(1,1)\). Lời gọi đầu tiên có thể dành cho A hoặc B.
• Bài toán con 3 (60 điểm): \(T=3\). Không có giới hạn bổ sung.

Ví dụ tương tác

Xét một trò chơi có dòng đầu của dữ liệu dành cho grader là 2 6 1 1. Phần đầu của chuỗi quy định thứ tự gọi là:

ABBAABAAABBBBBABBAABBBABBBBAAAAABABAABAABBBBABAAAA

Bảng sau mô tả quá trình tương tác kết thúc ở lượt chơi thứ \(6\), trước khi cần dùng các ký tự còn lại của chuỗi dài \(10\,000\) ký tự:

Chuỗi hành động này minh họa giao diện tương tác và không quy định chiến lược phải sử dụng.

Học viện JOI tổ chức một buổi trao đổi bánh kẹo vào dịp ngày Valentine trắng. Có \(N\) học sinh tham gia, được đánh số từ \(1\) đến \(N\). Mỗi học sinh chọn làm một trong hai loại bánh: bánh quy hoặc bánh kem, rồi tặng cho một học sinh khác. Học sinh \(i\) tặng \(B_i\) chiếc bánh mình làm cho học sinh \(A_i\).

Mỗi học sinh có sở thích riêng. Với học sinh \(i\):

• Mỗi chiếc bánh nhận được cùng loại với bánh mình làm đem lại \(C_i\) điểm vui vẻ.
• Mỗi chiếc bánh nhận được khác loại với bánh mình làm đem lại \(D_i\) điểm vui vẻ.

Điểm vui vẻ của mỗi học sinh là tổng điểm từ tất cả bánh người đó nhận được. Một học sinh có thể nhận bánh từ nhiều người hoặc không nhận được chiếc nào. Các hệ số \(C_i,D_i\) thuộc về người nhận bánh.

Yêu cầu

Chọn loại bánh mỗi học sinh làm sao cho tổng điểm vui vẻ của cả \(N\) học sinh lớn nhất, và tính giá trị lớn nhất đó.

Dữ liệu vào

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

• Dòng đầu tiên chứa số nguyên \(N\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa bốn số nguyên \(A_i,B_i,C_i,D_i\), phân cách bằng dấu cách: người nhận bánh từ học sinh \(i\), số bánh học sinh \(i\) tặng, điểm học sinh \(i\) nhận được cho mỗi bánh cùng loại và điểm học sinh \(i\) nhận được cho mỗi bánh khác loại.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: tổng điểm vui vẻ lớn nhất của \(N\) học sinh.

Giới hạn

• \(2 \le N \le 100\,000\).
• \(1 \le A_i \le N\) và \(A_i \ne i\) với mọi \(1 \le i \le N\).
• \(1 \le B_i,C_i,D_i \le 1\,000\,000\) với mọi \(1 \le i \le N\).
• Thời gian: 1 giây. Bộ nhớ: 256 MB.

Chấm điểm

Mỗi nhóm kiểm thử gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm và đáp ứng giới hạn thời gian, bộ nhớ.

• Bài toán con 1 (10 điểm): \(N \le 16\).
• Bài toán con 2 (20 điểm): \(N \le 5\,000\).
• Bài toán con 3 (70 điểm): Không có giới hạn bổ sung.

Ví dụ

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

257

Cho các học sinh \(1,2,5,6\) làm bánh quy và các học sinh \(3,4,7\) làm bánh kem. Khi đó:

• Học sinh \(1\) nhận \(8\) bánh quy và \(8\) bánh kem, được \(88\) điểm.
• Học sinh \(2\) nhận \(5\) bánh kem, được \(40\) điểm.
• Học sinh \(3\) nhận \(10\) bánh quy, được \(90\) điểm.
• Học sinh \(4\) nhận \(5\) bánh kem, được \(35\) điểm.
• Học sinh \(5\) không nhận bánh, được \(0\) điểm.
• Học sinh \(6\) không nhận bánh, được \(0\) điểm.
• Học sinh \(7\) nhận \(2\) bánh quy, được \(4\) điểm.

Tổng điểm vui vẻ là \(257\).

Trong một thiên hà xa xôi có \(N\) hành tinh được đánh số từ \(1\) đến \(N\). Mỗi hành tinh quản lý một tàu vũ trụ. Mỗi tàu hoặc đang ngừng hoạt động, hoặc đang phục vụ một tuyến đến một hành tinh khác.

Nếu tàu do hành tinh \(a\) quản lý phục vụ tuyến đến hành tinh \(b\), tàu sẽ liên tục đi qua lại giữa hai hành tinh. Tuy nhiên, hành khách thông thường chỉ được đi từ \(a\) đến \(b\); chuyến trở về từ \(b\) đến \(a\) không chở hành khách. Khi ngừng hoạt động, tàu đỗ tại hành tinh quản lý nó.

Ban đầu, tất cả các tàu đều ngừng hoạt động. Lịch thay đổi trạng thái tàu đã được xác định, với hai loại thay đổi:

• Cho tàu đang ngừng hoạt động của hành tinh \(a\) bắt đầu phục vụ tuyến đến hành tinh \(b\). Thay đổi này chỉ được thực hiện khi hành khách chưa thể đi từ \(b\) đến \(a\) bằng các tuyến đang hoạt động.
• Cho tàu đang hoạt động của hành tinh \(a\) ngừng hoạt động.

Hai người đang lên kế hoạch du lịch muốn trả lời các câu hỏi tại những thời điểm trong lịch trình. Nếu một người ở hành tinh \(a\), người kia ở hành tinh \(b\), liệu họ có thể gặp nhau bằng cách sử dụng các tuyến dành cho hành khách hay không? Nếu có, họ nên gặp nhau ở hành tinh nào để tổng số lượt đi tàu của cả hai nhỏ nhất?

Cụ thể, cần tìm một hành tinh \(c\) mà cả hai đều có thể đến từ vị trí của mình, sao cho tổng số lượt đi tàu từ \(a\) đến \(c\) và từ \(b\) đến \(c\) nhỏ nhất. Một người có thể ở nguyên hành tinh đang đứng và sử dụng \(0\) lượt đi tàu. Mỗi câu hỏi xét các tuyến đang hoạt động tại thời điểm đó.

Yêu cầu

Cho các thay đổi trạng thái và các câu hỏi theo thứ tự thời gian, hãy trả lời tất cả câu hỏi.

Dữ liệu vào

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

• Dòng đầu tiên chứa hai số nguyên \(N,Q\), trong đó \(Q\) là tổng số thay đổi và câu hỏi.
• Mỗi dòng trong \(Q\) dòng tiếp theo mô tả một sự kiện theo thứ tự thời gian, thuộc một trong ba dạng dưới đây. Các số trên cùng dòng được phân cách bằng dấu cách.

Các dạng sự kiện:

• 1 Ai Bi: Cho tàu của hành tinh \(A_i\) bắt đầu phục vụ tuyến đến hành tinh \(B_i\). Bảo đảm \(1 \le A_i,B_i \le N\), \(A_i \ne B_i\), tàu của \(A_i\) hiện đang ngừng hoạt động, và hành khách hiện chưa thể đi từ \(B_i\) đến \(A_i\).
• 2 Ai: Cho tàu của hành tinh \(A_i\) ngừng hoạt động. Bảo đảm \(1 \le A_i \le N\) và tàu này hiện đang hoạt động.
• 3 Ai Bi: Hỏi nơi gặp nhau tối ưu của hai người hiện ở \(A_i\) và \(B_i\). Bảo đảm \(1 \le A_i,B_i \le N\) và \(A_i \ne B_i\).

Gọi \(T_i\) là số đầu tiên trên dòng mô tả sự kiện thứ \(i\).

Dữ liệu ra

Với mỗi câu hỏi, theo thứ tự xuất hiện, ghi ra đầu ra chuẩn một dòng:

• Nếu hai người có thể gặp nhau, ghi số hiệu hành tinh gặp nhau làm tổng số lượt đi tàu nhỏ nhất.
• Nếu không thể gặp nhau, ghi -1.

Giới hạn

• \(2 \le N \le 1\,000\,000\).
• \(1 \le Q \le 1\,000\,000\).
• Thời gian: 10 giây. Bộ nhớ: 256 MB.

Chấm điểm

Mỗi nhóm kiểm thử gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm và đáp ứng giới hạn thời gian, bộ nhớ.

• Bài toán con 1 (10 điểm): \(N \le 5\,000\) và \(Q \le 5\,000\).
• Bài toán con 2 (30 điểm): \(T_i \ne 2\) với mọi \(1 \le i \le Q\); không có sự kiện ngừng hoạt động một tàu.
• Bài toán con 3 (60 điểm): Không có giới hạn bổ sung.

Ví dụ

6 5
1 2 4
3 2 6
1 4 3
1 6 4
3 2 6

-1
4

Đầu tiên, tuyến \(2 \to 4\) bắt đầu hoạt động. Hai người ở \(2\) và \(6\) chưa thể gặp nhau, nên câu trả lời đầu tiên là \(-1\).

Sau đó, các tuyến \(4 \to 3\) và \(6 \to 4\) bắt đầu hoạt động. Hai người ở \(2\) và \(6\) có thể gặp nhau tại \(3\) hoặc \(4\). Gặp tại \(4\) cần tổng cộng \(2\) lượt đi tàu, ít hơn so với gặp tại \(3\), nên câu trả lời là \(4\).

8 36
1 1 2
1 6 5
1 7 8
3 5 6
1 5 4
1 8 1
3 7 2
3 3 8
3 1 8
1 3 2
1 4 1
3 8 5
3 4 3
2 4
3 6 8
1 2 5
3 6 8
2 8
3 1 4
3 6 8
3 6 3
2 3
3 1 2
1 4 3
3 2 6
1 8 3
3 1 7
3 1 6
3 5 4
2 2
2 5
1 3 6
1 2 7
3 1 4
3 1 5
3 6 7

5
2
-1
1
1
2
-1
5
4
-1
5
2
5
3
5
4
3
5
6