Đề bài
Cho N câu hỏi trong một bài kiểm tra và K học sinh trong lớp. Trong nhóm K học sinh, N học sinh ghi nhớ chính xác một câu hỏi mỗi người. Một email có thể chứa tối đa X câu hỏi.
Tìm số lượng email tối thiểu cần thiết để toàn bộ lớp biết được tất cả các câu hỏi.
Nếu N = 3, K = 3, X = 1 thì phải gửi 6 email:
- Học sinh 1 gửi câu hỏi của mình cho học sinh 2 và học sinh 3 (2 email),
- Học sinh 2 và học sinh 3 cũng làm tương tự nên tổng số email = 2 * 3 = 6
Thuật toán
Câu trả lời cuối cùng có thể được tính bằng công thức sau:
ceil(N/X) * (K-N) + (( ceil((N-1)/X)) * (N-1)) + (N-1)
Ví dụ
#include <iostream> #include <cmath> using namespace std; int minMailsToBeSent(int n, int k, int x){ int m = (n - 1) + ceil((n - 1) * 1.0 / x) * (n - 1) + ceil(n * 1.0 / x) * (k- n); return m; } int main(){ int questions = 3; int students = 3; int X = 1; cout << "No of mails to be sent: " << minMailsToBeSent(questions, students, X) << endl; return 0; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
No of mails to be sent: 6