BOI 2022 - Ngày 2

Mọi vụ đột nhập, dù chỉ là giả định, đều cần một kế hoạch tẩu thoát tốt. Vì thế, bạn đã thuê một trợ lý để giúp mình thoát khỏi kho dưới nước phát hiện hôm qua.

Để kế hoạch thành công, việc liên lạc với trợ lý rất quan trọng. Cụ thể, bạn cần gửi một trong \(N\) thông điệp khác nhau, được đánh số từ \(1\) đến \(N\). Đáng tiếc là khi ở trong chiếc tàu ngầm mới tinh, bạn chỉ có thể phát hai loại tín hiệu. Vì vậy, bạn phải mã hóa thông điệp thành một dãy các tín hiệu này.

Tuy nhiên, phát tín hiệu là một quá trình phức tạp, liên quan đến ống phóng ngư lôi, một ứng dụng bất ngờ và tao nhã của thuật toán Dijkstra, cùng một gói mì spaghetti cỡ gia đình. Quá trình ấy có thể thất bại và phát nhầm tín hiệu. Bạn chỉ có thể chắc chắn rằng điều này không bao giờ xảy ra hai lần liên tiếp. Ngoài ra, bạn luôn biết tín hiệu nào thực sự đã được phát và có thể điều chỉnh hành động tiếp theo.

Hiển nhiên, tín hiệu trong hình được hiểu là bit \(1\).

Bạn nhận ra rằng trong những điều kiện này, có thể không truyền được một thông điệp một cách hoàn toàn không mơ hồ. Vì vậy, bạn chấp nhận việc trợ lý xác định nhiều nhất hai thông điệp mà bạn có thể muốn gửi, miễn là thông điệp ban đầu nằm trong số đó. Là một lập trình viên tài năng, bạn muốn viết chương trình vừa giúp mình quyết định nên phát tín hiệu nào, vừa giúp trợ lý xác định hai thông điệp có thể có.

Phát tín hiệu từ tàu ngầm có thể gây nghi ngờ — nó gây nhiễu vô tuyến nghiêm trọng và làm các loài vật địa phương vô cùng hoảng loạn — nên bạn chỉ được phát tối đa \(250\) tín hiệu. Trợ lý cũng cần phản ứng nhanh: họ phải nhận ra lúc nào việc liên lạc đã kết thúc mà không chờ thêm tín hiệu!

Giao tiếp

Đây là bài giao tiếp, trong đó chương trình của bạn được chạy nhiều lần cho mỗi bộ dữ liệu. Bạn phải cài đặt hai hàm sau. Trong mỗi lần chạy chương trình, chỉ một trong hai hàm được gọi, nhưng có thể được gọi nhiều lần với các tham số khác nhau:

void encode(int N, int X);
std::pair<int, int> decode(int N);

Các hàm do trình chấm cung cấp là:

int send(int s);
int receive();

• encode(N, X): \(N\) là số thông điệp khác nhau và \(X\) là thông điệp cần truyền, với \(1\le X\le N\). Trong mỗi lời gọi encode, bạn được gọi send(s) tối đa \(250\) lần. Tham số \(s\) phải bằng \(0\) hoặc \(1\), biểu thị tín hiệu muốn gửi. Giá trị trả về cho biết tín hiệu thực sự đã được gửi. Giá trị này có thể khác \(s\), nhưng trong hai lời gọi send liên tiếp thuộc cùng một lời gọi encode, điều đó xảy ra nhiều nhất một lần.
• decode(N): \(N\) giống với giá trị trong lời gọi encode tương ứng. Mỗi lời gọi encode có một lời gọi decode tương ứng. Trong decode, hàm receive() trả về tín hiệu tiếp theo thực sự đã được gửi trong lời gọi encode tương ứng. Cuối cùng, decode phải trả về một cặp số nguyên \((a,b)\), với \(1\le a,b\le N\), sao cho \(X=a\) hoặc \(X=b\). Được phép có \(a=b\).

Bạn bị chấm sai bộ dữ liệu nếu trong decode gọi receive nhiều lần hơn số lần send đã được gọi trong encode tương ứng. Bạn được phép gọi receive ít hơn số lần đó. Chỉ được gọi send trong encode và receive trong decode.

Nếu một lời gọi không thỏa mãn các điều kiện trên, chương trình bị kết thúc ngay và nhận kết quả Not correct cho bộ dữ liệu tương ứng. Bạn không được ghi ra đầu ra chuẩn hoặc đọc từ đầu vào chuẩn; nếu vi phạm, bạn có thể nhận kết quả Security violation!.

Mã nguồn phải chứa #include "communication.h". Bạn cài đặt encode và decode, không viết hàm main. Không thể dựa vào bộ nhớ dùng chung giữa phía mã hóa và phía giải mã, vì chúng được gọi trong những lần chạy chương trình khác nhau.

Lưu ý kỹ thuật

1. Không có bảo đảm rằng các lời gọi decode xuất hiện theo cùng thứ tự với các lời gọi encode tương ứng.
2. Giới hạn thời gian và thời gian chạy hiển thị trong CMS chính thức được tính theo thời gian trung bình của các lời gọi trong một lần chạy chương trình. Cụ thể, nếu một lần chạy có \(K\) lời gọi encode hoặc \(K\) lời gọi decode, tổng thời gian của lần chạy ấy không được vượt quá \(K\cdot0.005\) giây. Mỗi lần chạy được bảo đảm có ít nhất \(50\) lời gọi encode hoặc decode.
3. Giới hạn bộ nhớ được tính theo lượng bộ nhớ lớn nhất sử dụng tại bất kỳ thời điểm nào trong quá trình chạy.

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

Gói đính kèm của bài trên CMS chính thức có communication.h, trình chấm mẫu sample_grader.cpp và chương trình mẫu communication_sample.cpp. Bạn có thể liên kết bài làm với trình chấm mẫu; hướng dẫn nằm trong sample_grader.cpp. Chẳng hạn, đặt communication.cpp, communication.h và sample_grader.cpp trong cùng thư mục rồi chạy:

g++ -std=c++17 sample_grader.cpp communication.cpp
./a.out

Để đơn giản, trình chấm mẫu không chạy chương trình hai lần mà gọi cả encode và decode, mỗi hàm đúng một lần, trong cùng một lần chạy. Vì vậy, hành vi này khác với trình chấm thật.

Trình chấm mẫu trước tiên đọc hai số nguyên \(N\) và \(X\), với \(1\le X\le N\), từ đầu vào chuẩn. Sau đó, nó gọi encode(N, X) và ghi nhật ký mọi lời gọi send ra đầu ra chuẩn. Với mỗi lời gọi send, bạn nhập giá trị trả về cho lời gọi đó qua đầu vào chuẩn.

Tiếp theo, trình chấm gọi decode(N) và ghi nhật ký mọi lời gọi receive. Khi kết thúc, nó in một trong các thông báo sau:

• Invalid input.: dữ liệu nhập cho trình chấm không đúng định dạng trên.
• Invalid send.: gọi send trong decode, hoặc gọi send với tham số khác \(0\) và \(1\).
• Invalid reply to send.: giá trị trả về được nhập cho send không phải \(0\) hoặc \(1\), hoặc khác tham số của send hai lần liên tiếp.
• Looks (and smells) fishy.: gọi send quá \(250\) lần.
• Invalid receive.: gọi receive trong encode.
• Assistant waiting for Godot.: gọi receive nhiều lần hơn send.
• Invalid answer.: decode không trả về một cặp số nguyên trong đoạn từ \(1\) đến \(N\).
• Wrong answer.: cặp do decode trả về không chứa thông điệp ban đầu \(X\).
• Correct: w signal(s) sent.: cặp do decode trả về chứa \(X\) và đã có \(w\) lần gọi send.

Các thông báo trên giữ nguyên cách viết trong PDF chính thức. Trình chấm thật chỉ in Not correct khi có bất kỳ lỗi nào ở trên, hoặc Correct: w signal(s) sent.. Trình chấm thật còn có tính thích ứng: các tham số \(N\), \(X\) và các giá trị trả về của send có thể phụ thuộc vào hành vi của chương trình trong lần chạy hiện tại cũng như những lần chạy khác. Cả trình chấm mẫu và trình chấm thật đều tự động kết thúc chương trình khi có lỗi. Việc đọc và ghi các luồng chuẩn ở phần chạy thử do trình chấm mẫu thực hiện.

Ràng buộc

• \(3\le N\le10^9\).
• \(1\le X\le N\).
• Giới hạn thời gian: trung bình \(0.005\) giây cho mỗi lời gọi, theo cách tính ở phần lưu ý kỹ thuật.
• Giới hạn bộ nhớ: \(8\) MiB.

Phân nhóm

1. \(15\) điểm: \(N=3\).
2. Tối đa \(85\) điểm: không có ràng buộc thêm. Điểm phụ thuộc vào số tín hiệu lớn nhất \(w_{\max}\) đã gửi trong tất cả các thông điệp của các bộ dữ liệu thuộc phân nhóm này.

Điểm của phân nhóm \(2\) được xác định bởi hàm tuyến tính từng đoạn trong hình sau, rồi làm tròn đến số nguyên gần nhất duy nhất. Trục đứng score biểu diễn số điểm; trục ngang là \(w_{\max}\).

Cụ thể, trước khi làm tròn, số điểm là:

Các mốc của đồ thị là \((100,85)\), \((110,65)\), \((140,35)\), \((200,15)\) và \((250,5)\). Để đạt điểm tối đa, không được gọi send quá \(100\) lần cho bất kỳ thông điệp nào trong phân nhóm \(2\).

Ví dụ giao tiếp

Xét \(N=1337\) và \(X=42\). Đầu tiên, trình chấm gọi encode(1337, 42). Một quá trình giao tiếp có thể diễn ra như sau; mũi tên chỉ giá trị trả về:

send(1) -> 0
send(0) -> 0
send(1) -> 1
send(1) -> 0

Lần đầu phát nhầm tín hiệu. Lần thứ hai phát đúng, như đã được bảo đảm. Lần thứ ba tiếp tục phát đúng, còn lần thứ tư phát nhầm.

Sau đó, trong một lần chạy mới của chương trình, trình chấm gọi decode(1337). Một quá trình giao tiếp có thể là:

receive() -> 0
receive() -> 0
receive() -> 1
return {1337, 42}

Lời gọi receive đầu tiên trả về \(0\), là giá trị thực sự được trả về bởi lần gọi send đầu tiên, dù khác tham số đã truyền vào lần gọi ấy. Hai lời gọi tiếp theo lần lượt nhận các giá trị trả về của lần gọi send thứ hai và thứ ba. Cặp trả về chứa \(42\), nên câu trả lời đúng và được chấp nhận. Chương trình còn được phép gọi receive thêm một lần nữa.

Bạn đã không thể dừng lại ở việc tưởng tượng... Bạn thật sự thực hiện vụ đột nhập, và lúc đầu mọi chuyện diễn ra đúng kế hoạch. Nhưng việc liên lạc với trợ lý lại hỏng bét — cũng dễ đoán mà, phải không? Thay vì trở về Lübeck an toàn, giờ bạn mắc kẹt trên một hòn đảo nhỏ, còn tàu ngầm thì hết nhiên liệu.

Để về kịp lễ trao giải BOI, bạn phải đến được chuyến phà ở phía bên kia đảo. Tuy nhiên, cư dân địa phương có những truyền thống kỳ lạ. Cà vạt rất quan trọng với họ, và mỗi ngôi làng có một màu cà vạt yêu thích, có thể thay đổi theo thời gian.

Một bài viết trên mạng cho biết ban đầu các làng khác nhau thích các màu cà vạt khác nhau. Đáng tiếc là bài viết đã quá cũ. Kể từ đó, mỗi tuần có đúng một ngôi làng thuyết phục một làng láng giềng chuyển sang thích cùng màu cà vạt với mình. Hai làng là láng giềng nếu được nối trực tiếp bởi một con đường. Việc thuyết phục chỉ có thể xảy ra nếu tổng số người trên toàn đảo thích màu cà vạt của làng thứ nhất ít nhất bằng tổng số người thích màu cà vạt của làng thứ hai. Thời gian đã trôi qua đủ lâu để giờ đây tất cả cư dân trên đảo đều thích cùng một màu cà vạt.

Bạn gần như chắc chắn rằng dân đảo sẽ không cho mình đi qua nếu không đeo cà vạt đúng màu họ thích. Vì vậy, để đến được phà, bạn định đeo một chiếc cà vạt cho mỗi màu mà dân đảo có thể đang thích. Nhưng đeo quá nhiều cà vạt lại khiến bạn trông đáng ngờ. Hãy viết chương trình dựa trên mô tả hòn đảo để xác định những màu cà vạt bạn cần đeo.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(M\), lần lượt là số làng và số đường trên đảo. Các làng được đánh số từ \(1\) đến \(N\).

Dòng tiếp theo chứa \(N\) số nguyên \(s_1,\ldots,s_N\), trong đó \(s_i\) là số dân của làng \(i\).

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(a,b\), với \(1\le a,b\le N\) và \(a\ne b\), biểu thị một con đường nối làng \(a\) với làng \(b\). Từ bất kỳ làng nào cũng có thể đi đến mọi làng khác, trực tiếp hoặc qua các làng trung gian.

Dữ liệu ra

In một chuỗi độ dài \(N\) chỉ gồm các ký tự 0 và 1. Ký tự thứ \(i\) bằng 1 khi và chỉ khi có thể xảy ra việc tất cả cư dân trên đảo hiện nay đều thích màu cà vạt mà làng \(i\) yêu thích ban đầu.

Ràng buộc

• \(1\le N\le200\,000\).
• \(0\le M\le200\,000\).
• \(1\le s_i\le10^9\) với \(1\le i\le N\).
• Giới hạn thời gian: \(1\) giây.
• Giới hạn bộ nhớ: \(512\) MiB.

Phân nhóm

1. \(10\) điểm: \(N\le2\,000\) và \(M\le2\,000\).
2. \(10\) điểm: \(s_1\ge s_2\ge\cdots\ge s_N\), và mỗi làng \(b>1\) được nối trực tiếp với đúng một làng \(a\) có \(a<b\).
3. \(15\) điểm: hai làng \(a,b\) được nối trực tiếp khi và chỉ khi \(|a-b|=1\).
4. \(30\) điểm: có nhiều nhất \(10\) giá trị khác nhau trong các số dân \(s_1,\ldots,s_N\).
5. \(35\) điểm: không có ràng buộc thêm.

Ví dụ

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

1110

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

1110

Sau khi vượt qua được những truyền thống địa phương, bạn đến kịp chuyến phà ngay trước giờ khởi hành. Tuy nhiên, bạn không ngờ lại có nhiều người đi Lübeck đến thế! Vì không muốn muộn lễ trao giải — bạn còn cần thời gian cất toàn bộ tác phẩm nghệ thuật lấy được vào nhà trọ — bạn muốn đẩy nhanh việc lên phà.

Phà có một hàng gồm \(N\) ghế, được đặt kín bởi \(N\) hành khách. Vé của mỗi người ghi ghế được chỉ định và một trong \(G\) nhóm lên phà. Các nhóm lần lượt được gọi lên phà. Những người trong cùng một nhóm lên theo thứ tự ngẫu nhiên, với mọi thứ tự có xác suất như nhau. Mỗi hành khách có thể lên từ đầu hoặc cuối hàng ghế, rồi đi đến ghế của mình trước khi người tiếp theo lên.

Bạn nhận thấy việc tốn thời gian nhất là khi một hành khách phải đi ngang qua người đã ngồi trên ghế: hành lý chứa tất cả những chiếc cà vạt ấy là một chướng ngại đáng kể trên lối đi. May thay, bạn tìm thấy một bộ đồng phục nhân viên trong tủ gần đó, nên có thể quyết định thứ tự các nhóm lên phà và thông báo cho từng hành khách, trước khi bắt đầu lên phà, rằng họ phải lên từ đầu hay cuối hàng ghế.

Hãy viết chương trình dùng thông tin trên vé để tính kỳ vọng nhỏ nhất của tổng số lần một hành khách đi ngang qua người đã ngồi, khi bạn chọn tối ưu cả thứ tự các nhóm và hướng lên phà của từng hành khách.

Chú thích

Với một thứ tự các nhóm và một cách chỉ định hướng lên phà cho từng hành khách, kỳ vọng của số lần đi ngang qua được định nghĩa là

trong đó \(p_k\) là xác suất có đúng \(k\) lần đi ngang qua người đã ngồi trong quá trình lên phà. Nói cách khác, đây là số lần đi ngang qua trung bình khi xét mọi thứ tự có thể của các hành khách trong từng nhóm.

Dữ liệu vào

Dữ liệu vào gồm một chuỗi \(N\) ký tự \(s_1\ldots s_N\). Ký tự \(s_i\) là một trong \(G\) chữ cái in hoa đầu tiên của bảng chữ cái tiếng Anh, biểu thị nhóm lên phà của hành khách được chỉ định ngồi ở ghế thứ \(i\). Ghế ở đầu hàng được đánh số \(1\).

Dữ liệu ra

In một số duy nhất: kỳ vọng nhỏ nhất của số lần đi ngang qua người đã ngồi, khi chọn tối ưu thứ tự các nhóm và hướng lên phà của từng hành khách. Đáp án được chấp nhận nếu sai số tuyệt đối không vượt quá \(0.001\).

Ràng buộc

• \(1\le G\le15\).
• \(1\le N\le100\,000\).
• Giới hạn thời gian: \(2\) giây.
• Giới hạn bộ nhớ: \(1024\) MiB.

Phân nhóm

1. \(5\) điểm: \(G=1\), tức là chỉ có một nhóm lên phà.
2. \(25\) điểm: \(G\le7\) và \(N\le100\).
3. \(30\) điểm: \(G\le10\) và \(N\le10\,000\).
4. \(40\) điểm: không có ràng buộc thêm.

Ví dụ

AACCAA

1

HEHEHEHIHILOL

7.5

ONMLKJIHGFEDCBAABCDEFGHIJKLMNO

0

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

100800.5