Mạch DNA (HSG9 Hà Nội 2025 – Bài 2)
Đề bài
Bài II. Mạch DNA (5,0 điểm)
Cho mạch mã gốc DNA bốn loại nucleotide $A, T, G, C$. Để tiết kiệm bộ nhớ, mạch mã gốc đã được nén lại thành một chuỗi $S$ gồm các cặp là số lần xuất hiện liên tiếp nucleotide và loại nucleotide tương ứng.
Ví dụ: Mạch mã gốc AAACAATGGGGA nén thành 3A1C2A1T4G1A.
Các nucleotide ở hai mạch của phân tử DNA liên kết với nhau theo nguyên tắc bổ sung, trong đó $A$ liên kết với $T$, $G$ liên kết với $C$. Do vậy, nếu biết trình tự nucleotide trên một mạch có thể suy ra trình tự của mạch còn lại.
Ví dụ: Một đoạn phân tử DNA ở sinh vật nhân thực có trình tự nucleotide trên mạch mã gốc là AAACAATGGGGA. Trình tự nucleotide trên mạch bổ sung của đoạn DNA này là: TTTGTTACCCCT.
Yêu cầu: Cho một chuỗi ký tự $S$ mô tả mạch mã gốc DNA sau khi đã nén. Hãy lập trình xác định mạch bổ sung của mạch mã gốc sau khi giải nén.
Dữ liệu vào từ file văn bản MACHDNA.INP: Một chuỗi $S$ có độ dài không vượt quá $1000$. Dữ liệu đảm bảo chuỗi sau khi giải nén có độ dài không vượt quá $10^5$.
Kết quả ghi ra file văn bản MACHDNA.OUT: Chuỗi ký tự là mạch bổ sung của mạch mã gốc sau khi giải nén.
Ràng buộc:
- Có 20% số test ứng với 20% số điểm của bài thỏa mãn: độ dài chuỗi $S$ là $2$, trong đó ký tự đầu tiên là chữ số, ký tự thứ hai là một trong 4 chữ cái $A, T, G, C$;
- Có 20% số test khác ứng với 20% số điểm của bài thỏa mãn: có duy nhất một loại nucleotide;
- Có 40% số test khác ứng với 40% số điểm của bài thỏa mãn: số lần xuất hiện liên tiếp nucleotide $A, T, G, C$ nhỏ hơn $10$;
- 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.
Lưu ý: đề gốc đọc/ghi file MACHDNA.INP / MACHDNA.OUT; trên CLUE OJ thì đọc từ bàn phím, in ra màn hình (giới hạn trên CLUE: 1 giây, 1 GB).
5A2G1A11T1CTTTTTCCTAAAAAAAAAAAGAAAAAGGATTTTTTTTTTTC.Mạch bổ sung là:
TTTTTCCTAAAAAAAAAAAG.Lời mở đầu
Đây là bài 2 trong đề thi học sinh giỏi Tin học lớp 9 thành phố Hà Nội năm 2025. Bài này thuần xử lý xâu, không cần thuật toán gì cao siêu, nhưng rất hợp để các bạn lớp 9 luyện kỹ năng đọc từng ký tự và "ghép" các chữ số thành một số – một thao tác mà sau này các bạn sẽ gặp đi gặp lại. Mình viết lời giải theo đúng từng subtask để bạn nào đi thi cũng biết cách "ăn" điểm từng phần. Hy 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 OJMình giải thích ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Chuỗi nén $S$ = 5A2G1A11T1C gồm các cặp (số lần, loại nucleotide):
| Cặp trong S | Mạch mã gốc | Mạch bổ sung |
|---|---|---|
5A | AAAAA | TTTTT (A ↔ T) |
2G | GG | CC (G ↔ C) |
1A | A | T |
11T | TTTTTTTTTTT | AAAAAAAAAAA (T ↔ A) |
1C | C | G (C ↔ G) |
Ghép lại, mạch bổ sung là TTTTTCCTAAAAAAAAAAAG (dài $5 + 2 + 1 + 11 + 1 = 20$ ký tự). Để ý cặp 11T: số lần có thể có nhiều chữ số, đây chính là chỗ "bẫy" của bài.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Subtask 1Chuỗi S chỉ có 2 ký tự – O(1)
Vì độ dài $S$ là $2$ và ký tự đầu là chữ số, nên ký tự thứ nhất chính là số lần xuất hiện (chỉ có 1 chữ số, từ $0$ đến $9$), còn ký tự thứ hai là loại nucleotide. Do đó ta chỉ cần lấy $s[1] - 48$ (đổi ký tự chữ số sang số, vì mã ASCII của '0' là $48$) rồi in ra chừng đó lần ký tự bổ sung với $s[2]$.
'0', '1', …, '9' có mã ASCII lần lượt là $48, 49, \ldots, 57$. Nên s[i] - 48 (hay s[i] - '0') cho ta đúng con số mà ký tự đó biểu diễn. Ví dụ '7' - 48 = 55 - 48 = 7.Trong code, mình thêm ký tự # vào đầu xâu (s = "#" + s) để các ký tự được đánh số từ $1$ cho dễ nhìn: $s[1]$ là ký tự đầu, $s[2]$ là ký tự thứ hai.
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(){
if(fopen("machdna.inp", "r")){
freopen("machdna.inp", "r", stdin);
freopen("machdna.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
string s; cin >> s;
int n = s.size(); s = "#" + s;
for (int i = 0; i < (s[1] - 48); i++){
if(s[2] == 'A') cout << 'T';
else if(s[2] == 'G') cout << 'C';
else if(s[2] == 'T') cout << 'A';
else cout << 'G';
}
}s = input().strip()
n = len(s)
s = "#" + s
res = []
for i in range(ord(s[1]) - 48):
if s[2] == 'A':
res.append('T')
elif s[2] == 'G':
res.append('C')
elif s[2] == 'T':
res.append('A')
else:
res.append('G')
print("".join(res))Các bạn bấm Tiếp để chạy tay từng dòng. Thử thêm nút Ngoài subtask 1: 12A để thấy vì sao code này chỉ ăn được 20% điểm nha:
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(1)$ (xâu $S$ chỉ có 2 ký tự).
- Thời gian: vòng lặp chạy tối đa $9$ lần nên là $O(1)$.
Subtask 2Chỉ có một loại nucleotide – O(|S| + độ dài kết quả)
Chỉ có một loại nucleotide duy nhất, nghĩa là chuỗi $S$ có dạng một con số rồi tới một chữ cái, ví dụ 123C. (Vì các nucleotide giống nhau liên tiếp đã được gom thành một cặp khi nén, nên không thể có kiểu 3A5A.) Suy ra:
- Ký tự thứ $n$ (với $n$ là độ dài của $S$) – ký tự cuối cùng – là loại nucleotide.
- Các ký tự từ $s[1]$ đến $s[n-1]$ ghép lại là số lần xuất hiện. Lần này số lần có thể có nhiều chữ số.
Để "ghép" các chữ số thành một số, ta đặt $dg = 0$ rồi duyệt $i$ từ $1$ đến $n - 1$. Mỗi lần đọc thêm chữ số $s[i]$, ta coi như viết thêm chữ số đó vào bên phải số $dg$ hiện tại. Thao tác này tương đương với:
Ví dụ với
123: $dg = 0 \to 0 \cdot 10 + 1 = 1 \to 1 \cdot 10 + 2 = 12 \to 12 \cdot 10 + 3 = 123$.Sau đó ta chỉ cần duyệt in ra nucleotide bổ sung với $s[n]$ đúng $dg$ lần.
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(){
if(fopen("machdna.inp", "r")){
freopen("machdna.inp", "r", stdin);
freopen("machdna.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
string s; cin >> s;
int n = s.size(); s = "#" + s;
int dg = 0;
for (int i = 1; i < n; i++) dg = dg * 10 + s[i] - 48;
for (int i = 0; i < dg; i++){
if(s[n] == 'A') cout << 'T';
else if(s[n] == 'G') cout << 'C';
else if(s[n] == 'T') cout << 'A';
else cout << 'G';
}
}s = input().strip()
n = len(s)
s = "#" + s
dg = 0
for i in range(1, n):
dg = dg * 10 + ord(s[i]) - 48
bs = {'A': 'T', 'G': 'C', 'T': 'A', 'C': 'G'} # cặp bổ sung
print(bs[s[n]] * dg)Đánh giá độ phức tạp của cách làm này: ghép số mất $O(|S|)$, in kết quả mất $O(dg)$ với $dg \le 10^5$.
Subtask 3 + 4Duyệt từng ký tự, gặp chữ cái thì in – O(|S| + độ dài kết quả)
Bây giờ là trường hợp tổng quát: $S$ gồm nhiều cặp (số, chữ cái) nối tiếp nhau. Ý tưởng là gộp cả 2 subtask trên lại: ta duyệt các ký tự lần lượt từ $s[1]$ đến $s[n]$, gọi $dg$ là số đang tạo được hiện tại (ban đầu $dg = 0$). Khi đó, nếu:
- Ký tự $s[i]$ là chữ số thì viết thêm nó vào bên phải $dg$: $dg = dg \times 10 + (s[i] - 48)$ (giống subtask 2).
- Ký tự $s[i]$ là một loại nucleotide ($A$, $T$, $G$ hoặc $C$) thì cặp hiện tại đã đọc xong: ta in ra ký tự bổ sung với $s[i]$ đúng $dg$ lần. Sau đó đặt lại $dg = 0$ để tiếp tục "ghép" một con số mới bắt đầu từ ký tự tiếp theo.
dg = 0 thì với 5A2G, khi đọc tới 2 ta sẽ có $dg = 5 \cdot 10 + 2 = 52$ thay vì $2$ – sai ngay! Và nhớ là số lần có thể có nhiều chữ số (như 11T), nên không được chỉ lấy đúng 1 ký tự trước chữ cái như subtask 1.Subtask 3 (số lần nhỏ hơn $10$) và subtask 4 (không ràng buộc gì thêm) đều giải được bằng cùng một code này.
Minh hoạ quá trình giải nén
Các bạn nhập chuỗi nén $S$ rồi bấm Tiếp để xem từng ký tự được xử lý: ô tím là chữ số đang được ghép vào $dg$, gặp chữ cái thì mạch gốc và mạch bổ sung được nối thêm:
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(){
if(fopen("machdna.inp", "r")){
freopen("machdna.inp", "r", stdin);
freopen("machdna.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
string s; cin >> s;
int n = s.size(); s = "#" + s;
int dg = 0;
for (int i = 1; i <= n; i++){
if (s[i] == 'A' || s[i] == 'T' || s[i] == 'G' || s[i] == 'C'){
for(int j = 0; j < dg; j++){
if (s[i] == 'A') cout << 'T';
else if (s[i] == 'C') cout << 'G';
else if (s[i] == 'G') cout << 'C';
else cout << 'A';
}
dg = 0;
}
else dg = dg * 10 + s[i] - 48;
}
}s = input().strip()
n = len(s)
s = "#" + s
bs = {'A': 'T', 'C': 'G', 'G': 'C', 'T': 'A'} # cặp bổ sung
res = []
dg = 0
for i in range(1, n + 1):
if s[i] in "ATGC":
res.append(bs[s[i]] * dg)
dg = 0
else:
dg = dg * 10 + ord(s[i]) - 48
print("".join(res))Giải thích 1 số chỗ trong code ở trên:
- Ta không cần lưu mạch mã gốc sau giải nén, cũng không cần lưu mạch bổ sung: cứ đọc tới chữ cái nào là in luôn ký tự bổ sung tương ứng. Bản Python thì mình gom các đoạn vào một list rồi in một lần (
"".join(...)) cho nhanh, cònbs[c] * dglà lặp lại ký tựbs[c]đúng $dg$ lần. - Số lần lớn nhất là $10^5$ nên biến
intlà thoải mái, không lo tràn số. - Code dùng
cin >> sđể đọc xâu nên tự bỏ qua dấu cách / xuống dòng thừa ở cuối file (nếu có).
Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(|S|)$ để lưu xâu $S$ (tối đa $1000$ ký tự).
- Thời gian: duyệt mỗi ký tự của $S$ một lần, cộng với việc in ra tổng cộng $L \le 10^5$ ký tự (độ dài mạch sau giải nén), nên là $O(|S| + L)$.
- 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