Excel
Đề bài
Xét một bảng tính (ở định dạng Microsoft Excel hoặc Google Sheet) bao gồm $m$ hàng và $n$ cột. Các hàng được đánh số liên tiếp từ $1$ và các cột được ký hiệu bằng các chữ cái liên tiếp A, B, C, … (dữ liệu đảm bảo bảng tính có không quá $9$ hàng và $26$ cột). Mỗi ô của bảng tính là giao điểm của một hàng và một cột nhất định, đồng thời được ký hiệu bằng chữ cái tượng trưng cho cột đi liền với chữ số tượng trưng cho hàng đó. Ví dụ: ô nằm giao giữa hàng $2$ và cột B sẽ được ký hiệu là B2. Trên mỗi ô ta viết một số nguyên không âm như hình minh hoạ dưới đây:
Nhiệm vụ của bạn là lập trình tính chính xác giá trị của $Q$ biểu thức phân biệt, mỗi biểu thức sẽ có dạng $f(x, y)$, trong đó $f = \text{MAX}$ (tượng trưng cho hàm lấy giá trị lớn nhất) hoặc $f = \text{SUM}$ (tượng trưng cho hàm tính tổng), $x$ sẽ là ký hiệu toạ độ của một ô hoặc một biểu thức hợp lệ khác (tương tự với $y$). Như trên hình minh hoạ, nếu ta tính giá trị biểu thức $\text{MAX}(\text{A1}, \text{B2})$ thì kết quả nhận được là $5$. Xét một biểu thức phức tạp hơn là $\text{SUM}(\text{C4}, \text{MAX}(\text{C2}, \text{C3}))$, ta có thể biến đổi nó về dạng tương đương là $\text{SUM}(2, 6)$ để nhận được kết quả là $8$.
Input:
- Dòng đầu chứa hai số nguyên dương $m$ và $n$ $(1 \le m \le 9$ và $1 \le n \le 26)$.
- Dòng thứ $i$ trong $m$ dòng tiếp theo chứa $n$ số nguyên không âm mô tả giá trị các ô tại hàng thứ $i$ của bảng tính. Dữ liệu đảm bảo các số đều không vượt quá $1000$.
- Dòng tiếp theo chứa số nguyên dương $Q$ $(1 \le Q \le 10)$.
- $Q$ dòng tiếp theo, mỗi dòng chứa một xâu ký tự thể hiện biểu thức cần tính. Dữ liệu đảm bảo các xâu đều không chứa dấu cách và có độ dài không vượt quá $1000$.
Output: gồm $Q$ dòng chứa $Q$ kết quả tìm được theo trình tự trong input.
Scoring:
- Subtask 1 ($80\%$ số điểm): mỗi biểu thức trong $Q$ biểu thức được cho đều có dạng $\text{SUM}(a, b)$ hoặc $\text{MAX}(c, d)$, trong đó $a, b, c, d$ là ký hiệu cho một ô nào đó trong bảng tính.
- Subtask 2 ($20\%$ số điểm): không có ràng buộc gì thêm.
Giới hạn: 2 giây, 512 MB.
4 3
2 1 9
1 5 3
4 3 6
3 2 2
3
SUM(A1,B2)
MAX(A1,B2)
SUM(C4,C1)7
5
114 3
2 1 9
1 5 3
4 3 6
3 2 2
2
SUM(MAX(A1,B2),SUM(C3,C4))
SUM(C4,MAX(C2,C3))13
8Giải thích ví dụ 2: $\text{SUM}(\text{MAX}(\text{A1}, \text{B2}), \text{SUM}(\text{C3}, \text{C4}))$ $= \text{SUM}(\text{MAX}(2, 5), \text{SUM}(6, 2))$ $= \text{SUM}(5, 8)$ $= 13$; còn $\text{SUM}(\text{C4}, \text{MAX}(\text{C2}, \text{C3}))$ $= \text{SUM}(2, 6)$ $= 8$.
Lời mở đầu
Bài này là phiên bản "Excel" của bài toán kinh điển tính giá trị biểu thức có ngoặc. Subtask 1 (80% điểm!) chỉ cần đọc đúng vị trí ký tự là xong, còn subtask 2 với các hàm lồng nhau sâu tới hàng chục tầng ngoặc thì cần một công cụ quen thuộc của chương này: ngăn xếp. Mình sẽ đi từ cách "ăn điểm" nhanh tới cách đầy đủ, kèm kết quả chạy thật trên bộ test của CLUE.
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ì?
| Test | m (hàng) | n (cột) | Q | Độ dài biểu thức | Số hàm trong 1 biểu thức | Độ sâu ngoặc | Kết quả lớn nhất |
|---|---|---|---|---|---|---|---|
| 1 – 80 | 1 … 9 | 1 … 26 | 10 | 10 | 1 | 1 | 1902 |
| 81 – 100 | 1 … 8 | 5 … 26 | 10 | 994 | 124 | 81 | 38790 |
- Bộ test có 100 test, mỗi test đều có $Q = 10$ biểu thức.
- Test 1–80 đúng là subtask 1: biểu thức nào cũng dài đúng 10 ký tự, ví dụ
SUM(D6,A3). Có cả trường hợp hai ô trùng nhau nhưMAX(I2,I2), và bảng chỉ có 1 hàng hoặc 1 cột. - Test 81–100 là subtask 2 và là các test "khó" thật sự: mọi biểu thức đều dài 994 ký tự, chứa tới 124 hàm, lồng sâu tới 81 tầng ngoặc. Kết quả lớn nhất khoảng 38.790 – vẫn vừa kiểu
int, nhưng mình dùnglong longcho chắc.
Các subtask khớp với bộ test như sau (ô ghi số test đúng của từng cách – chạy thật):
| Subtask | Điều kiện | Các test | Cách 1 đọc vị trí cố định | Cách 2 ngăn xếp |
|---|---|---|---|---|
| 1 (80%) | chỉ có dạng $\text{SUM}(a, b)$ / $\text{MAX}(c, d)$ với $a, b, c, d$ là ô | 1 – 80 | 80/80 | 80/80 |
| 2 (20%) | biểu thức lồng nhau tuỳ ý | 81 – 100 | 0/20 | 20/20 |
Cách 1Subtask 1: đọc ký tự ở vị trí cố định
Ở subtask 1, biểu thức luôn có dạng SUM(A1,B2) hoặc MAX(A1,B2): tên hàm 3 chữ, rồi (, ô thứ nhất, ,, ô thứ hai, ). Vì cột chỉ là một chữ cái (tối đa 26 cột) và hàng chỉ là một chữ số (tối đa 9 hàng) nên mỗi ô đúng 2 ký tự. Đánh số ký tự từ 0:
| Vị trí | 0 1 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|
| Ký tự | S U M | ( | A | 1 | , | B | 2 | ) |
Vậy chỉ cần nhìn s[0] để biết là SUM hay MAX, lấy ô thứ nhất từ s[4], s[5] và ô thứ hai từ s[7], s[8]. Đổi ký hiệu ô ra chỉ số: cột = c - 'A' + 1 (A → 1, B → 2, …), hàng = r - '0'.
Kết quả chạy thật: bản C++ đúng 80/100 test (sai ở các test 81–100), test chạy lâu nhất 0.004s; bản Python đúng 80/100 test, lâu nhất 0.022s. Ở các test lồng nhau, các vị trí 4, 5, 7, 8 không còn là ký hiệu ô nữa (ví dụ MAX(H2,SUM(… có s[7] = 'S', s[8] = 'U') nên chương trình đọc ra ngoài mảng và bị lỗi. Dù vậy 80% số điểm đã nằm trong tay – trong phòng thi, đây là cách nên viết đầu tiên!
Ý tưởngHai ngăn xếp: tên hàm và giá trị
Khi biểu thức lồng nhau, ta không biết trước đối số nằm ở đâu. Nhưng có một nhận xét quan trọng: mỗi dấu ) kết thúc đúng hàm được mở gần nhất, và lúc đó hai đối số của hàm ấy chính là hai giá trị được tính xong gần nhất. "Gần nhất" = "vào sau, ra trước" → dùng ngăn xếp.
- Gặp
SUM(hoặcMAX(: đẩy tên hàm vào ngăn xếpop. - Gặp một ô như
B2: đẩy giá trị của ô vào ngăn xếpval. - Gặp dấu phẩy: bỏ qua.
- Gặp
): lấy 2 giá trị trên đỉnhval($y$ rồi $x$), lấy 1 hàm trên đỉnhop, tính $f(x, y)$ rồi đẩy kết quả lại vàoval– kết quả này sẽ là đối số của hàm bên ngoài.
val chỉ còn đúng một số: đó là đáp án.Một chi tiết nhỏ: cột S và cột M cũng là chữ cái, nên không thể chỉ nhìn s[i] == 'S' để đoán là hàm SUM (ô S3 chẳng hạn). Ta xét thêm ký tự kế tiếp: hàm thì sau S là U, sau M là A; còn ô thì sau chữ cái luôn là một chữ số.
Em nhập biểu thức (bảng tính là bảng 4 × 3 của ví dụ) rồi bấm Tiếp để xem hai ngăn xếp thay đổi:
Cách 2Cài đặt bằng ngăn xếp – O(độ dài xâu)
- Gặp
SUM(thìi += 3, cộng thêmi++của vòngforlà nhảy qua đúng 4 ký tựS, U, M, (. Tương tự với ô:i++trong thân, cộngi++của vòngforlà nhảy qua 2 ký tự. - Khi gặp
), giá trị lấy ra đầu tiên là đối số thứ hai $y$ (vào sau ra trước). Với SUM và MAX thứ tự không quan trọng, nhưng nếu đề có thêm phép trừ hay chia thì phải nhớ điều này. - Dấu phẩy không khớp nhánh nào nên tự động bị bỏ qua.
- Hai ngăn xếp khai báo bên trong vòng
whilenên mỗi biểu thức bắt đầu với ngăn xếp rỗng.
Cũng có thể giải bằng đệ quy: hàm eval() đọc tên hàm, gọi eval() cho đối số thứ nhất, bỏ dấu phẩy, gọi eval() cho đối số thứ hai. Thực chất đệ quy dùng ngăn xếp lời gọi của máy thay cho ngăn xếp ta tự quản lý – với độ sâu tối đa khoảng 500 tầng (xâu dài 1000) thì cả hai cách đều an toàn.
Kết quả chạy thật: bản C++ đúng 100/100 test, test chạy lâu nhất 0.004s; bản Python đúng 100/100 test, lâu nhất 0.023s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Đọc vị trí cố định | C++ | 80/100 | 0.004s | Sai (lỗi chạy) ở test 81–100 – biểu thức lồng nhau |
| Python | 80/100 | 0.022s | Sai (lỗi chạy) ở test 81–100 – biểu thức lồng nhau | |
| 2. Hai ngăn xếp | C++ | 100/100 | 0.004s | Full điểm |
| Python | 100/100 | 0.023s | Full điểm |
Nhận xét
Đăng nhận xét