B. Mammoth’s Genome Decoding
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
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.
题意：解密猛犸基因组，有四种核苷酸，A,G,C,T，输入基因序列长度n，输入基因序列，未知的核苷酸用‘？’表示，给的序列中，AGCG给定的个数必定相等，求完整的基因序列。如果序列不合法则输出“===”
题解：因为每种核苷酸数量相等，因此序列长度必为4的倍数，且任意一种核苷酸个数不会超过总数除4的平均值。以此来判断是否合法。计数每种核苷酸已知总数，再算每种核苷酸缺多少个，然后扫一遍序列，遇到问号就输出一个缺少的核苷酸。已知的就直接输出即可。
#include<stdio.h>
int main()
{
int n,i;
char a[288];
while(scanf("%d",&n)!=EOF)
{
scanf("%s",a);
int A=0,G=0,C=0,T=0,sum;
sum=n/4;
for(i=0;i<n;i++)
{
if(a[i]=='T')T++;
if(a[i]=='A')A++;
if(a[i]=='C')C++;
if(a[i]=='G')G++;
}
if(n%4!=0||A>sum||C>sum||G>sum||T>sum)
{
printf("===
");
continue;
}
A=sum-A;T=sum-T;G=sum-G;C=sum-C;
for(i=0;i<n;i++)
{
if(a[i]=='?')
{
if(A)
{
printf("A");
A--;
continue;
}
if(C)
{
printf("C");
C--;
continue;
}
if(G)
{
printf("G");
G--;
continue;
}
if(T)
{
printf("T");
T--;
continue;
}
}
else
printf("%c",a[i]);
}
printf("
");
}
}