123Code...

Nội dung Bài tập

Mã:: TeamOLP

Tên:: Xây dựng đội tuyển OLP

Dạng thi:: oi

Thang điểm:: 100 điểm

Giới hạn thời gian:: 1 giây

Giới hạn bộ nhớ:: 256 MB

Được tạo bởi:: Shido

: Share

John và Ken đang tham gia olympic cờ vua nên họ muốn luyện tập xây dựng đội nhóm. Họ tập hợp n người chơi mà ở đó n là lũy thừa của 2 và họ sẽ chơi thể thao. John và Ken cũng nằm trong n người đó.Một trong những môn thể thao là kéo co với mỗi 1 <= i <= n người thứ i có sửa mạnh S_i . Các vòng loại sẽ được tổ chức cho đến khi chỉ còn 1 người - người đó được gọi là người chiến thắng tuyệt đối Ở mỗi vòng - Giả sử rằng m > 1 , người chơi vẫn còn trong trò chơi ở đó mà m là lũy thừa của 2 - m người chia được chia ra 2 đội với slố lượng thành viên bằng nhau (tức là m /2 các người chơi trong mỗi đội) . Sức mạnh cả đội là tổng sức mạnh các người chơi - Nếu hai đội có sức mạnh ngang nhau thì John sẽ chọn ra ai thắng ngược lại thì đội mạnh hơn sẽ thắng - Mọi người chơi của đội thua sẽ bị loại , do đó vẫn còn m /2 người chơi John đã biết rõ sức mạnh của từng người chơi và đang tự hỏi ai có thể trở thành người chiến thắng tuyệt đối và ai không thể nếu anh ta có thể chọn cách thành lập các đội trong mỗi hiệp đấu cũng như đội chiến thắng trong trường hợp sức mạnh 2 bên ngang bằng nhau Input - Dòng đầu gồm 1 số nguyên duy nhất (4 <= n <=32) - số lượng người chơi tham gia kéo co. Đảm bảo rằng n là lũy thừa của 2 - Dòng thứ hai bao gồm 1 chuỗi s₁, s₂ , ... ,s_n của số nguyên (1 <= s_i<= 10¹⁵) - sức mạnh của từng người chơi Output - 1 dòng duy nhất in ra chuỗi nhị phân có độ dài n - kí tự thứ i của chuỗi là 1 nếu người đó có thể trở thành người chiến thắng tuyệt đối và ngược lại là 0 Ví dụ 1: Input Output 4 60 32 59 87 1001 Ví dụ 2: Input Output 4 100 100 100 100 1111 Ví dụ 3: Input Output 8 8 8 8 8 4 4 4 4 11110000 Ví dụ 4: Input Output 32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 00000000000000001111111111111111 Giải thích Ở testcase đầu tiên , người chơi 1 và 4 với sức mạnh tương ứng là 60 và 87 trở thành người chiến thắng tuyệt đối Quá trình người chơi 1. Đầu tiên , chia thành hai nhóm [1,3] và [2,4] . Sức mạnh của 2 đội là 60 + 59 = 119 và 32 + 87 = 119 . Hai đội ngang nhau John có thể chọn 1 trong 2 đội. Giả sử John chọn đội [1,3] Ta còn lại người chơi 1 và người chơi 3 . Vì người chơi 1 mạnh hơn người chơi 3 (60 >59) họ được tuyên bố là người chiến thắng tuyệt đối vì họ là người chơi cuối cùng còn lại Ở testcase thứ ba , sức mạnh những người người còn lại có thể giống như [8,8,8,8,4,4,4,4] -> [8,8,4,4] -> [8,4] -> [8]. Mỗi người có sức mạnh 8 có thể trở thành người chiến thắng tuyệt đối còn những người còn lại thì không
Quảng cáo