Hướng dẫn giải

Có N học sinh, mỗi người biết một câu chuyện riêng. Mỗi tin nhắn chỉ gửi cho một người và người gửi chia sẻ mọi câu chuyện đã biết. Cần tìm số tin nhắn ít nhất để ai cũng biết đủ N câu chuyện.

Cách làm

Kết quả chỉ phụ thuộc vào N:

• Nếu N = 1 thì chỉ có một học sinh đã biết đủ mọi câu chuyện, không cần gửi tin nhắn nào, đáp số là 0.
• Nếu N >= 2 thì cần đúng 2*N - 2 tin nhắn. Cách làm: N - 1 học sinh lần lượt gửi tất cả câu chuyện của mình cho một người "trung tâm" để người đó biết đủ mọi thứ, sau đó người trung tâm gửi lại cho N - 1 người còn lại.

Với N = 2 ta được 2 tin nhắn, khớp với ví dụ. Số lớn nhất là 2*10^5 nên int là đủ, nhưng dùng long long cho an toàn.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        if (n == 1) {
            // Chỉ có một học sinh, không cần gửi tin nhắn nào
            cout << 0 << "\n";
        } else {
            // Cần gửi đúng 2*n - 2 tin nhắn
            cout << 2 * n - 2 << "\n";
        }
    }
    return 0;
}