VuaTenMien.Com: Các câu hỏi phỏng vấn [38]

Thứ Tư, 16 tháng 3, 2011

Bạn có 2 cái lọ và 100 viên bi trong đó có 50 viên đỏ và 50 viên xanh. Giả sử mỗi lọ đủ lớn để đựng hết số bi. Hãy dàn xếp 100 bi vào 2 lọ sao cho, nếu ta lấy ngẫu nhiên một lọ và chọn ngẫu nhiên một bi trong lọ thì xác suất được bi đỏ là tối đa.
Cho $n$ cặp số $(a_i, b_i), i \in [n]$ . Bạn không có quyền tráo đổi các con số giữa các cặp, nhưng bạn có quyền hoán chuyển $a_i \leftrightarrow b_i$ . Hãy thiết kế một thuật toán hoán chuyển bên trong từng cặp, và hoán chuyển vị trí của các cặp, sao cho cuối cùng thi ta có $a_1 \leq \cdots \leq a_n$ và $b_1 \geq \cdots \geq b_n$ . Thuật toán in ra “không tồn tại” nếu mà không tồn tại một cách hoán chuyển như vậy. (Credit: bài chôm từ TCS stackexchange.)