ATGX - ADN
Xem PDFCon người có 4 loại ADN: \(A,X,T,G\). Giả sử đoạn gen quy định màu da của con người là một chuỗi \(N\) ADN kết hợp từ 4 loại ADN trên (\(1 \le N \le 20\)). Ví dụ một đoạn gen có \(8\) ADN là: \(AATXGGGT\). Các ADN trong đoạn gen được đánh số từ \(1\) đến \(N\).
Đoạn gen quy định màu da của thế hệ con cũng là một đoạn \(N\) ADN kết hợp từ gen của bố và gen của mẹ. Trong đó ADN thứ \(i\) (\(1 \le i \le N\)) được hình thành bằng cách lấy ADN thứ \(i\) tương ứng của gen bố hoặc gen mẹ.
Ví dụ:
Gen của bố: \(AATX\).
Gen của mẹ: \(GATT\).
Gen của con chỉ có thể là 4 trường hợp sau: \(AATX,AATT,GATX,GATT\).
Cho trước gen của bố và gen của mẹ, bạn hãy viết chương trình liệt kê các khả năng có thể xảy ra của gen thế hệ con.
Input
-
Dòng thứ nhất: là số \(N\) biểu thị số ADN trong đoạn gen của bố và mẹ. (\(1 \le N \le 20\)).
-
Dòng thứ hai: đoạn gen của bố.
-
Dòng thứ ba: đoạn gen của mẹ. (hai đoạn gen này có chiều dài bằng \(N\) và chỉ gồm các ký tự \(A,X,T,G\)).
Output
- Ghi số \(K\) là tổng số khả năng có thể xảy ra của đoạn gen thế hệ con.
Example
Test 1
Input
2
AT
GXOutput
4Note
Sample input 1: Gen bố là \(AT\), gen mẹ là \(GX\), vậy khả năng gen của con là: \(AT,AX,TG,TX\).
Test 2
Input
3
AXT
GXAOutput
4
Bình luận
Gợi ý cho C++
Vì n <= 20 nên dùng quay lui để sinh ra các xâu, rồi lưu vào map để lấy các xâu riêng biệt. Kết quả chính là kích thước của map.
Code
thư viện bits/stdc++.h
int là long long
endl là "\n"
using namespace std;
int n,x[21]={}; map<string,int> mp;
string s1,s2,s;
void farm()
{
int i; s="";
for(i=0;i<n;i++)
{
if (x[i]==1) s+=s1[i];
else s+=s2[i];
}
mp[s]++;
}
void in(int i)
{
int j;
for(j=1;j<=2;j++)
{
x[i]=j;
if (i<n-1) in(i+1);
else farm();
}
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>s1>>s2;
in(0);
cout<<mp.size();
}
2 bình luận nữa