시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 85 8 7 17.949%

문제

20세기 중반에 사회학자들은 맥주에 관련된 학생들의 행동에 대한 연구를 시작했다. 연구의 가장 큰 성과는 학생들의 수업이 끝나고 난 이후에 호프집을 선택하는 복잡한 과정을 매우 정확하게 묘사하는 방법을 개발한 것이다.

학생들은 호프집을 투표를 통해서 결정한다. 사회학자들은 일부의 주도하는 학생들이 다른 학생들에게 눈치를 주는 점에 주목했다. 

호프집을 선택하는 과정은 다음과 같이 나타낼 수 있다.

  • 주도하는 학생들은 각자 선호하는 호프집을 가지고 있다. 이 학생들은 항상 그 호프집에 표를 던진다. 주도적인 학생 여러 명이 같은 호프집에 표를 던질 수도 있다.
  • 그 다음, 남은 학생들은 모두 주도적인 학생이 아니다. 이 학생들은 주도적인 학생들의 눈치를 보면서 확률적으로 투표를 하며. 그들이 어떤 특정 호프집에 투표를 할 확률은, 그 호프집이 그 때까지 받은 표의 수를 그 때 까지 투표한 사람의 수로 나눈 값이다.
  • 모든 사람이 투표를 하게 되면, 가장 높은 표를 얻은 호프집이 선택된다. 만약, 가장 높은 표를 받은 호프집이 여러 개인 경우에는, 임의로 선택한다. (이때, 각 호프집을 선택할 확률은 모두 같다)

예를 들어, 학생이 일곱 명, 호프집이 세 개가 있고, 그 중 다섯 명이 주도적인 학생인 경우를 생각해보자. 세 학생이 1번 호프집에 표를 던지고, 나머지 학생이 각각 2번과 3번 호프집에 표를 던졌다고 하자. 이제 각 호프집이 받은 표의 수는 (3, 1, 1)이 된다.

이제 주도적이지 않은 학생 두 명이 투표를 해야 한다. 각 학생은 차례대로 투표를 한다. 먼저, 첫 번째 학생이 1번 호프집을 선택할 확률은 3/5, 2번과 3번을 선택할 확률은 1/5이다. 이 학생이 3번 호프집을 선택하면, 각 호프집이 받은 표의 수는 (3, 1, 2)가 된다.

두 번째 학생이 1번 호프집을 선택할 확률은 1/2, 2번 호프집은 1/6, 3번 호프집은 1/3이 된다. 이 학생은 3번 호프집을 선택했다고 하면, 각 호프집이 받은 표의 수는 (3, 1, 3)이 된다. 1번 호프집과 3번 호프집의 표가 같기 때문에, 두 호프집은 1/2의 확률로 선택을 받게 된다.

학생의 수와, 호프집의 수, 그리고 모든 주도적인 학생들이 선택한 호프집이 주어진다. 이때, 각 호프집을 갈 확률을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 맥주집의 수 n (n ≤ 5)과 학생의 수 k가 주어진다. (k ≤ 50) 둘째 줄에는 주도적인 학생의 투표가 끝난 후의 결과 a1, a2, ..., an이 주어진다. 항상 \( k \ge \sum_{i=1}^{n}{a_i}\)를 만족한다.

출력

각 테스트 케이스에 대해서, 각 맥주집이 선택받을 확률을 출력한다. 'pub i: percentage %'와 같이 출력하며, i는 맥주집의 번호, percentage는 그 맥주집을 선택할 확률을 반올림해서 소수점 둘째 자리까지 나타낸 값이다.

예제 입력 1

3 7
3 1 1

예제 출력 1

pub 1: 93.33 %
pub 2: 3.33 %
pub 3: 3.33 %
W3sicHJvYmxlbV9pZCI6IjM2NDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2MzhcdWQ1MDRcdWM5ZDEgXHVjMTIwXHVkMGRkIiwiZGVzY3JpcHRpb24iOiI8cD4yMFx1YzEzOFx1YWUzMCBcdWM5MTFcdWJjMThcdWM1ZDAgXHVjMGFjXHVkNjhjXHVkNTU5XHVjNzkwXHViNGU0XHVjNzQwIFx1YjllNVx1YzhmY1x1YzVkMCBcdWFkMDBcdWI4MjhcdWI0MWMgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1ZDU4OVx1YjNkOVx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjNWYwXHVhZDZjXHViOTdjIFx1YzJkY1x1Yzc5MVx1ZDU4OFx1YjJlNC4gXHVjNWYwXHVhZDZjXHVjNzU4IFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVjMTMxXHVhY2ZjXHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWMyMThcdWM1YzVcdWM3NzQgXHViMDVkXHViMDk4XHVhY2UwIFx1YjA5YyBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjI5NCBcdWJjZjVcdWM3YTFcdWQ1NWMgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YjllNFx1YzZiMCBcdWM4MTVcdWQ2NTVcdWQ1NThcdWFjOGMgXHViYjE4XHVjMGFjXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWFjMWNcdWJjMWNcdWQ1NWMgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzQ0IFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWQxYjVcdWQ1NzRcdWMxMWMgXHVhY2IwXHVjODE1XHVkNTVjXHViMmU0LiBcdWMwYWNcdWQ2OGNcdWQ1NTlcdWM3OTBcdWI0ZTRcdWM3NDAgXHVjNzdjXHViZDgwXHVjNzU4IFx1YzhmY1x1YjNjNFx1ZDU1OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHViMmU0XHViOTc4IFx1ZDU1OVx1YzBkZFx1YjRlNFx1YzVkMFx1YWM4YyBcdWIyMDhcdWNlNThcdWI5N2MgXHVjOGZjXHViMjk0IFx1YzgxMFx1YzVkMCBcdWM4ZmNcdWJhYTlcdWQ1ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTQgXHVhY2ZjXHVjODE1XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjOGZjXHViM2M0XHVkNTU4XHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWFjMDFcdWM3OTAgXHVjMTIwXHVkNjM4XHVkNTU4XHViMjk0IFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc0NCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3NzQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWFkZjggXHVkNjM4XHVkNTA0XHVjOWQxXHVjNWQwIFx1ZDQ1Y1x1Yjk3YyBcdWIzNThcdWM5YzRcdWIyZTQuIFx1YzhmY1x1YjNjNFx1YzgwMVx1Yzc3OCBcdWQ1NTlcdWMwZGQgXHVjNWVjXHViN2VjIFx1YmE4NVx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNWQwIFx1ZDQ1Y1x1Yjk3YyBcdWIzNThcdWM5YzggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZGY4IFx1YjJlNFx1Yzc0YywgXHViMGE4XHVjNzQwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjOGZjXHViM2M0XHVjODAxXHVjNzc4IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1Yzc3NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVjOGZjXHViM2M0XHVjODAxXHVjNzc4IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWIyMDhcdWNlNThcdWI5N2MgXHViY2Y0XHViYTc0XHVjMTFjIFx1ZDY1NVx1Yjk2MFx1YzgwMVx1YzczY1x1Yjg1YyBcdWQyMmNcdWQ0NWNcdWI5N2MgXHVkNTU4XHViYTcwLiBcdWFkZjhcdWI0ZTRcdWM3NzQgXHVjNWI0XHViNWE0IFx1ZDJiOVx1YzgxNSBcdWQ2MzhcdWQ1MDRcdWM5ZDFcdWM1ZDAgXHVkMjJjXHVkNDVjXHViOTdjIFx1ZDU2MCBcdWQ2NTVcdWI5NjBcdWM3NDAsIFx1YWRmOCBcdWQ2MzhcdWQ1MDRcdWM5ZDFcdWM3NzQgXHVhZGY4IFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWJjMWJcdWM3NDAgXHVkNDVjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkZjggXHViNTRjIFx1YWU0Y1x1YzljMCBcdWQyMmNcdWQ0NWNcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOFx1Yjg1YyBcdWIwOThcdWIyMDggXHVhYzEyXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWQ1NThcdWFjOGMgXHViNDE4XHViYTc0LCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1ZDQ1Y1x1Yjk3YyBcdWM1YmJcdWM3NDAgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzc0IFx1YzEyMFx1ZDBkZFx1YjQxY1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1ZDQ1Y1x1Yjk3YyBcdWJjMWJcdWM3NDAgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0LCBcdWM3ODRcdWM3NThcdWI4NWMgXHVjMTIwXHVkMGRkXHVkNTVjXHViMmU0LiAoXHVjNzc0XHViNTRjLCBcdWFjMDEgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWQ2NTVcdWI5NjBcdWM3NDAgXHViYWE4XHViNDUwIFx1YWMxOVx1YjJlNCk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjNzdjXHVhY2YxIFx1YmE4NSwgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzc0IFx1YzEzOCBcdWFjMWNcdWFjMDAgXHVjNzg4XHVhY2UwLCBcdWFkZjggXHVjOTExIFx1YjJlNFx1YzEyZiBcdWJhODVcdWM3NzQgXHVjOGZjXHViM2M0XHVjODAxXHVjNzc4IFx1ZDU1OVx1YzBkZFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLiBcdWMxMzggXHVkNTU5XHVjMGRkXHVjNzc0IDFcdWJjODggXHVkNjM4XHVkNTA0XHVjOWQxXHVjNWQwIFx1ZDQ1Y1x1Yjk3YyBcdWIzNThcdWM5YzBcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVhYzAxXHVhYzAxIDJcdWJjODhcdWFjZmMgM1x1YmM4OCBcdWQ2MzhcdWQ1MDRcdWM5ZDFcdWM1ZDAgXHVkNDVjXHViOTdjIFx1YjM1OFx1Yzg0Y1x1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Yzc3NFx1YzgxYyBcdWFjMDEgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzc0IFx1YmMxYlx1Yzc0MCBcdWQ0NWNcdWM3NTggXHVjMjE4XHViMjk0ICgzLCAxLCAxKVx1Yzc3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzgxYyBcdWM4ZmNcdWIzYzRcdWM4MDFcdWM3NzRcdWM5YzAgXHVjNTRhXHVjNzQwIFx1ZDU1OVx1YzBkZCBcdWI0NTAgXHViYTg1XHVjNzc0IFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVkNTU5XHVjMGRkXHVjNzQwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWQyMmNcdWQ0NWNcdWI5N2MgXHVkNTVjXHViMmU0LiBcdWJhM2NcdWM4MDAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNTU5XHVjMGRkXHVjNzc0IDFcdWJjODggXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWQ2NTVcdWI5NjBcdWM3NDAgM1wvNSwgMlx1YmM4OFx1YWNmYyAzXHViYzg4XHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWQ2NTVcdWI5NjBcdWM3NDAgMVwvNVx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1ZDU1OVx1YzBkZFx1Yzc3NCAzXHViYzg4IFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NThcdWJhNzQsIFx1YWMwMSBcdWQ2MzhcdWQ1MDRcdWM5ZDFcdWM3NzQgXHViYzFiXHVjNzQwIFx1ZDQ1Y1x1Yzc1OCBcdWMyMThcdWIyOTQgKDMsIDEsIDIpXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWQ1NTlcdWMwZGRcdWM3NzQgMVx1YmM4OCBcdWQ2MzhcdWQ1MDRcdWM5ZDFcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTYwIFx1ZDY1NVx1Yjk2MFx1Yzc0MCAxXC8yLCAyXHViYzg4IFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc0MCAxXC82LCAzXHViYzg4IFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc0MCAxXC8zXHVjNzc0IFx1YjQxY1x1YjJlNC4gXHVjNzc0IFx1ZDU1OVx1YzBkZFx1Yzc0MCAzXHViYzg4IFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1ODhcdWIyZTRcdWFjZTAgXHVkNTU4XHViYTc0LCBcdWFjMDEgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzc0IFx1YmMxYlx1Yzc0MCBcdWQ0NWNcdWM3NTggXHVjMjE4XHViMjk0ICgzLCAxLCAzKVx1Yzc3NCBcdWI0MWNcdWIyZTQuIDFcdWJjODggXHVkNjM4XHVkNTA0XHVjOWQxXHVhY2ZjIDNcdWJjODggXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzU4IFx1ZDQ1Y1x1YWMwMCBcdWFjMTlcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWI0NTAgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzQwIDFcLzJcdWM3NTggXHVkNjU1XHViOTYwXHViODVjIFx1YzEyMFx1ZDBkZFx1Yzc0NCBcdWJjMWJcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NTlcdWMwZGRcdWM3NTggXHVjMjE4XHVjNjQwLCBcdWQ2MzhcdWQ1MDRcdWM5ZDFcdWM3NTggXHVjMjE4LCBcdWFkZjhcdWI5YWNcdWFjZTAgXHViYWE4XHViNGUwIFx1YzhmY1x1YjNjNFx1YzgwMVx1Yzc3OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHVjMTIwXHVkMGRkXHVkNTVjIFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhYzAxIFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc0NCBcdWFjMDggXHVkNjU1XHViOTYwXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjllNVx1YzhmY1x1YzlkMVx1Yzc1OCBcdWMyMTggbiAobiAmbGU7IDUpXHVhY2ZjIFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWMyMTgga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChrICZsZTsgNTApIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOGZjXHViM2M0XHVjODAxXHVjNzc4IFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWQyMmNcdWQ0NWNcdWFjMDAgXHViMDVkXHViMDljIFx1ZDZjNFx1Yzc1OCBcdWFjYjBcdWFjZmMgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkNTZkXHVjMGMxIFxcKCBrIFxcZ2UgXFxzdW1fe2k9MX1ee259e2FfaX1cXClcdWI5N2MgXHViOWNjXHVjODcxXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhYzAxIFx1YjllNVx1YzhmY1x1YzlkMVx1Yzc3NCBcdWMxMjBcdWQwZGRcdWJjMWJcdWM3NDQgXHVkNjU1XHViOTYwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gJiMzOTtwdWIgaTogcGVyY2VudGFnZSAlJiMzOTtcdWM2NDAgXHVhYzE5XHVjNzc0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3MCwgaVx1YjI5NCBcdWI5ZTVcdWM4ZmNcdWM5ZDFcdWM3NTggXHViYzg4XHVkNjM4LCBwZXJjZW50YWdlXHViMjk0IFx1YWRmOCBcdWI5ZTVcdWM4ZmNcdWM5ZDFcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTYwIFx1ZDY1NVx1Yjk2MFx1Yzc0NCBcdWJjMThcdWM2MmNcdWI5YmNcdWQ1NzRcdWMxMWMgXHVjMThjXHVjMjE4XHVjODEwIFx1YjQ1OFx1YzlmOCBcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHViMDk4XHVkMGMwXHViMGI4IFx1YWMxMlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjQxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQmVlciBQcmVzc3VyZSIsImRlc2NyaXB0aW9uIjoiPHA+RXZlciBzaW5jZSB0aGUgbWlkZGxlIG9mIHRoZSAyMHRoIGNlbnR1cnksIHNvY2lvbG9naXN0cyBoYXZlIGJlZW4gc3R1ZHlpbmcgdGhlIGZhc2NpbmF0aW5nIHRvcGljIG9mIGJlZXItcmVsYXRlZCBiZWhhdmlvdXIgYW1vbmcgdGhlIHN0dWRlbnQgcG9wdWxhdGlvbiBpbiBEZWxmdC4gT25lIG9mIHRoZSBncmVhdCBzdWNjZXNzZXMgaGFzIGJlZW4gdGhlIGRldmVsb3BtZW50IG9mIGEgaGlnaGx5IGFjY3VyYXRlIG1vZGVsIHRoYXQgZGVzY3JpYmVzIHRoZSBpbnRyaWNhdGUgcml0dWFsIG9mIHB1YiBzZWxlY3Rpb24sIHRoYXQgY2FuIGJlIG9ic2VydmVkIGluIHRoZSBhZnRlcm5vb24gYWZ0ZXIgdGhlIGNvdXJzZXMgZm9yIHRoZSBkYXkgYXJlIGRvbmUuPFwvcD5cclxuXHJcbjxwPlN0dWRlbnRzIHNlbGVjdCBhIHB1YiBieSBjYXN0aW5nIHZvdGVzLiBXaGF0IG1ha2VzIGl0IGludGVyZXN0aW5nIGZyb20gYSBzb2Npb2xvZ2ljYWwgcGVyc3BlY3RpdmUgaXMgdGhlIG1peCBvZiBkb21pbmFudCBiZWhhdmlvdXIgYnkgc29tZSBzdHVkZW50cywgYW5kIGJlaGF2aW91ciBkcml2ZW4gYnkgcGVlciBwcmVzc3VyZSBjb21iaW5lZCB3aXRoIHJhbmRvbW5lc3MgYnkgb3RoZXIgc3R1ZGVudHMuPFwvcD5cclxuXHJcbjxwPlNwZWNpXHVmYjAxY2FsbHksIHRoZSBtb2RlbCB1c2VkIHRvIGRlc2NyaWJlIHRoZSBwdWIgc2VsZWN0aW9uIHJpdHVhbCBpcyB0aGlzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlRoZSBkb21pbmFudCBzdHVkZW50cywgd2hvIGhhdmUgYSBzdHJvbmcgcHJlZmVyZW5jZSBmb3IgYSBwYXJ0aWN1bGFyIHB1Yiwgd2lsbCAobG91ZGx5KSBhbm5vdW5jZSB0aGVpciB2b3RlLiBTZXZlcmFsIGRvbWluYW50IHN0dWRlbnRzIG1heSB2b3RlIGZvciB0aGUgc2FtZSBwdWIuPFwvbGk+XHJcblx0PGxpPk5leHQsIHRoZSByZW1haW5pbmcgc3R1ZGVudHMgdm90ZSwgb25lIGJ5IG9uZS4gVGhlc2Ugbm9uLWRvbWluYW50IHN0dWRlbnRzIHZvdGUgcHJvYmFiaWxpc3RpY2FsbHkgYW5kIGFyZSBzdWJqZWN0IHRvIHBlZXIgcHJlc3N1cmU7IHRoZSBwcm9iYWJpbGl0eSB0aGF0IHRoZXkgd2lsbCB2b3RlIGZvciBhbnkgc3BlY2lcdWZiMDFjIHB1YiBpcyBlcXVhbCB0byB0aGUgbnVtYmVyIG9mIHZvdGVzIGNhc3QgZm9yIHRoYXQgc3BlY2lcdWZiMDFjIHB1YiBzbyBmYXIsIGRpdmlkZWQgYnkgdGhlIHRvdGFsIG51bWJlciBvZiB2b3RlcyBjYXN0IHNvIGZhci48XC9saT5cclxuXHQ8bGk+RmluYWxseSwgd2hlbiBhbGwgdm90ZXMgYXJlIGluLCB0aGUgcHViIHdpdGggdGhlIGhpZ2hlc3QgbnVtYmVyIG9mIHZvdGVzIGlzIHNlbGVjdGVkLiBJZiBzZXZlcmFsIHB1YnMgcmVjZWl2ZWQgdGhlIHNhbWUgaGlnaGVzdCBudW1iZXIgb2Ygdm90ZXMsIG9uZSBvZiB0aG9zZSBpcyBzZWxlY3RlZCBhdCByYW5kb20sIHdpdGggZXF1YWwgcHJvYmFiaWxpdHkuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGluIG9uZSBwYXJ0aWN1bGFyIGluc3RhbmNlIHdpdGggc2V2ZW4gc3R1ZGVudHMsIHRoZSBcdWZiMDF2ZSBkb21pbmFudCBzdHVkZW50cyBzdGFydCBieSBkZWNsYXJpbmcgdGhlaXIgdm90ZXMgZm9yIHRocmVlIGRpZmZlcmVudCBwdWJzLiBUaHJlZSBkb21pbmFudCBzdHVkZW50cyBwcm9jbGFpbSBhIHByZWZlcmVuY2UgZm9yIHRoZSBcdWZiMDFyc3QgcHViOyB0aGUgZm91cnRoIGRvbWluYW50IHN0dWRlbnQgYW5ub3VuY2VzIGhlciBwcmVmZXJlbmNlIGZvciBhIHNlY29uZCBwdWIsIGFuZCB0aGUgbGFzdCBkb21pbmFudCBzdHVkZW50IHZvdGVzIGZvciB0aGUgdGhpcmQgcHViLiBUaGlzIGxlYXZlcyB0aGUgaW5pdGlhbCB2b3RlLWNvdW50IGF0ICgzLCAxLCAxKS48XC9wPlxyXG5cclxuPHA+QWZ0ZXIgdGhhdCwgdGhlIHJlbWFpbmluZyB0d28gbm9uLWRvbWluYW50IHN0dWRlbnRzIHN0YXJ0IHRvIHZvdGUsIG9uZSBhZnRlciB0aGUgb3RoZXIuIFRoZSBmaXJzdCBvZiB0aGVtIHdpbGwgcGljayBlaXRoZXIgcHViIG51bWJlciBvbmUgd2l0aCBwcm9iYWJpbGl0eSAzXC81LCBwdWIgbnVtYmVyIHR3byB3aXRoIHByb2JhYmlsaXR5IDFcLzUsIG9yIHB1YiBudW1iZXIgdGhyZWUgd2l0aCBwcm9iYWJpbGl0eSAxXC81LiBIZSBoYXBwZW5zIHRvIHBpY2sgcHViIG51bWJlciB0aHJlZSwgYW5kIHRoZSB2b3RlLWNvdW50IGJlY29tZXMgKDMsIDEsIDIpLjxcL3A+XHJcblxyXG48cD5GaW5hbGx5LCB0aGUgbGFzdCBzdHVkZW50IHdpbGwgcGljayBlaXRoZXIgcHViIG51bWJlciBvbmUgd2l0aCBwcm9iYWJpbGl0eSAxXC8yLCBwdWIgbnVtYmVyIHR3byB3aXRoIHByb2JhYmlsaXR5IDFcLzYsIG9yIHB1YiBudW1iZXIgdGhyZWUgd2l0aCBwcm9iYWJpbGl0eSAxXC8zLiBTaGUsIHRvbywgcGlja3MgcHViIG51bWJlciB0aHJlZS48XC9wPlxyXG5cclxuPHA+VGhpcyBsZWF2ZXMgdGhlIFx1ZmIwMW5hbCB2b3RlLWNvdW50IGF0ICgzLCAxLCAzKTogYSB0aWUgYmV0d2VlbiBwdWIgb25lIGFuZCBwdWIgdGhyZWUuIFRoaXMgdGllIGlzIGJyb2tlbiBieSBhIGNvaW4tdG9zczsgd2l0aCBwcm9iYWJpbGl0eSAxXC8yLCBwdWIgb25lIGlzIHNlbGVjdGVkIGZvciB0aGF0IGV2ZW5pbmcmcnNxdW87cyBkcmlua2luZy48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBhIHNvY2lvbG9naXN0IG9ic2VydmluZyB0aGUgcml0dWFsIGRlc2NyaWJlZCBhYm92ZS4gQWZ0ZXIgdGhlIGRvbWluYW50IHN0dWRlbnRzIGFyZSBkb25lIGRlY2xhcmluZyB0aGVpciB2b3RlcywgeW91IHdhbnQgdG8ga25vdyB3aGF0IHRoZSBwcm9iYWJpbGl0aWVzIGFyZSBmb3IgZWFjaCBwdWIgdGhhdCB0aGV5IHdpbGwgYmUgc2VydmluZyBkcmlua3MgdG8gdGhlIHN0dWRlbnRzIHRoYXQgbmlnaHQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHRoZSBpbnB1dCBjb25zaXN0cyBvZiB0d28gbGluZXM6PFwvcD5cclxuXHJcbjxwPmEgbGluZSBjb250YWluaW5nIHR3byBwb3NpdGl2ZSBpbnRlZ2VyczogbiwgZGVub3RpbmcgdGhlIG51bWJlciBvZiBwdWJzIGluIHRoaXMgdHJpYWwgKG4gJmxlOyA1KTsgYW5kIGssIHRoZSB0b3RhbCBudW1iZXIgb2Ygc3R1ZGVudHMsIGJvdGggZG9taW5hbnQgYW5kIG5vbi1kb21pbmFudCAoayAmbGU7IDUwKS48YnIgXC8+XHJcbmEgbGluZSBjb250YWluaW5nIG4gcG9zaXRpdmUgaW50ZWdlcnMgKGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5uPFwvc3ViPiksIGRlbm90aW5nIHRoZSB2b3RlLWNvdW50IHJpZ2h0IGFmdGVyIGFsbCBkb21pbmFudCBzdHVkZW50cyBoYXZlIGNhc3QgdGhlaXIgdm90ZS48XC9wPlxyXG5cclxuPHA+RnVydGhlcm1vcmUsIGl0IGlzIGd1YXJhbnRlZWQgdGhhdCZuYnNwO1xcKCBrIFxcZ2UgXFxzdW1fe2k9MX1ee259e2FfaX1cXCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHdyaXRlIG4gbGluZXMgb2Ygb3V0cHV0IGNvbnRhaW5pbmcgdGhlIHByb2JhYmlsaXR5IHRoYXQgdGhlIGkmcnNxdW87dGggcHViIHdpbGwgYmUgc2VsZWN0ZWQgKDEgJmxlOyBpICZsZTsgbiksIG9yZGVyZWQgYnkgYXNjZW5kaW5nIGkuPFwvcD5cclxuXHJcbjxwPkVhY2ggbGluZSBzaGFsbCBiZSBvZiB0aGUgZm9ybSAmbHNxdW87cHViIGk6IHBlcmNlbnRhZ2UgJSZyc3F1bzssIHdoZXJlIHBlcmNlbnRhZ2UgaXMgYSBcdWZiMDJvYXRpbmcgcG9pbnQgbnVtYmVyIHJvdW5kZWQgdG8gMiBkaWdpdHMgYWZ0ZXIgdGhlIGRlY2ltYWwgcG9pbnQuPFwvcD5cclxuXHJcbjxwPkEgc3BhY2Ugc2hvdWxkIHNlcGFyYXRlIHRoZSBwZXJjZW50YWdlIG51bWJlciBhbmQgdGhlIHN1YnNlcXVlbnQgcGVyY2VudCBzaWduLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2012 B번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: corea