Nguồn đề bài: http://vn.spoj.com/problems/BONES/
1. Đề bài BONES spoj
Bessie rất yêu thích chơi những trò chơi đổ xúc xắc và cô bò này đã nài được bác nông dân John chở tới cửa hàng đồ chơi và cô bò đã mua 3 cái xúc xắc về để lăn.
Những viên xúc xắc này tương ứng có S1, S2 và S3 mặt đều nhau, các mặt được đánh số từ 1->S1, 1->S2 và 1->S3 (2 <= S1 <= 20; 2 <= S2 <= 20; 2 <= S3 <= 40).
Bessie cứ thả xúc xắc liên tục và mỗi lần lại ghi nhận lại 1 số nguyên là tổng giá trị của 3 mặt xúc xắc thả được. Mục đích của cô bò là để tìm ra xem tổng giá trị nào xuất hiện nhiều nhất.
Cho số mặt của 3 xúc xắc, hãy xác định xem tổng giá trị nào xuất hiện nhiều nhất. Nếu có nhiều hơn 1 giá trị xuất hiện nhiều nhất thì ghi ra giá trị nhỏ nhất.
DỮ LIỆU
- Dòng 1: 3 số nguyên cách nhau bởi dấu cách: S1, S2 và S3
KẾT QUẢ
- Dòng 1: Số nguyên nhỏ nhất là tổng giá trị xuất hiện nhiều lần nhất, giả sử rằng xác suất các mặt xúc xắc xuất hiện là như nhau.
VÍ DỤ
Dữ liệu
3 2 3
Kết quả
5
GIẢI THÍCH
Đây là tất cả các trường hợp có thể xảy ra. 1 1 1 -> 3 1 2 1 -> 4 2 1 1 -> 4 2 2 1 -> 5 3 1 1 -> 5 3 2 1 -> 6 1 1 2 -> 4 1 2 2 -> 5 2 1 2 -> 5 2 2 2 -> 6 3 1 2 -> 6 3 2 2 -> 7 1 1 3 -> 5 1 2 3 -> 6 2 1 3 -> 6 2 2 3 -> 7 3 1 3 -> 7 3 2 3 -> 8 Trong đó 5 và 6 xuất hiện nhiều nhất (mỗi số 5 lần), vậy 5 là kết quả.
2. Code tham khảo BONES spoj
Bài này khá đơn giản với ý tưởng ĐPT O(S1*S2*S3):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | const fi=''; var f:text; s1,s2,s3:byte; A:array[0..100] of longint; procedure xuli; var m,n,p:byte; lon,k,i,tam:word; begin fillchar(a,sizeof(a),0); for m:=1 to s1 do for n:=1 to s2 do for p:=1 to s3 do inc(a[m+n+p]); lon:=0; for i:=1 to 100 do begin if (a[i]>lon) then begin lon:=a[i]; k:=i; end; end; writeln(k); end; begin assign(f,fi); reset(f); readln(f,s1,s2,s3); close(f); xuli; end. |
Bài viết liên quan
- P167PROE spoj PTIT – ROUND 7E – Phương trình
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- PTIT016D spoj PTIT- ACM PTIT 2016 D – Biểu thức
- Spoj PTIT PTIT016C – ACM PTIT 2016 C – Chẵn lẻ
- PTIT127A spoj PTIT – Tổ chức kì thi
- P164SUMI spoj PTIT – ROUND 4I – Next round
- PTIT135J spoj PTIT – Tính lãi suất
- P156SUME spoj PTIT – ROUND 6E – Ước chung của chuỗi
- P156PROE spoj PTIT – ROUND 6E – Phép dịch
- P156SUMH spoj PTIT – ROUND 6H – Kim cương
Sửa lại độ phức tạp O(S1*S2*S3) bạn ui !
Oke, cảm ơn bạn đã góp ý.