시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVkNTZkXHVjMGMxIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1YzJkY1x1ZDBhNFx1YmE3MCwgXHViYWE4XHViNGUwIFx1ZDUzY1x1ZDA2Y1x1YjI5NCBcdWIyZTRcdWI5NzRcdWIyZTQuIFx1YWMwMSBcdWQ1M2NcdWQwNmNcdWIyOTQgXHVjMThjXHVjMjE4XHVjODEwIFx1Y2Q1Y1x1YjMwMCA1XHVjOWY4XHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFlMzhcdWM3NzRcdWFjMDAgXHVjZDVjXHViMzAwIDQwMFx1Yzc3OCBQXHVjNjQwIFFcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNChcdWIyZThcdWJjMzFcdWM5YzgpXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMTc4XHVjNzc0XHVjOTg4IFx1ZDUzY1x1ZDA2Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjXHVkNTU4XHViMjk0IFx1YjJmNVx1Yzc3NCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YWMwMFx1YjJhNVx1ZDU1YyBcdWIyZThcdWJjMzFcdWM5YzhcdWM3NDAgUFFRXHVjNjQwIFFRUFx1Yzc3NFx1YjJlNC4gXHViNDUwIFx1YjJlOFx1YmMzMVx1YzljOCBcdWJhYThcdWI0NTAgMjkxLjE1ODI4LCAzNTMuMTY5OTEgXHVhY2IwXHVhY2ZjXHViOTdjIFx1YzgxY1x1YzY3OFx1ZDU1OFx1YmE3NCBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM5OTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJZGVudGlmaWNhdGlvbiBvZiBQcm90ZWluIiwiZGVzY3JpcHRpb24iOiI8cD5BIHByb3RlaW4gaXMgYSBzZXF1ZW5jZSBvZiBhbWlubyBhY2lkcy4gT25lIG9mIHRoZSB3YXlzIHRvIHNlcXVlbmNlIChpLmUuIHRvIHJlYWQpIGEgcHJvdGVpbiBpcyB0byB1c2UgVGFuZGVtIG1hc3Mgc3BlY3Ryb21ldHJ5ICh1c3VhbGx5IGFiYnJldmlhdGVkIGFzIE1TPHN1cD4yPFwvc3VwPikuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgcHJvYmxlbSB0aGUgZm9sbG93aW5nIHRveSBzaXR1YXRpb24gaXMgY29uc2lkZXJlZDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BIHByb3RlaW4gaXMgYSBzZXF1ZW5jZSBvZiBhdCBtb3N0IDQwMCBhbWlubyBhY2lkcy48XC9saT5cclxuXHQ8bGk+VGhlIGFyZSBvbmx5IHR3byB0eXBlcyBvZiBhbWlubyBhY2lkcywgUCBhbmQgUS48XC9saT5cclxuXHQ8bGk+TWFzcyBvZiBQIGlzIDk3LjA1Mjc2IGRhbHRvbnMsIG1hc3Mgb2YgUSBpcyAxMjguMDU4NTggZGFsdG9ucy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgcmVzdWx0IG9mIGFuIGlkZWFsIG1lYXN1cmVtZW50IHZpYSBNUzxzdXA+MjxcL3N1cD4gaXMgYSBzZXQgb2YgcmVhbCBudW1iZXJzIGNhbGxlZCBwZWFrcywgd2hpY2ggY29udGFpbnMgdGhlIG1hc3Mgb2YgZWFjaCBwcmVcdWZiMDF4IGFuZCBlYWNoIHN1XHVmYjAzeCBvZiB0aGUgcHJvdGVpbiAoaW5jbHVkaW5nIHRoZSBlbnRpcmUgcHJvdGVpbiksIGFuZCBubyBvdGhlciBudW1iZXJzLjxcL3A+XHJcblxyXG48cD5CdXQgaXQmcnNxdW87cyBuZXZlciBpZGVhbCBpbiBwcmFjdGljZS4gWW91JnJzcXVvO3JlIGdpdmVuIHRoZSByZXN1bHRzIG9mIE1TPHN1cD4yPFwvc3VwPiBleHBlcmltZW50IGZvciBhbiB1bmtub3duIHByb3RlaW4uIFRoZSBmb2xsb3dpbmcgY29uZGl0aW9ucyBob2xkOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm1hc3NlcyBvZiBzb21lIHByZVx1ZmIwMXhlcyBhbmRcL29yIHNvbWUgc3VcdWZiMDN4ZXMgbWlnaHQgYmUgYWJzZW50IGluIHRoZSBzZXQuPFwvbGk+XHJcblx0PGxpPnNvbWUgcGVha3MgdGhhdCBkbyBub3QgY29ycmVzcG9uZCB0byBhbnkgcHJlXHVmYjAxeFwvc3VcdWZiMDN4IG1hc3MgbWlnaHQgYmUgaW5jbHVkZWQgaW4gdGhlIHNldCAodGhleSBhcmUgY2FsbGVkIG5vaXNlIHBlYWtzKS48XC9saT5cclxuXHQ8bGk+YWxsIHBlYWtzIGFyZSBwb3NpdGl2ZSBudW1iZXJzLjxcL2xpPlxyXG5cdDxsaT50aGUgbGFyZ2VzdCBwZWFrIGluIHRoZSBzZXQgaXMgZXF1YWwgdG8gdGhlIG1hc3Mgb2YgdGhlIGVudGlyZSBwcm90ZWluLjxcL2xpPlxyXG5cdDxsaT5hbGwgcGVha3MgdGhhdCBjb3JyZXNwb25kIHRvIHByZVx1ZmIwMXhcL3N1XHVmYjAzeCBtYXNzZXMgYXJlIGV4YWN0IG1lYXN1cmVtZW50cy48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5SZWNvbnN0cnVjdCB0aGUgcHJvdGVpbiB0aGF0IGhhcyB0aGUgbWFzcyBlcXVhbCB0byB0aGUgbGFyZ2VzdCBwZWFrIGFuZCBtaW5pbWl6ZXMgdGhlIG51bWJlciBvZiBub2lzZSBwZWFrcyAoYW5kIHRodXMgbWF4aW1pemVzIHRoZSBudW1iZXIgb2YgcGVha3MgdGhhdCBjb3JyZXNwb25kIHRvIGl0cyBzdVx1ZmIwM3hlcyBvciBwcmVcdWZiMDF4ZXMpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIGNvbnRhaW5zIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiBwZWFrcyBpbiB0aGUgZ2l2ZW4gTVM8c3VwPjI8XC9zdXA+IGV4cGVyaW1lbnQgcmVzdWx0cy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBuIGxpbmVzIGNvbnRhaW5zIGEgcG9zaXRpdmUgcmVhbCBudW1iZXIgcDxzdWI+aTxcL3N1Yj4sIHRoZSBtYXNzIG9mIHRoZSBpLXRoIHBlYWsuPFwvcD5cclxuXHJcbjxwPkFsbCBvZiBhYm92ZSBjb25kaXRpb25zIGFyZSBndWFyYW50ZWVkIHRvIGJlIHNhdGlzXHVmYjAxZWQuIEFsbCBwZWFrcyBhcmUgZGlzdGluY3QuIEVhY2ggcGVhayBoYXMgbm8gbW9yZSB0aGFuIDUgZGlnaXRzIGFmdGVyIGEgZGVjaW1hbCBwb2ludC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYSBzdHJpbmcgb2YgdXAgdG8gNDAwIGNoYXJhY3RlcnMgY29uc2lzdGluZyBvbmx5IG9mICZsc3F1bztQJnJzcXVvOyBhbmQgJmxzcXVvO1EmcnNxdW87IGNoYXJhY3RlcnMgJm1kYXNoOyB0aGUgcmVjb25zdHJ1Y3RlZCBwcm90ZWluLiBJZiB0aGVyZSBhcmUgbXVsdGlwbGUgYW5zd2VycyB0aGF0IG1pbmltaXplIHRoZSBudW1iZXIgb2Ygbm9pc2UgcGVha3MsIG91dHB1dCBhbnkgb25lIG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoZSBnaXZlbiBleGFtcGxlLCB0aGUgcHJvdGVpbiBQUVEgKG9yIFFRUCkgZXhwbGFpbnMgYWxsIHBlYWtzIGV4Y2VwdCB0d286IDI5MS4xNTgyOCBhbmQgMzUzLjE2OTkxLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==