Giải đấu (khá liên quan đến tổ hợp)

[An_Nguyen (An Nguyễn)]

Mọi người cho e hỏi bài này với ạ:
Trong một giai đấu với n người tham gia, mỗi trận đấu được chơi tại một thời điểm và người thua bị loại ra. Trong mỗi trận đấu, số chiến thắng của 2 người tham gia từ trước tới giơ hơn kém nhau không nhiều hơn 1. Vậy số lượng tối đa các trận đấu của người chiến thắng giải là bao nhiêu??
INPUT:
Nhập vào số n(1<=n<=105)
OUPUT:
Kết quả tương ứng.
Ví dụ:
IP: 5
OP: 3

[tntxtnt]

có liên quan gì tới tổ hợp đâu nhỉ :V

liên quan tới dãy Fibonacci @_@

để có 1 đội thắng 1 trận, cần 2 đội thắng 0 trận đấu với nhau
để có 1 đội thắng 2 trận, cần 1 đội thắng 1 trận và 1 đội thắng 0 trận, vậy cần tổng cộng 2 + 1 = 3 đội
để có 1 đội thắng 3 trận, cần 1 đội thắng 2 trận và 1 đội thắng 1 trận, vậy cần tổng cộng 3 + 2 = 5 đội
để có 1 đội thắng 4 trận, cần 1 đội thắng 3 trận và 1 đội thắng 2 trận, vậy cần tổng cộng 5 + 3 = 8 đội
v.v…

hình minh họa

1 2 3 4 5 6 7 8 9101112131415161718192021
0┬0 0 0┬0 0┬0 0 0┬0 0 0┬0 0┬0 0 0┬0 0┬0 0
 1─┬┘  1   1─┬┘  1─┬┘  1   1─┬┘  1   1─┬┘
   2─┬─┘     2     2─┬─┘     2─┬─┘     2
     3───┬───┘       3         3───┬───┘
         4─────┬─────┘             4
               5─────────┬─────────┘
                         6

tạo dãy Fibonacci tới khi nào nhiều hơn n đội là ra bao nhiêu trận thắng :V

#include <utility>

int maxWins(int n) {
    int w = 0;
    for (int a = 1, b = 2; b <= n; w++) a = std::exchange(b, a + b);
    return w;
}

test: https://rextester.com/RDGVT56691

[An_Nguyen (An Nguyễn)]

exchange là cái gì thế ạ?

[tntxtnt]

Em tự viết lại cái vòng lặp fibo của em cũng đc mà :V

a = exchange(b, c)

Đồng nghĩa với

temp = b
b = c
a = temp

3 dòng còn 1 dòng

exchange(a, b) nghĩa là gán a = b và trả về a cũ