Summer Contest 2021 SC1
Đề bài
Kỳ nghỉ Tết cũng đã kết thúc, Quang đã kiếm chác được một số tiền khá lớn dựa vào tiền lì xì, tiền đánh bài, lô tô, tổ tôm, bầu cua, cá ngựa. Số tiền của Quang tích góp sau Tết sau khi thống kê lại, được $a_1$ tờ 1.000 đồng, $a_2$ tờ 2.000 đồng, $a_3$ tờ 5.000 đồng, $a_4$ tờ 10.000 đồng, $a_5$ tờ 20.000 đồng, $a_6$ tờ 50.000 đồng, $a_7$ tờ 100.000 đồng, $a_8$ tờ 200.000 đồng, $a_9$ tờ 500.000 đồng. Quang quyết định bỏ tiền của mình vào ống heo để tiết kiệm. Tuy nhiên, Quang sẽ muốn ăn mừng 1 bữa thắng lớn. Thế là Quang chạy ra tiệm trà sữa Giun Giun, Quang gọi 1 ly trà sữa Thái trân châu đường đen full topping, ca cao, phô mai, kem cheese, bánh flan, bánh quế, 100% đường 20% đá size XXL. Quả nhiên là 1 ly trà sữa hảo hạng.
Số tiền để mua ly trà sữa này là $C$ (đồng) và $C$ chia hết cho 1000. Tiệm trà sữa Giun Giun hiện tại đang có $b_1$ tờ 1.000 đồng, $b_2$ tờ 2.000 đồng, $b_3$ tờ 5.000 đồng, $b_4$ tờ 10.000 đồng, $b_5$ tờ 20.000 đồng, $b_6$ tờ 50.000 đồng, $b_7$ tờ 100.000 đồng, $b_8$ tờ 200.000 đồng, $b_9$ tờ 500.000 đồng trong quầy tính tiền. Vì chú heo đất của Quang không to lắm, nên Quang muốn tống khứ càng nhiều tờ tiền của mình càng tốt. Quang có thể trả tiền cho ly trà sữa với một số tiền là $X$ $(X > C)$ và quán Giun Giun phải thối lại cho Quang 1 số tiền là $X - C$ đồng. Vì là 1 tiệm kinh doanh trà sữa, nên bà chủ Giun Giun muốn tống khứ càng ít tiền của quán càng tốt (quán cần nhiều tiền lẻ để còn tiền thối cho các khách sau). Hãy giúp Quang tính xem số tờ tiền tối thiểu mà Quang sẽ có nếu thực hiện xong thương vụ mua trà sữa.
Dữ liệu đầu vào:
- Dòng đầu tiên gồm một số nguyên dương $T$ $(1 \le T \le 40)$ là số lượng bộ dữ liệu của đề bài.
- $T$ bộ dữ liệu tiếp theo, mỗi bộ dữ liệu được tổ chức như sau:
- Dòng thứ nhất gồm một số nguyên dương $C$ là giá tiền của ly trà sữa mà Quang mua ($C$ chia hết cho 1000).
- 9 dòng tiếp theo, dòng thứ $i$ được tổ chức theo định dạng
c[i]: a[i] b[i]. Trong đó, $c[i]$ là mệnh giá tiền Việt Nam, $c = \{1.000, 2.000, 5.000, 10.000, 20.000, 50.000, 100.000, 200.000, 500.000\}$. Còn $a[i]$ và $b[i]$ tương ứng là số tờ tiền mệnh giá $c[i]$ mà Quang và tiệm trà sữa Giun Giun đang sở hữu.
Dữ liệu đầu ra: gồm $T$ dòng, mỗi dòng gồm một số nguyên dương duy nhất là số tờ tiền mà Quang sở hữu được sau khi giao dịch trà sữa. Nếu không thể mua trà sữa được, hãy in ra 1 chuỗi SORRY!!!.
Bài toán được chia thành 2 Dataset:
- Small Dataset: $0 \le a[i], b[i] \le 1$.
- Large Dataset: $0 \le a[i], b[i] \le 70$.
- Trong mọi test, số tiền trà sữa không vượt quá $70.000.000$.
Đề gốc cho 5 giây, 512 MB mỗi dataset; trên CLUE OJ bài đặt giới hạn 1 giây, 512 MB cho mỗi file test.
5
52000
1.000: 0 1
2.000: 0 1
5.000: 5 0
10.000: 2 0
20.000: 1 5
50.000: 1 0
100.000: 5 12
200.000: 0 15
500.000: 2 20
50000
1.000: 0 0
2.000: 3 0
5.000: 9 0
10.000: 0 0
20.000: 0 0
50.000: 0 0
100.000: 0 0
200.000: 0 0
500.000: 0 0
200000
1.000: 0 0
2.000: 0 0
5.000: 0 0
10.000: 0 0
20.000: 0 0
50.000: 0 0
100.000: 2 0
200.000: 5 0
500.000: 5 0
600000
1.000: 1 51
2.000: 1 24
5.000: 1 42
10.000: 1 52
20.000: 1 11
50.000: 1 4
100.000: 1 0
200.000: 1 5
500.000: 1 24
58000
1.000: 3 2
2.000: 1 5
5.000: 0 5
10.000: 2 12
20.000: 5 12
50.000: 9 24
100.000: 1 15
200.000: 4 5
500.000: 9 127
SORRY!!!
10
7
16Giải thích ví dụ (trích đề):
- Ví dụ 1: ly trà sữa có giá 52.000 đồng, nhưng Quang sẽ đưa cho bà chủ quán tận 555.000 đồng: 5 tờ 100.000, 1 tờ 20.000, 1 tờ 10.000 và 5 tờ 5.000. Chủ quán sẽ thối lại Quang $555.000 - 52.000$ $= 503.000$, gồm 1 tờ 500.000, 1 tờ 2.000 và 1 tờ 1.000. Tổng số tờ tiền mà Quang có sau khi mua trà sữa là 7.
- Ví dụ 2: Quang có 9 tờ 5.000 và 3 tờ 2.000, tổng tiền Quang có là 51.000 và quán phải thối lại Quang 1.000. Tuy nhiên quán không còn 1 tờ tiền nào cả nên giao dịch này không thể thực hiện được.
- Ví dụ 3: ly trà sữa có giá 200.000 và Quang trả 2 tờ 100.000. Quang còn lại 10 tờ.
- Những ví dụ còn lại chỉ dành để các bạn kiểm tra xem thuật toán của mình đã đúng hay chưa.
- Đề ghi $X > C$ nhưng ví dụ 3 Quang trả vừa đúng $X = C = 200.000$ → thực ra được phép $X \ge C$ (không cần thối).
- Trong file test thật các dòng mệnh giá không có dấu hai chấm (
1.000 0 1), còn đề thì có. Đọc mệnh giá bằngcin >> s(kiểustring) rồi bỏ đi là an toàn cho cả hai. - Mọi số tiền đều chia hết cho 1000 nên mình đổi hết ra đơn vị nghìn đồng: mệnh giá còn $1, 2, 5, \dots, 500$.
Lời mở đầu
Thoạt nhìn có 2 người với 2 mong muốn khác nhau, nhưng thật ra chúng cùng chiều: Quang còn lại $A - p + q$ tờ, với $A$ là số tờ ban đầu, $p$ là số tờ Quang đưa, $q$ là số tờ quán thối. Quang muốn $p$ lớn, quán muốn $q$ nhỏ – cả hai đều làm $A - p + q$ nhỏ đi. Vậy bài toán là: chọn số tiền $X \ge C$ sao cho (nhiều tờ nhất để Quang ghép đúng $X$) trừ (ít tờ nhất để quán ghép đúng $X - C$) là lớn nhất. Mỗi vế là một bài cái túi có giới hạn số lượng.
Có một câu hỏi tinh tế: quán có được thối lại chính tờ tiền Quang vừa đưa không? Không cần quan tâm – nếu quán trả lại tờ Quang vừa đưa thì chẳng khác gì Quang không đưa tờ đó ngay từ đầu, kết quả như nhau. Nên chỉ cần xét tiền thối lấy từ $b_i$.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bài này chỉ có 2 file test, mỗi file chứa nhiều bộ dữ liệu (đúng kiểu "dataset" của đề gốc). Mình mở từng file ra thống kê theo từng bộ:
| Phần | Số bộ $T$ | $a_i, b_i$ lớn nhất | Giá $C$ (đồng) | Tiền Quang lớn nhất | Số bộ SORRY!!! |
|---|---|---|---|---|---|
| Test 1 (cả file) | 20 | 1 | 10.000–580.000 | 863.000 | 9 |
| Test 2 – 20 bộ đầu | 20 | 1 | 10.000–580.000 | 863.000 | 9 |
| Test 2 – 20 bộ sau | 20 | 70 | 1.120.000–33.160.000 | 49.933.000 | 7 |
- Test 1 chính là Small dataset ($a_i, b_i \le 1$).
- Test 2 gồm lại nguyên 20 bộ của test 1 rồi thêm 20 bộ Large ($a_i, b_i \le 70$). Vì cả file chấm chung một lần nên muốn ăn test 2 thì phải giải được Large.
- Trong file test các dòng mệnh giá viết
1.000 0 1(không có dấu hai chấm), còn ví dụ trong đề viết1.000: 0 1. Code đọc mệnh giá vào mộtstringrồi bỏ qua thì cả hai kiểu đều đúng. - Tổng tiền của Quang tối đa $70 \cdot (1 + 2 + 5 + \dots + 500)$ $= 70 \cdot 888$ $= 62\,160$ nghìn đồng; thực tế trong test lớn nhất khoảng $49\,933$ nghìn.
| File | Nội dung | Cách 1 vét cạn | Cách 2 cái túi từng tờ | Cách 3 chia nhị phân |
|---|---|---|---|---|
| Test 1 | Small | qua | qua | qua |
| Test 2 | Small + Large | quá thời gian | qua (0,15 s) | qua (0,03 s) |
Ý tưởngHai mảng cái túi P và Q
P[x]= số tờ nhiều nhất Quang dùng để ghép đúng $x$ ($-\infty$ nếu không ghép được), $0 \le x \le S_A$ = tổng tiền của Quang.Q[y]= số tờ ít nhất quán dùng để ghép đúng $y$ ($+\infty$ nếu không ghép được), $0 \le y \le S_A - c$.- Đáp án: $A - \max_{c \le x \le S_A} \big(P[x] - Q[x - c]\big)$ trên các $x$ mà cả hai ghép được; không có $x$ nào thì in
SORRY!!!.
Em nhập giá $c$ (nghìn đồng) và số tờ của từng mệnh giá (9 số theo thứ tự 1, 2, 5, 10, 20, 50, 100, 200, 500 nghìn), bấm Tiếp để xem lần lượt: điền P, điền Q, rồi dò từng $x$:
Cách 1Vét cạn số tờ mỗi mệnh giá (Small dataset)
Hàm tra(i, x, p) thử Quang đưa $k = 0..a_i$ tờ mệnh giá thứ $i$; đi hết 9 mệnh giá thì có số tiền $X$ và số tờ $p$. Với mỗi $X \ge c$, hàm thoi(i, y) lại vét cạn số tờ quán đưa để ghép đúng $y = X - c$ với ít tờ nhất.
Kết quả chạy thật: đúng 1/2 file test. Test 1 (Small: mỗi bên mỗi mệnh giá tối đa 1 tờ, $2^9 \cdot 2^9$ trường hợp) chạy 0,00 giây; test 2 có các bộ Large với tới $71^9$ cách đưa tiền → quá thời gian.
Cách 2Cái túi 0/1 – mỗi tờ tiền là một đồ vật
Coi mỗi tờ tiền là một đồ vật riêng (mệnh giá $d_i$ có $a_i$ đồ vật giống nhau) rồi làm 2 bài cái túi 0/1 với mảng 1 chiều, duyệt giảm dần như bài Knapsack 1.
Kết quả chạy thật: đúng 2/2 file test, chậm nhất 0,15 giây – qua được vì tiền của Quang trong test thật chưa chạm trần. Nhưng mình tự sinh một file xấu nhất (40 bộ, mọi $a_i = b_i = 70$) thì cách này chạy 1,53 giây – vượt 1 giây. Có tới $9 \cdot 70 = 630$ tờ mỗi bên, mỗi tờ quét cả mảng $62\,160$ ô.
Cách 3Chia nhị phân số lượng (an toàn cả trường hợp xấu nhất)
Thay vì $a_i$ đồ vật giống nhau, ta gom chúng thành các gói $1, 2, 4, 8, \dots$ tờ và một gói phần dư. Ví dụ $a_i = 70 = 1 + 2 + 4 + 8 + 16 + 32 + 7$: chỉ còn 7 gói, mà mọi số tờ từ 0 đến 70 vẫn ghép được bằng cách chọn một số gói. Gói $t$ tờ mệnh giá $d$ là một đồ vật có khối lượng $t \cdot d$ và giá trị $t$ tờ.
- Hàm
splitsinh các gói: mỗi mệnh giá còn tối đa $\lceil \log_2 71 \rceil = 7$ gói thay vì 70 tờ → số đồ vật giảm 10 lần. Pdùngmaxvới khởi tạo $-\infty$;Qdùngminvới khởi tạo $+\infty$; cả hai có ô 0 bằng 0 – đặc trưng của cái túi "đúng bằng". Ô không ghép được có thể thành $-\infty + 1$, $-\infty + 2$... (vẫn rất âm), nên khi dò mình kiểm traP[x] >= 0chứ không so sánh bằng-INF.- Kiểm tra
c > SAtrước: Quang không đủ tiền thì inSORRY!!!luôn (và tránh tạo mảng kích thước âm).
Kết quả chạy thật: bản C++ đúng 2/2 file test, chậm nhất 0,03 giây; với file xấu nhất tự sinh chỉ mất 0,15 giây (nhanh gấp 10 lần cách 2). Bản Python (mình viết thêm, dùng list comprehension) cho kết quả đúng ở cả 2 file nhưng file 2 mất khoảng 3,31 giây nên chỉ được 1/2 với giới hạn 1 giây (với giới hạn gốc 5 giây thì qua).