시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 172 | 52 | 23 | 16.667% |
단백질은 아미노산의 연결체이다. 단백질은 이중 질량 분석기 (MS2)를 이용해서 단백질의 서열을 알아낼 수 있다.
문제를 풀기 위해 다음과 같은 상황을 가정한다.
MS2의 결과는 실수의 집합이며, 각각의 실수는 피크라고 부른다. 집합은 단백질의 모든 prefix와 suffix의 질량이 포함(전체 단백질의 질량 포함)되어 있으며, 다른 숫자는 포함되어 있지 않다.
알 수 없는 단백질을 MS2로 실험한 결과가 주어진다. 실험은 오차가 발생할 수 있기 때문에, 결과는 아래 조건을 만족한다.
실험 결과가 주어졌을 때, 최대 피크가 단백질의 질량이면서, 노이즈 피크의 수가 최소인 단백질을 만드는 프로그램을 작성하시오.
첫째 줄에 MS2의 실험 결과인 피크의 수 n이 주어진다. (1 ≤ n ≤ 100,000)
다음 n개 줄에는 i번째 피크 pi가 주어진다.
항상 문제의 모든 조건을 만족시키며, 모든 피크는 다르다. 각 피크는 소수점 최대 5째자리까지 주어진다.
길이가 최대 400인 P와 Q로 이루어진 문자열(단백질)을 출력한다. 노이즈 피크의 수를 최소로하는 답이 여러 가지인 경우에는 아무거나 출력한다.
6 225.11134 353.16992 353.16991 291.15828 97.05276 128.05858
PQQ
가능한 단백질은 PQQ와 QQP이다. 두 단백질 모두 291.15828, 353.16991 결과를 제외하면 얻을 수 있다.
ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2012 I번