Chương trình đếm số trận đấu trong giải đấu trong Python

Giả sử ta có số n đội thi đấu. Quy tắc giải đấu:

• Nếu số đội chẵn: mỗi đội ghép đôi, chơi n/2 trận, n/2 đội thắng lên vòng sau.
• Nếu số đội lẻ: 1 đội tự động lên vòng, phần còn lại ghép đôi, chơi (n-1)/2 trận, (n-1)/2 + 1 đội lên vòng sau.

Tìm tổng số trận đấu để ra được vô địch.

Ví dụ: n = 10, kết quả là 9.

Giải thuật

1. ans := 0
2. While n != 1:
   • f := n // 2
   • remainder := n % 2
   • ans += f
   • n := f + remainder
3. Trả về ans

Ví dụ (Python)

def solve(n):
    ans = 0
    while n != 1:
        f = n // 2
        remainder = n % 2
        ans += f
        n = f + remainder
    return ans

n = 10
print(solve(n))

Input

10

Output

9