Biểu Thức Bằng K (EXPR)
Đề bài
Bài 3. Biểu thức bằng K (7 điểm)
Cho dãy số nguyên dương $a_1, a_2, \ldots, a_n$, người ta viết các phần tử của dãy số này cách nhau bởi dấu ?:
$a_1 \ ? \ a_2 \ ? \ \ldots \ ? \ a_n$
Hãy thay các dấu ? bởi dấu $+$ hoặc $-$ để được một biểu thức có giá trị bằng $k$ cho trước. Biết rằng luôn tồn tại cách làm như vậy.
Dữ liệu vào từ tệp văn bản EXPR.INP có cấu trúc:
- Dòng 1 chứa số nguyên dương $n$ $(2 \le n \le 100)$ và số nguyên $k$;
- Dòng 2 chứa $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ $(\forall i: a_i \le 100)$;
- Các số trên một dòng được ghi cách nhau ít nhất một dấu cách.
Kết quả ghi vào tệp văn bản EXPR.OUT một dòng gồm $n - 1$ ký tự, ký tự thứ $i \in \{+, -\}$ là dấu điền vào vị trí dấu ? thứ $i$.
Ràng buộc: Có 60% số test ứng với 60% số điểm của bài có $n \le 20$.
(Code trong bài đọc/ghi chuẩn – bàn phím/màn hình; khi đi thi đọc ghi file thì các bạn thêm freopen nhé.)
4 2
1 2 3 4++-Lời mở đầu
Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại thành bài giải chi tiết để các bạn tham khảo nhen. Hi vọng mang đến được giá trị cho các bạn 😇.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJGiải thích ví dụ: $1 + 2 + 3 - 4 = 2 = k$ nên đáp án là ++-. Chú ý là đáp án có thể không duy nhất. Ví dụ với 4 số $8, 3, 10, 7$ và $k = 8$ thì $8 - 3 + 10 - 7 = 8$ (đáp án -+-) mà $8 + 3 - 10 + 7 = 8$ (đáp án +-+) cũng đúng. Nên bài này khi chấm người ta sẽ không so khớp output mà viết trình chấm riêng: lấy các dấu của em thế vào biểu thức xem có ra đúng $k$ không. Em in ra cách nào đúng cũng được.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Sinh nhị phân (quay lui) thử mọi cách điền dấu – O(2ⁿ)
Đây là cách em học viên của mình làm: mỗi dấu ? có 2 lựa chọn $+$ hoặc $-$, giống như một chuỗi nhị phân độ dài $n - 1$ mà thay $0/1$ bằng $+/-$. Sinh hết các chuỗi đó (bằng đệ quy quay lui), mỗi chuỗi tính giá trị biểu thức, gặp chuỗi nào ra đúng $k$ thì in ra và dừng.
Ở code dưới, hàm Try(i, sum) nghĩa là: đã điền xong các dấu trước $a_i$ và tổng hiện tại là sum, giờ chọn dấu cho $a_i$. Khi $i \gt n$ thì kiểm tra sum == k.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int n;
long long k;
int a[105];
string s;
bool found = false;
void Try(int i, long long sum){
if(found) return;
if(i > n){
if(sum == k){
found = true;
cout << s;
}
return;
}
s.push_back('+');
Try(i + 1, sum + a[i]);
s.pop_back();
if(found) return;
s.push_back('-');
Try(i + 1, sum - a[i]);
s.pop_back();
}
int main(){
cin >> n >> k;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
Try(2, a[1]);
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
s = []
def Try(i, total):
if i > n:
return total == k
s.append('+')
if Try(i + 1, total + a[i]):
return True
s[-1] = '-'
if Try(i + 1, total - a[i]):
return True
s.pop()
return False
Try(2, a[1])
print(''.join(s))
main()Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n)$ cho chuỗi dấu và độ sâu đệ quy.
- Thời gian: $O(2^{n-1})$ lá trên cây đệ quy. Với $n \le 20$ là khoảng $5 \cdot 10^5$ – chạy vèo vèo, ăn được 60%. Nhưng $n = 100$ thì $2^{99}$ là con số khổng lồ ⇒ TLE.
- Random $n$ số nguyên dương, rồi random luôn $n - 1$ phép tính $+/-$, thế vào để tính ra giá trị sau cùng – gọi đó là $k$. Như vậy $k$ chắc chắn hợp lệ.
- Đưa $n$ số và $k$ đó vào code của em để nó trả ra $n - 1$ phép tính.
- Không so sánh với dãy dấu đã random (vì có thể có nhiều đáp án), mà thế các dấu code em trả ra vào lại biểu thức, tính xem có đúng bằng $k$ không. Đúng thì OK, cứ để nó random chạy liên tục.
Cách 2Lưu các tổng phân biệt theo từng dòng (set) + truy vết
Nhận thấy mọi dữ liệu đều quá nhỏ: tối đa chỉ có $100$ phần tử, giá trị mỗi phần tử tối đa chỉ là $100$. Vậy em nghĩ xem, giá trị của biểu thức sau cùng nhỏ nhất và lớn nhất có thể là bao nhiêu?
- Nhỏ nhất: phần tử đầu là $1$, toàn bộ 99 số sau là $100$ và đều là dấu trừ: $1 - 100 - 100 - \ldots = 1 - 9900 = -9899$.
- Lớn nhất: đủ 100 số $100$ cộng hết lại $= 10000$.
Làm tròn cứ xem như miền giá trị tổng là $[-10000, 10000]$, tức là chỉ có khoảng $20000$ khả năng thôi. Trong khi cây đệ quy sinh nhị phân có $2^{99}$ lá ⇒ chắc chắn có rất nhiều bài toán con bị trùng nhau: nhánh này cộng/trừ ra được $9$, nhánh khác cũng ra $9$, mà từ $9$ đi tiếp thì 2 nhánh giống hệt nhau, tội gì xét 2 lần.
Mình làm mẫu với test ví dụ $1, 2, 3, 4$ và $k = 2$:
- Dòng 1: $\{1\}$.
- Dòng 2: $1 + 2 = 3$, $1 - 2 = -1$ ⇒ $\{3, -1\}$.
- Dòng 3: $3 + 3 = 6$, $3 - 3 = 0$, $-1 + 3 = 2$, $-1 - 3 = -4$ ⇒ $\{6, 0, 2, -4\}$.
- Dòng 4: $10, 2, 4, -4, 6, -2, 0, -8$.
Truy vết ngược để ra các dấu
Dòng cuối có chứa $k = 2$ (đề đảm bảo chắc chắn có). Trước đó biểu thức có dạng $a_1 \ ? \ a_2 \ ? \ a_3 \ ? \ a_4 = k$. Chuyển vế đổi dấu:
$a_1 \ ? \ a_2 \ ? \ a_3 = k \ \overline{?} \ a_4$
trong đó $\overline{?}$ là dấu ngược với $?$ (trước đó là $+$ thì qua bên kia thành $-$ và ngược lại). Vậy ta thử $k - a_4$ và $k + a_4$, xem cái nào có trong dòng 3:
- $a_4 = 4$: $2 - 4 = -2$ (không có ở dòng 3), $2 + 4 = 6$ (có!) ⇒ đã chuyển vế thành $+$ nghĩa là dấu thật là $-$. Đi tiếp với giá trị $6$.
- $a_3 = 3$: $6 - 3 = 3$ có ở dòng 2 ⇒ dấu thật là $+$. Đi tiếp với $3$.
- $a_2 = 2$: $3 - 2 = 1$ có ở dòng 1 ⇒ dấu thật là $+$. Đến dòng đầu tiên rồi thì dừng.
Các dấu ghi nhận theo thứ tự là $-, +, +$, do ta đang đi từ phải qua trái, nên đảo ngược lại thành ++- – đúng đáp án đề.
Minh hoạ
Em nhập dãy $a$ và $k$ rồi bấm Tiếp: đầu tiên sinh từng dòng các tổng phân biệt, sau đó truy vết ngược từ $k$ lên dòng đầu. Ô vàng là giá trị đang xét, ô xanh là giá trị tìm thấy ở dòng trên, ô đỏ gạch là giá trị thử mà không có.
Để đơn giản, cài đặt bằng cấu trúc dữ liệu set trên mỗi dòng để lưu các số phân biệt. Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
long long k;
cin >> n >> k;
vector<int> a(n + 1);
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
vector<set<int>> check(n + 1);
check[1].insert(a[1]);
for(int i = 1; i < n; ++i){
for(auto it = check[i].begin(); it != check[i].end(); ++it){
check[i + 1].insert(*it + a[i + 1]);
check[i + 1].insert(*it - a[i + 1]);
}
}
string s;
long long x = k;
for(int i = n; i > 1; --i){
long long x1 = x - a[i];
long long x2 = x + a[i];
if(check[i - 1].find(x1) != check[i - 1].end()){
x = x1;
s.push_back('+');
}
else if(check[i - 1].find(x2) != check[i - 1].end()){
x = x2;
s.push_back('-');
}
}
reverse(s.begin(), s.end());
cout << s;
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
check = [set() for _ in range(n + 1)]
check[1].add(a[1])
for i in range(1, n):
nxt = check[i + 1]
for v in check[i]:
nxt.add(v + a[i + 1])
nxt.add(v - a[i + 1])
s = []
x = k
for i in range(n, 1, -1):
if x - a[i] in check[i - 1]:
x -= a[i]
s.append('+')
elif x + a[i] in check[i - 1]:
x += a[i]
s.append('-')
print(''.join(reversed(s)))
main()Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n \cdot S)$ với $S \approx 20000$ là số giá trị tổng có thể có.
- Thời gian: $O(n \cdot S \cdot \log S)$ vì mỗi thao tác
insert/findtrênsetmất $O(\log)$. Vẫn chạy nhanh với giới hạn của đề.
Cách 3Mảng đánh dấu 2 chiều + kỹ thuật tịnh tiến – O(n · S)
Dùng các cấu trúc dữ liệu có sẵn như set thì tiện nhưng sẽ làm time chạy lâu hơn. Tối ưu nhất là dùng mảng đánh dấu: các giá trị tổng chỉ nằm trong miền $[-10000, 10000]$ tức là chỉ khoảng $20000$ trường hợp, nên dùng một mảng đánh dấu 2 chiều có $100$ dòng, mỗi dòng $20001$ cột: check[i][j] = true nghĩa là tổng của $i$ số đầu có thể bằng giá trị ứng với cột $j$.
OFFSET = 10000 vào mọi giá trị. Giá trị $v$ được lưu ở cột $v + 10000$, nên $-10000 \to 0$, $0 \to 10000$, $10000 \to 20000$. Khi truy vết thì bắt đầu từ cột $x = k + 10000$.Các bước y hệt cách 2: dòng 1 đánh dấu cột $a_1 + 10000$; duyệt từng dòng $i$, cột $j$ nào được đánh dấu thì đánh dấu 2 cột $j + a_{i+1}$ và $j - a_{i+1}$ ở dòng $i + 1$. Truy vết: từ cột $x$ ở dòng $i$, thử cột $x - a_i$ ở dòng $i - 1$ trước (dấu $+$), không có thì là cột $x + a_i$ (dấu $-$). Do phép tịnh tiến chỉ cộng một hằng số nên hiệu giữa các cột vẫn giữ nguyên, phần truy vết không phải sửa gì cả.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
const int OFFSET = 10000;
bool check[105][2 * OFFSET + 5];
int a[105];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
long long k;
cin >> n >> k;
for(int i = 1; i <= n; ++i){
cin >> a[i];
}
check[1][a[1] + OFFSET] = true;
for(int i = 1; i < n; ++i){
for(int j = 0; j <= 2 * OFFSET; ++j){
if(check[i][j] == true){
check[i + 1][j + a[i + 1]] = true;
check[i + 1][j - a[i + 1]] = true;
}
}
}
int x = k + OFFSET;
string s;
for(int i = n; i > 1; --i){
int x1 = x - a[i];
int x2 = x + a[i];
if(check[i - 1][x1] == true){
s.push_back('+');
x = x1;
}
else if(check[i - 1][x2] == true){
s.push_back('-');
x = x2;
}
}
reverse(s.begin(), s.end());
cout << s;
return 0;
}import sys
def main():
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
OFFSET = 10000
W = 2 * OFFSET + 1
check = [bytearray(W + 105) for _ in range(n + 1)]
check[1][a[1] + OFFSET] = 1
for i in range(1, n):
cur, nxt, v = check[i], check[i + 1], a[i + 1]
for j in range(W):
if cur[j]:
nxt[j + v] = 1
nxt[j - v] = 1
x = k + OFFSET
s = []
for i in range(n, 1, -1):
if check[i - 1][x - a[i]]:
s.append('+')
x -= a[i]
elif check[i - 1][x + a[i]]:
s.append('-')
x += a[i]
print(''.join(reversed(s)))
main()Trong khung chạy tay bên dưới, vòng for j chạy qua $20001$ cột, đa số là false, nên mình gom các đoạn cột false liên tiếp thành 1 bước cho dễ theo dõi; chỉ các cột true mới đi chi tiết từng dòng.
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(n \cdot S)$ với $S = 20001$: mảng
bool$105 \times 20005$ chỉ khoảng 2 MB. - Thời gian: sinh bảng $O(n \cdot S) = 100 \cdot 20001 \approx 2 \cdot 10^6$ phép, truy vết $O(n)$ ⇒ $O(n \cdot S)$, chạy tức thì.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét