基因组解码
The process of mammoth’s genome decoding in Berland comes to its end!
One of the few remaining tasks is to restore unrecognized nucleotides in a found chain s. Each nucleotide is coded with a capital letter of English alphabet: ‘A’, ‘C’, ‘G’ or ‘T’. Unrecognized nucleotides are coded by a question mark ‘?’. Thus, s is a string consisting of letters ‘A’, ‘C’, ‘G’, ‘T’ and characters ‘?’.
It is known that the number of nucleotides of each of the four types in the decoded genome of mammoth in Berland should be equal.
Your task is to decode the genome and replace each unrecognized nucleotide with one of the four types so that the number of nucleotides of each of the four types becomes equal.
Input
The first line contains the integer n (4 ≤ n ≤ 255) — the length of the genome.
The second line contains the string s of length n — the coded genome. It consists of characters ‘A’, ‘C’, ‘G’, ‘T’ and ‘?’.
Output
If it is possible to decode the genome, print it. If there are multiple answer, print any of them. If it is not possible, print three equals signs in a row: “===” (without quotes).
Examples
Input
8
AG?C??CT
Output
AGACGTCT
Input
4
AGCT
Output
AGCT
Input
6
???G?
Output
Input
4
AA??
Output
Note
In the first example you can replace the first question mark with the letter ‘A’, the second question mark with the letter ‘G’, the third question mark with the letter ‘T’, then each nucleotide in the genome would be presented twice.
In the second example the genome is already decoded correctly and each nucleotide is exactly once in it.
In the third and the fourth examples it is impossible to decode the genom.
法1：
比较麻烦
思路：先找出A C G T中最大的个数，把其他不够的都补上，如果？不够，也就是说没补完就到最后一个字符了，就输出===，全都补上之后，如果剩下？的个数%4==0，则把A C G T再分别补上剩下？的个数/4个
#include<bits/stdc++.h>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
int n;
cin>>n;
char a[1000];
int n1,n2,n3,n4;
n1=0,n2=0,n3=0,n4=0;
cin>>a;
if(n%4==0)
{
int len=strlen(a);
for(int i=0; i<len; i++)
{
if(a[i]=='A')
n1++;
else if(a[i]=='C')
n2++;
else if(a[i]=='G')
n3++;
else if(a[i]=='T')
n4++;
}
int maxn=max(n1,n2);
maxn=max(maxn,n3);
maxn=max(maxn,n4);
int i=0;
int flag=1;//标记？是否够补上目前最多个数
while(n1<maxn)
{
if(i<len)
{
if(a[i]=='?')
{
a[i]='A';
n1++;
}
i++;
}
else
{
flag=0;
break;
}
}
while(n2<maxn)
{
if(i<len)
{
if(a[i]=='?')
{
a[i]='C';
n2++;
}
i++;
}
else
{
flag=0;
break;
}
}
while(n3<maxn)
{
if(i<len)
{
if(a[i]=='?')
{
a[i]='G';
n3++;
}
i++;
}
else
{
flag=0;
break;
}
}
while(n4<maxn)
{
if(i<len)
{
if(a[i]=='?')
{
a[i]='T';
n4++;
}
i++;
}
else
{
flag=0;
break;
}
}
if(flag==1)
{
int n5=0;//保存剩下的？个数
for(int j=0; j<len; j++)
{
if(a[j]=='?')
n5++;
}
if(n5%4==0)
{
maxn=n5/4;
int p=0;
while(p<maxn)
{
if(a[i]=='?')
{
a[i]='A';
p++;
}
i++;
}
p=0;
while(p<maxn)
{
if(a[i]=='?')
{
a[i]='C';
p++;
}
i++;
}
p=0;
while(p<maxn)
{
if(a[i]=='?')
{
a[i]='G';
p++;
}
i++;
}
p=0;
while(p<maxn)
{
if(a[i]=='?')
{
a[i]='T';
p++;
}
i++;
}
cout<<a<<endl;
}
else
cout<<"==="<<endl;
}
else
cout<<"==="<<endl;
}
else
cout<<"==="<<endl;
return 0;
}
法二：
先找出n/4，然后补上不足的
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
char str[300];
cin>>str;
int sum1=0,sum2=0,sum3=0,sum4=0;
if(n%4!=0)
cout<<"==="<<endl;
else
{
int sum = n/4;
for(int i = 0; i<n; i++)
{
if(str[i]=='A')
sum1++;
else if(str[i]=='C')
sum2++;
else if(str[i]=='G')
sum3++;
else if(str[i]=='T')
sum4++;
}
if(sum1>sum||sum2>sum||sum3>sum||sum4>sum)
cout<<"==="<<endl;
else
{
for(int i = 0; i<n; i++)
{
if(str[i]=='?')
{
if(sum1<sum)
{
str[i]='A';
sum1++;
}
else if(sum2<sum)
{
str[i]='C';
sum2++;
}
else if(sum3<sum)
{
str[i]='G';
sum3++;
}
else if(sum4<sum)
{
str[i]='T';
sum4++;
}
}
}
if(sum1==sum&&sum2==sum&&sum3==sum&&sum4==sum)
cout<<str<<endl;
else
cout<<"==="<<endl;
}
}
return 0;
}