시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 49 12 7 16.279%

문제

단백질은 아미노산의 연결체이다. 단백질은 이중 질량 분석기 (MS2)를 이용해서 단백질의 서열을 알아낼 수 있다.

문제를 풀기 위해 다음과 같은 상황을 가정한다.

  • 단백질은 최대 400개 아미노산이 연결된 형태이다.
  • 아미노산은 두 종류 P와 Q만 있다.
  • P의 질량은 97.05276돌턴, Q의 질량은 128.05858돌턴이다.

MS2의 결과는 실수의 집합이며, 각각의 실수는 피크라고 부른다. 집합은 단백질의 모든 prefix와 suffix의 질량이 포함(전체 단백질의 질량 포함)되어 있으며, 다른 숫자는 포함되어 있지 않다.

알 수 없는 단백질을 MS2로 실험한 결과가 주어진다. 실험은 오차가 발생할 수 있기 때문에, 결과는 아래 조건을 만족한다.

  • 일부 prefix와 suffix의 결과는 집합에 포함되어 있지 않다.
  • 단백질의 prefix/suffix 질량에 해당하지 않는 피크가 집합에 포함되어 있을 수도 있다. 이러한 피크를 노이즈 피크라고 한다.
  • 모든 피크는 양수이다.
  • 가장 큰 피크는 단백질 전체 질량이다.
  • prefix/suffix 질량에 해당하는 피크는 정확한 값이다.

실험 결과가 주어졌을 때, 최대 피크가 단백질의 질량이면서, 노이즈 피크의 수가 최소인 단백질을 만드는 프로그램을 작성하시오.

입력

첫째 줄에 MS2의 실험 결과인 피크의 수 n이 주어진다. (1 ≤ n ≤ 100,000)

다음 n개 줄에는 i번째 피크 pi가 주어진다.

항상 문제의 모든 조건을 만족시키며, 모든 피크는 다르다. 각 피크는 소수점 최대 5째자리까지 주어진다.

출력

길이가 최대 400인 P와 Q로 이루어진 문자열(단백질)을 출력한다. 노이즈 피크의 수를 최소로하는 답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1

6
225.11134
353.16992
353.16991
291.15828
97.05276
128.05858

예제 출력 1

PQQ

힌트

가능한 단백질은 PQQ와 QQP이다. 두 단백질 모두 291.15828, 353.16991 결과를 제외하면 얻을 수 있다. 

W3sicHJvYmxlbV9pZCI6IjM5OTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWJjMzFcdWM5YzggXHVjMmRkXHViY2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZThcdWJjMzFcdWM5YzhcdWM3NDAgXHVjNTQ0XHViYmY4XHViMTc4XHVjMGIwXHVjNzU4IFx1YzVmMFx1YWNiMFx1Y2NiNFx1Yzc3NFx1YjJlNC4gXHViMmU4XHViYzMxXHVjOWM4XHVjNzQwIFx1Yzc3NFx1YzkxMSBcdWM5YzhcdWI3YzkgXHViZDg0XHVjMTFkXHVhZTMwIChNUzxzdXA+MjxcL3N1cD4pXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWIyZThcdWJjMzFcdWM5YzhcdWM3NTggXHVjMTFjXHVjNWY0XHVjNzQ0IFx1YzU0Y1x1YzU0NFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDgwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzBjMVx1ZDY2OVx1Yzc0NCBcdWFjMDBcdWM4MTVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViMmU4XHViYzMxXHVjOWM4XHVjNzQwIFx1Y2Q1Y1x1YjMwMCA0MDBcdWFjMWMgXHVjNTQ0XHViYmY4XHViMTc4XHVjMGIwXHVjNzc0IFx1YzVmMFx1YWNiMFx1YjQxYyBcdWQ2MTVcdWQwZGNcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzU0NFx1YmJmOFx1YjE3OFx1YzBiMFx1Yzc0MCBcdWI0NTAgXHVjODg1XHViOTU4IFBcdWM2NDAgUVx1YjljYyBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlBcdWM3NTggXHVjOWM4XHViN2M5XHVjNzQwIDk3LjA1Mjc2XHViM2NjXHVkMTM0LCBRXHVjNzU4IFx1YzljOFx1YjdjOVx1Yzc0MCAxMjguMDU4NThcdWIzY2NcdWQxMzRcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+TVM8c3VwPjI8XC9zdXA+XHVjNzU4IFx1YWNiMFx1YWNmY1x1YjI5NCBcdWMyZTRcdWMyMThcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzc0XHViYTcwLCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMmU0XHVjMjE4XHViMjk0IFx1ZDUzY1x1ZDA2Y1x1Yjc3Y1x1YWNlMCBcdWJkODBcdWI5NzhcdWIyZTQuIFx1YzlkMVx1ZDU2OVx1Yzc0MCBcdWIyZThcdWJjMzFcdWM5YzhcdWM3NTggXHViYWE4XHViNGUwIHByZWZpeFx1YzY0MCBzdWZmaXhcdWM3NTggXHVjOWM4XHViN2M5XHVjNzc0IFx1ZDNlY1x1ZDU2OChcdWM4MDRcdWNjYjQgXHViMmU4XHViYzMxXHVjOWM4XHVjNzU4IFx1YzljOFx1YjdjOSBcdWQzZWNcdWQ1NjgpXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViMmU0XHViOTc4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTRjIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHViMmU4XHViYzMxXHVjOWM4XHVjNzQ0IE1TPHN1cD4yPFwvc3VwPlx1Yjg1YyBcdWMyZTRcdWQ1ZDhcdWQ1NWMgXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMmU0XHVkNWQ4XHVjNzQwIFx1YzYyNFx1Y2MyOFx1YWMwMCBcdWJjMWNcdWMwZGRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YWNiMFx1YWNmY1x1YjI5NCBcdWM1NDRcdWI3OTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWM3N2NcdWJkODAgcHJlZml4XHVjNjQwIHN1ZmZpeFx1Yzc1OCBcdWFjYjBcdWFjZmNcdWIyOTQgXHVjOWQxXHVkNTY5XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWM5YzAgXHVjNTRhXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIyZThcdWJjMzFcdWM5YzhcdWM3NTggcHJlZml4XC9zdWZmaXggXHVjOWM4XHViN2M5XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVkNTNjXHVkMDZjXHVhYzAwIFx1YzlkMVx1ZDU2OVx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWQ1M2NcdWQwNmNcdWI5N2MgXHViMTc4XHVjNzc0XHVjOTg4IFx1ZDUzY1x1ZDA2Y1x1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCBcdWQ1M2NcdWQwNmNcdWIyOTQgXHVjNTkxXHVjMjE4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWFjMDBcdWM3YTUgXHVkMDcwIFx1ZDUzY1x1ZDA2Y1x1YjI5NCBcdWIyZThcdWJjMzFcdWM5YzggXHVjODA0XHVjY2I0IFx1YzljOFx1YjdjOVx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+cHJlZml4XC9zdWZmaXggXHVjOWM4XHViN2M5XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWQ1M2NcdWQwNmNcdWIyOTQgXHVjODE1XHVkNjU1XHVkNTVjIFx1YWMxMlx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWMyZTRcdWQ1ZDggXHVhY2IwXHVhY2ZjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Y2Q1Y1x1YjMwMCBcdWQ1M2NcdWQwNmNcdWFjMDAgXHViMmU4XHViYzMxXHVjOWM4XHVjNzU4IFx1YzljOFx1YjdjOVx1Yzc3NFx1YmE3NFx1YzExYywgXHViMTc4XHVjNzc0XHVjOTg4IFx1ZDUzY1x1ZDA2Y1x1Yzc1OCBcdWMyMThcdWFjMDAgXHVjZDVjXHVjMThjXHVjNzc4IFx1YjJlOFx1YmMzMVx1YzljOFx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTVMyXHVjNzU4IFx1YzJlNFx1ZDVkOCBcdWFjYjBcdWFjZmNcdWM3NzggXHVkNTNjXHVkMDZjXHVjNzU4IFx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IGlcdWJjODhcdWM5ZjggXHVkNTNjXHVkMDZjIHA8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTZkXHVjMGMxIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YmE3MCwgXHViYWE4XHViNGUwIFx1ZDUzY1x1ZDA2Y1x1YjI5NCBcdWIyZTRcdWI5NzRcdWIyZTQuIFx1YWMwMSBcdWQ1M2NcdWQwNmNcdWIyOTQgXHVjMThjXHVjMjE4XHVjODEwIFx1Y2Q1Y1x1YjMwMCA1XHVjOWY4XHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFlMzhcdWM3NzRcdWFjMDAgXHVjZDVjXHViMzAwIDQwMFx1Yzc3OCBQXHVjNjQwIFFcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNChcdWIyZThcdWJjMzFcdWM5YzgpXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMTc4XHVjNzc0XHVjOTg4IFx1ZDUzY1x1ZDA2Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjXHVkNTU4XHViMjk0IFx1YjJmNVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWFjMDBcdWIyYTVcdWQ1NWMgXHViMmU4XHViYzMxXHVjOWM4XHVjNzQwIFBRUVx1YzY0MCBRUVBcdWM3NzRcdWIyZTQuIFx1YjQ1MCBcdWIyZThcdWJjMzFcdWM5YzggXHViYWE4XHViNDUwIDI5MS4xNTgyOCwgMzUzLjE2OTkxIFx1YWNiMFx1YWNmY1x1Yjk3YyBcdWM4MWNcdWM2NzhcdWQ1NThcdWJhNzQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzOTk4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSWRlbnRpZmljYXRpb24gb2YgUHJvdGVpbiIsImRlc2NyaXB0aW9uIjoiPHA+QSBwcm90ZWluIGlzIGEgc2VxdWVuY2Ugb2YgYW1pbm8gYWNpZHMuIE9uZSBvZiB0aGUgd2F5cyB0byBzZXF1ZW5jZSAoaS5lLiB0byByZWFkKSBhIHByb3RlaW4gaXMgdG8gdXNlIFRhbmRlbSBtYXNzIHNwZWN0cm9tZXRyeSAodXN1YWxseSBhYmJyZXZpYXRlZCBhcyBNUzxzdXA+MjxcL3N1cD4pLjxcL3A+XHJcblxyXG48cD5JbiB0aGlzIHByb2JsZW0gdGhlIGZvbGxvd2luZyB0b3kgc2l0dWF0aW9uIGlzIGNvbnNpZGVyZWQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QSBwcm90ZWluIGlzIGEgc2VxdWVuY2Ugb2YgYXQgbW9zdCA0MDAgYW1pbm8gYWNpZHMuPFwvbGk+XHJcblx0PGxpPlRoZSBhcmUgb25seSB0d28gdHlwZXMgb2YgYW1pbm8gYWNpZHMsIFAgYW5kIFEuPFwvbGk+XHJcblx0PGxpPk1hc3Mgb2YgUCBpcyA5Ny4wNTI3NiBkYWx0b25zLCBtYXNzIG9mIFEgaXMgMTI4LjA1ODU4IGRhbHRvbnMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIHJlc3VsdCBvZiBhbiBpZGVhbCBtZWFzdXJlbWVudCB2aWEgTVM8c3VwPjI8XC9zdXA+IGlzIGEgc2V0IG9mIHJlYWwgbnVtYmVycyBjYWxsZWQgcGVha3MsIHdoaWNoIGNvbnRhaW5zIHRoZSBtYXNzIG9mIGVhY2ggcHJlXHVmYjAxeCBhbmQgZWFjaCBzdVx1ZmIwM3ggb2YgdGhlIHByb3RlaW4gKGluY2x1ZGluZyB0aGUgZW50aXJlIHByb3RlaW4pLCBhbmQgbm8gb3RoZXIgbnVtYmVycy48XC9wPlxyXG5cclxuPHA+QnV0IGl0JnJzcXVvO3MgbmV2ZXIgaWRlYWwgaW4gcHJhY3RpY2UuIFlvdSZyc3F1bztyZSBnaXZlbiB0aGUgcmVzdWx0cyBvZiBNUzxzdXA+MjxcL3N1cD4gZXhwZXJpbWVudCBmb3IgYW4gdW5rbm93biBwcm90ZWluLiBUaGUgZm9sbG93aW5nIGNvbmRpdGlvbnMgaG9sZDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5tYXNzZXMgb2Ygc29tZSBwcmVcdWZiMDF4ZXMgYW5kXC9vciBzb21lIHN1XHVmYjAzeGVzIG1pZ2h0IGJlIGFic2VudCBpbiB0aGUgc2V0LjxcL2xpPlxyXG5cdDxsaT5zb21lIHBlYWtzIHRoYXQgZG8gbm90IGNvcnJlc3BvbmQgdG8gYW55IHByZVx1ZmIwMXhcL3N1XHVmYjAzeCBtYXNzIG1pZ2h0IGJlIGluY2x1ZGVkIGluIHRoZSBzZXQgKHRoZXkgYXJlIGNhbGxlZCBub2lzZSBwZWFrcykuPFwvbGk+XHJcblx0PGxpPmFsbCBwZWFrcyBhcmUgcG9zaXRpdmUgbnVtYmVycy48XC9saT5cclxuXHQ8bGk+dGhlIGxhcmdlc3QgcGVhayBpbiB0aGUgc2V0IGlzIGVxdWFsIHRvIHRoZSBtYXNzIG9mIHRoZSBlbnRpcmUgcHJvdGVpbi48XC9saT5cclxuXHQ8bGk+YWxsIHBlYWtzIHRoYXQgY29ycmVzcG9uZCB0byBwcmVcdWZiMDF4XC9zdVx1ZmIwM3ggbWFzc2VzIGFyZSBleGFjdCBtZWFzdXJlbWVudHMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+UmVjb25zdHJ1Y3QgdGhlIHByb3RlaW4gdGhhdCBoYXMgdGhlIG1hc3MgZXF1YWwgdG8gdGhlIGxhcmdlc3QgcGVhayBhbmQgbWluaW1pemVzIHRoZSBudW1iZXIgb2Ygbm9pc2UgcGVha3MgKGFuZCB0aHVzIG1heGltaXplcyB0aGUgbnVtYmVyIG9mIHBlYWtzIHRoYXQgY29ycmVzcG9uZCB0byBpdHMgc3VcdWZiMDN4ZXMgb3IgcHJlXHVmYjAxeGVzKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBjb250YWlucyBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMTAwIDAwMCksIHRoZSBudW1iZXIgb2YgcGVha3MgaW4gdGhlIGdpdmVuIE1TPHN1cD4yPFwvc3VwPiBleHBlcmltZW50IHJlc3VsdHMuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgbiBsaW5lcyBjb250YWlucyBhIHBvc2l0aXZlIHJlYWwgbnVtYmVyIHA8c3ViPmk8XC9zdWI+LCB0aGUgbWFzcyBvZiB0aGUgaS10aCBwZWFrLjxcL3A+XHJcblxyXG48cD5BbGwgb2YgYWJvdmUgY29uZGl0aW9ucyBhcmUgZ3VhcmFudGVlZCB0byBiZSBzYXRpc1x1ZmIwMWVkLiBBbGwgcGVha3MgYXJlIGRpc3RpbmN0LiBFYWNoIHBlYWsgaGFzIG5vIG1vcmUgdGhhbiA1IGRpZ2l0cyBhZnRlciBhIGRlY2ltYWwgcG9pbnQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGEgc3RyaW5nIG9mIHVwIHRvIDQwMCBjaGFyYWN0ZXJzIGNvbnNpc3Rpbmcgb25seSBvZiAmbHNxdW87UCZyc3F1bzsgYW5kICZsc3F1bztRJnJzcXVvOyBjaGFyYWN0ZXJzICZtZGFzaDsgdGhlIHJlY29uc3RydWN0ZWQgcHJvdGVpbi4gSWYgdGhlcmUgYXJlIG11bHRpcGxlIGFuc3dlcnMgdGhhdCBtaW5pbWl6ZSB0aGUgbnVtYmVyIG9mIG5vaXNlIHBlYWtzLCBvdXRwdXQgYW55IG9uZSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGUgZ2l2ZW4gZXhhbXBsZSwgdGhlIHByb3RlaW4gUFFRIChvciBRUVApIGV4cGxhaW5zIGFsbCBwZWFrcyBleGNlcHQgdHdvOiAyOTEuMTU4MjggYW5kIDM1My4xNjk5MS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=