Bầu cua tôm cá
Đề bài
Hôm nay, CaiWinDao mở sòng bầu cua tôm cá. Sau khi 3 em gái đã đặt tiền, CaiWinDao bắt đầu rung xúc xắc. Vốn là một trùm bịp, CaiWinDao có khả năng rung được bất kỳ khả năng nào cho 3 viên xúc xắc trong tay (tất nhiên CaiWinDao chỉ có thể qua mặt được các em gái ngây thơ thôi).
Tuy là trùm bịp nhưng CaiWinDao rất thương các em, anh quyết định rung xúc xắc sao cho tổng số tiền các em gái thắng được là nhiều nhất (đồng nghĩa với CaiWinDao thua nhiều nhất...). Dù rất giỏi bịp nhưng CaiWinDao lại không thể tính toán kịp trong lúc bịp. Các bạn hãy giúp anh tạo ra một chương trình giúp tính toán số tiền CaiWinDao thua nhiều nhất nhé!
Luật chơi Bầu Cua Tôm Cá: Giả sử bạn là 1 em gái, bạn có thể đặt tiền vào một hay nhiều ô trong các ô Bầu, Cua, Tôm, Cá, Gà, Nai. Ví dụ bạn đặt $a$ đồng vào ô Cá:
- Nếu không có xúc xắc nào là Cá thì bạn mất trắng $a$ đồng đó vào tay CaiWinDao.
- Nếu có $b$ ($1 \le b \le 3$) xúc xắc có hình Cá thì bạn lấy lại $a$ đồng đã đặt và nhận thêm $a \times b$ đồng từ CaiWinDao.
Dữ liệu vào
- Dòng đầu tiên gồm ba số tự nhiên $a[1], a[2], a[3]$ là số ô các em gái đặt ($1 \le a[i] \le 6$).
- Sau đó là 3 khối dữ liệu. Mỗi khối là $a[i]$ dòng biểu diễn các ô mà em gái thứ $i$ đặt tiền, mỗi dòng chứa 2 số: $x\ y$.
- Trong đó $x$ là số thứ tự của ô và $y$ là số tiền đặt vào ô đó ($1 \le x \le 6$, $1 \le y \le 20$). Các số $x$ trong mỗi khối khác nhau. Ta quy ước các ô là 1, 2, 3, 4, 5, 6 thay cho Bầu, Cua, Tôm, Cá, Gà, Nai.
Dữ liệu ra
- In ra số tiền lớn nhất CaiWinDao có thể thua.
1 2 3
1 10
2 5
6 5
2 3
3 2
4 3181 1 1
1 10
1 10
1 1090Giải thích ví dụ 1:
- Em gái 1 đặt 1 cửa: 10 đồng cho ô 1.
- Em gái 2 đặt 2 cửa: 5 đồng cho ô 2 và 5 đồng cho ô 6.
- Em gái 3 đặt 3 cửa: 3 đồng cho ô 2, 2 đồng cho ô 3, và 3 đồng cho ô 4.
CaiWinDao sẽ rung ra các ô 1, 2, 6. Khi đó CaiWinDao sẽ đưa cho em thứ nhất 10đ, em thứ hai 10đ, và lấy của em thứ ba 2đ. Số tiền bỏ ra là 18đ.
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesHiểu luật chơi bầu cua tôm cá
Trò chơi bầu cua tôm cá này rất phổ biến, đặc biệt vào các dịp Tết là thấy nhiều nhất :)) Nên mình nghĩ chắc bạn nào cũng biết luật chơi rồi đúng không? Cho những ai không biết thì mình giải thích nhanh: tổng cộng có 6 ô, mình ký hiệu từ 1 đến 6 cho tiện nhé:
Người chơi đặt tiền cược cho các ô. Người chủ trò có 3 viên xúc xắc, mỗi viên có 6 mặt từ 1 đến 6, để lên dĩa, đậy bát lại rồi xóc lên. Mở bát ra, với mỗi viên xúc xắc ta xét mặt trên cùng của nó: người chơi nào đặt tiền đúng ô trùng với mặt đó thì giữ nguyên tiền của mình và nhận thêm đúng bằng nhiêu đó tiền từ chủ trò; còn ô đã đặt mà không xuất hiện ở viên nào thì người chơi mất số tiền đã đặt ở ô đó. Quy luật trên xét lần lượt cho cả 3 viên xúc xắc.
Ví dụ: người chơi đặt ô 1: 3 đồng, ô 3: 5 đồng, ô 6: 7 đồng. Kết quả 3 viên xúc xắc là:
Không có quy định người chơi phải đặt mấy ô, có thể tùy ý từ 1 đến 6. Như ví dụ trên nếu chỉ đặt mỗi ô 1 là 3 đồng thì người chơi lời 3 đồng; còn nếu chỉ đặt mỗi ô 6 là 7 đồng thì người chơi lỗ 7 đồng.
Tóm tắt yêu cầu
Ta có danh sách các ô đặt cược và số tiền cụ thể của từng em gái. Việc của ta là xem kết quả 3 viên xúc xắc phải ra thế nào để thằng anh dại gái thua nhiều tiền nhất có thể. Đề không cần in ra kết quả 3 viên xúc xắc, chỉ cần in ra số tiền thua nhiều nhất đó.
Chính phần tóm tắt này đã gợi ý cho các bạn: chỉ cần biết 3 viên xúc xắc ra thế nào thì tính ra số tiền thua là rất đơn giản. Vấn đề là 3 viên xúc xắc sẽ phải ra thế nào?
Ý tưởng: vét cạn
Với bài này, vét cạn là thế nào? Đầu tiên ta thống kê tổng số tiền các em gái đặt cho từng ô (trong 6 ô). Sau đó xét tất cả trường hợp có thể xảy ra của 3 viên xúc xắc:
Cụ thể là $\{1,1,1\}, \{1,1,2\}, \ldots, \{1,1,6\}$ rồi $\{1,2,1\}, \ldots, \{1,2,6\}$, cứ thế cho đến $\{1,6,6\}$, rồi lại $\{2,1,1\}, \{2,1,2\}, \ldots$ và cuối cùng là $\{6,6,6\}$. Với mỗi trường hợp, ta tính được ngay tiền các em gái ăn được và tiền các em gái bị mất; lấy tiền ăn được trừ tiền mất sẽ ra tiền lời (dương là lời, âm là lỗ). Ta dùng biến Max lưu tiền lời lớn nhất các em gái ăn được từ thằng anh (đồng nghĩa là thằng anh lỗ nhất), đó chính là đáp án.
Kỹ thuật mảng đánh dấu
Tư tưởng rất rõ ràng nhưng bạn nào không xử lý khéo thì code sẽ dài dòng lắm. Ví dụ bước thống kê tiền đặt cho từng ô: nếu không khéo là phải tạo 6 biến tương ứng 6 ô, rồi xét điều kiện xem ô hiện tại là ô nào để cộng vào biến đó.
Sẽ gọn hơn rất nhiều nếu dùng mảng đánh dấu: tạo mảng a có 7 phần tử (index 0 đến 6), bỏ qua index 0, chỉ dùng index 1 đến 6 để khớp với đề tính ô từ 1. Khi đó a[i] chính là tổng số tiền các em gái đặt cho ô i. Ban đầu mọi phần tử bằng 0, mỗi lần đọc một dòng x y ta chỉ cần a[x] += y.
a mình đang nói ở đây nha. 3 em gái đứng chung một phe, nên 3 số này ta chẳng cần lưu mảng gì cả: cứ đọc lần lượt vào biến x rồi cộng dồn vào n, vòng lặp sau đó lặp đúng n lần để đọc hết các dòng đặt cược.Với ví dụ 1, sau khi đọc xong ta có mảng:
Ô 2 = 5 + 3 = 8 vì em gái 2 và em gái 3 cùng đặt ô 2.
Duyệt 216 trường hợp bằng 3 vòng lặp lồng nhau
Có mảng đánh dấu rồi thì bước tiếp theo khỏe re: dùng 3 vòng lặp for i, j, k chạy từ 1 đến 6 lồng nhau. Theo nguyên tắc vòng lặp lồng nhau, với mỗi giá trị của vòng lặp cha sẽ xét hết các giá trị của vòng lặp con, nên đủ $6^3 = 216$ trường hợp. Trong vòng lặp trong cùng, 3 giá trị i, j, k chính là 3 mặt kết quả:
- Tiền các em gái ăn được:
sum = a[i] + a[j] + a[k]. - Trừ tiền các ô không xuất hiện: duyệt thêm một vòng
for ltừ 1 đến 6, ôlnào khác đồng thời cải, j, kthìsum -= a[l]. - So sánh với
Max(khởi tạo bằngINT_MIN= −2 147 483 648, giá trị nhỏ nhất của kiểuint, để lần so sánh đầu tiên luôn cập nhật được).
a[i] + a[j] + a[k] lại đúng cả khi nhiều viên ra cùng một mặt?a[Cá] được cộng 3 lần, khớp đúng luật "có $b$ xúc xắc hình Cá thì nhận thêm $a \times b$ đồng". Ví dụ 2 chính là trường hợp này.Kiểm tra ví dụ 1 với kết quả 1, 2, 6:
Kiểm tra ví dụ 2: mảng có a[1] = 30, các ô khác bằng 0. Trường hợp tốt nhất là cả 3 viên đều ra ô 1:
Em nhập các ô và số tiền mà từng em gái đặt (dạng ô tiền, các cặp cách nhau bởi dấu phẩy), rồi bấm Tiếp: khung sẽ dựng mảng đánh dấu rồi vét cạn 216 trường hợp, dừng lại mỗi khi tìm được kỷ lục mới:
Source code
Source code cho các bạn tham khảo nếu làm theo tư tưởng mình trình bày ở trên:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x, y;
cin >> n >> x;
n += x;
cin >> x;
n += x;
int a[7] = {0};
while(n--){
cin >> x >> y;
a[x] += y;
}
int Max = INT_MIN;
for(int i = 1; i <= 6; ++i){
for(int j = 1; j <= 6; ++j){
for(int k = 1; k <= 6; ++k){
int sum = a[i] + a[j] + a[k];
for(int l = 1; l <= 6; ++l){
if(l != i && l != j && l != k){
sum -= a[l];
}
}
Max = max(Max, sum);
}
}
}
cout << Max;
return 0;
}import sys
data = sys.stdin.read().strip().split()
it = iter(data)
n = int(next(it))
x = int(next(it))
n += x
x = int(next(it))
n += x
a = [0] * 7
for _ in range(n):
x = int(next(it))
y = int(next(it))
a[x] += y
Max = -10**18
for i in range(1, 7):
for j in range(1, 7):
for k in range(1, 7):
total = a[i] + a[j] + a[k]
for l in range(1, 7):
if l != i and l != j and l != k:
total -= a[l]
if total > Max:
Max = total
print(Max)Giải thích code
Hàm max(Max, sum) trả về số lớn hơn trong 2 số Max, sum, rồi gán vào Max. Đây là hàm có sẵn trong C++, nằm trong thư viện giải thuật <algorithm> và namespace std. Trong code mình đã include bits/stdc++.h nên đã bao gồm hết; bạn nào không dùng thư viện này thì muốn dùng hàm max phải include <algorithm> nhé. Dòng Max = max(Max, sum); là cách viết gọn của:
if (sum > Max) { Max = sum; }
// hoặc dùng toán tử 3 ngôi:
Max = Max > sum ? Max : sum;Độ phức tạp
- Không gian: $O(1)$ vì mảng
achỉ có 7 phần tử, là hằng số. Nói tổng quát thì là $O(K)$ với $K$ là số mặt của xúc xắc. - Thời gian: bước đọc dữ liệu lặp $N$ lần với $N$ là tổng 3 số ở dòng đầu. Phần xử lý chính có 4 vòng lặp lồng nhau, mỗi vòng 6 lần, tức $6^4$. Tổng quát là $O(K^{L+1})$ với $K$ là số mặt xúc xắc, $L$ là số viên xúc xắc, $+1$ là do vòng
for lsau cùng để trừ các mặt không xuất hiện. (Dấu^ở đây là lũy thừa chứ không phải phép xor nhé.)
Trường hợp xấu nhất: dòng đầu có 3 số, mỗi số tối đa 6, nên đọc tối đa $6 \times 3 = 18$ dòng. Xử lý chính lặp $6^4 = 1296$ lần. Tổng cộng $18 + 1296 = 1314$ lần lặp. Với giới hạn 1 giây, ngưỡng an toàn khoảng $(3 \text{ đến } 5) \times 10^7$, cao lắm là $10^8$, còn ở đây chỉ hơn $10^3$ nên yên tâm không sợ TLE.
Nhận xét
Đăng nhận xét