Chọn đội tuyển

Điểm: 0,01 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: CHONDOI.INP

Output: CHONDOI.OUT

Tác giả:

bedao

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Để chuẩn bị cho kỳ thi học sinh giỏi tỉnh, thầy Minh muốn thành lập đội tuyển học sinh giỏi môn tin gồm ~3~ học sinh từ ~N~ học sinh, tên học sinh thứ ~i~ là ~S_i~. Vì các học sinh của thầy đều học giỏi nên thầy phải đưa ra điều kiện chọn đội như sau:

Tên của mỗi học sinh được chọn phải bắt đầu bằng kí tự H, S, G, P, hoặc T.
Tên các em học được chọn phải có chữ cái đầu đôi một khác nhau.

Yêu cầu: Em hãy viết chương trình cho biết thầy Minh có bao nhiêu cách chọn đội tuyển gồm ~3~ học sinh thoả mãn điều kiện trên.

Input

Vào từ tệp văn bản CHONDOI.INP:

Dòng ~1~ chứa số nguyên dương ~N~ (~1 \le N \le 10^5~)
~N~ dòng sau, dòng thứ ~i~ là tên học sinh ~S_i~ (không có hai học sinh nào có tên giống nhau) có độ dài không quá ~10~ chỉ gồm các kí tự chữ cái in hoa.

Output

Đưa ra tệp CHONDOI.OUT một số nguyên là số các chọn ~3~ học sinh vào đội tuyển thoả mãn điều kiện trên.

Sample Input 1

5
HONG
SANG
GIANG
ANH
HANH

Sample Output 1

Notes

(Hai cách chọn 3 học sinh thoả mãn điều kiện: (HONG, SANG, GIANG); (SANG, GIANG, HANH))

Bình luận

Hãy đọc nội quy trước khi bình luận.

6
quangthenpc đã bình luận lúc 6, Tháng 4, 2025, 11:15 ← sửa 2 →
!SPOILER! (sẽ rất khó hiểu cho những ai chưa biết về tổ hợp)

Áp dụng tổ hợp và phép nhân trong quy tắc đếm (Xem thêm tại: https://vietjack.com/toan-10-kn/ly-thuyet-bai-23-quy-tac-dem.jsp).

Kết quả là: (Tổng số cách chọn 3 học sinh trong m học sinh có chữ cái đầu hợp lệ) - (Tổng số cách chọn 3 học sinh trong n học sinh có chữ cái đầu hợp lệ mà có 2 hoặc 3 học sinh trùng nhau).

Gọi m là tổng số học sinh có chữ cái đầu hợp lệ.

Để tính tổng số cách chọn 3 học sinh (gọi là sum) thì ta nhận ra rằng k = 3, nên công thức tổ hợp là: $$ C_m^3 = \frac{m * (m - 1) * (m - 2)}{6} $$ Để tính tổng số cách chọn 3 học sinh mà trong đó có 2 hoặc 3 học sinh có chữ cái đầu trùng nhau thì ta chia ra 5 trường hợp tương ứng với 5 chữ cái H, S, G, T, P.

Gọi a là tần suất của học sinh có chữ cái đầu c với c thuộc {H, S, G, T, P}.

Nếu a = 2 thì luôn có m - 2 cách.

Nếu a > 2 thì được tính như sau: $$ C_a^2 * (m - a) + C_a^3 = \frac{a * (a - 1)}{2} * (m - a) + \frac{a * (a - 1) * (a - 2)}{6} $$ Sau khi tính thì ta lấy sum trừ đi cho kết quả vừa rồi và thực hiện với các chữ cái c còn lại.

Code: https://onlinegdb.com/wpvEioEQH