Tuyên bố vấn đề
Đưa ra N câu hỏi trong một bài kiểm tra và K học sinh trong lớp. Trong số học sinh K, học sinh N ghi nhớ chính xác một câu hỏi. Một thư có thể chứa tối đa X câu hỏi.
Tìm số lượng thư tối thiểu cần thiết để cả lớp biết về tất cả các câu hỏi
Nếu N =3, K =3, X =1 thì một người phải gửi 6 thư -
- 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 e-mail),
- Sinh viên 2 và sinh viên 3 cũng vậy nên tổng số thư =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 dưới đây -
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;
} Đầu ra
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