Tìm đội thắng cuộc trong trận bóng chuyền từ chuỗi nhị phân trong Python

Cho một chuỗi nhị phân biểu diễn điểm số của trận bóng chuyền, ta cần xác định đội thắng dựa trên các quy tắc:

• Hai đội thi đấu, đội nào đạt 15 điểm trước thắng, trừ khi cả hai đều đạt 14 điểm.
• Khi cả hai đều đạt 14 điểm, đội nào dẫn trước 2 điểm sẽ thắng.

Trong chuỗi nhị phân, 0 đại diện cho đội mất điểm, 1 đại diện cho đội ghi điểm. Ta cần kiểm tra đội có thắng hay thua.

Ví dụ, nếu đầu vào là "1001100110111001110011011", kết quả sẽ là Team won.

Thuật toán giải quyết

• Khởi tạo score_cnt := [0, 0].
• Duyệt qua chuỗi score:
  • pos := ord(score[i]) - ord('0').
  • Tăng score_cnt[pos].
  • Nếu score_cnt[0] == n và score_cnt[1] < n - 1: trả về "Team lost".
  • Nếu score_cnt[1] == n và score_cnt[0] < n - 1: trả về "Team won".
  • Nếu cả hai đều bằng n - 1 (14): reset score_cnt về 0 và thoát vòng lặp.
• Tiếp tục duyệt từ vị trí hiện tại:
  • Cập nhật score_cnt.
  • Nếu |score_cnt[0] - score_cnt[1]| == 2:
    • Nếu score_cnt[0] > score_cnt[1]: trả về "Team lost".
    • Ngược lại: trả về "Team won".

Ví dụ minh họa

def predictWinner(score, n):
    score_cnt = [0, 0]
    for i in range(len(score)):
        pos = ord(score[i]) - ord('0')
        score_cnt[pos] += 1
        if score_cnt[0] == n and score_cnt[1] < n - 1:
            return "Team lost"
        if score_cnt[1] == n and score_cnt[0] < n - 1:
            return "Team won"
        if score_cnt[0] == n - 1 and score_cnt[1] == n - 1:
            score_cnt[0] = 0
            score_cnt[1] = 0
            break
    i += 1
    for i in range(i, len(score)):
        pos = ord(score[i]) - ord('0')
        score_cnt[pos] += 1
        if abs(score_cnt[0] - score_cnt[1]) == 2:
            if score_cnt[0] > score_cnt[1]:
                return "Team lost"
            else:
                return "Team won"

score = "1001010101111011101111"
n = 15
print(predictWinner(score, n))  # Team won

Đầu vào

"1001010101111011101111"

Đầu ra

Team won