시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 90 11 8 18.605%

문제

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+XHVhZGY4IFx1YjJlNFx1Yzc0YywgXHViMGE4XHVjNzQwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWJhYThcdWI0NTAgXHVjOGZjXHViM2M0XHVjODAxXHVjNzc4IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1Yzc3NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVjOGZjXHViM2M0XHVjODAxXHVjNzc4IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc1OCBcdWIyMDhcdWNlNThcdWI5N2MgXHViY2Y0XHViYTc0XHVjMTFjIFx1ZDY1NVx1Yjk2MFx1YzgwMVx1YzczY1x1Yjg1YyBcdWQyMmNcdWQ0NWNcdWI5N2MgXHVkNTU4XHViYTcwLiBcdWFkZjhcdWI0ZTRcdWM3NzQgXHVjNWI0XHViNWE0IFx1ZDJiOVx1YzgxNSBcdWQ2MzhcdWQ1MDRcdWM5ZDFcdWM1ZDAgXHVkMjJjXHVkNDVjXHViOTdjIFx1ZDU2MCBcdWQ2NTVcdWI5NjBcdWM3NDAsIFx1YWRmOCBcdWQ2MzhcdWQ1MDRcdWM5ZDFcdWM3NzQgXHVhZGY4IFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWJjMWJcdWM3NDAgXHVkNDVjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkZjggXHViNTRjIFx1YWU0Y1x1YzljMCBcdWQyMmNcdWQ0NWNcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzIxOFx1Yjg1YyBcdWIwOThcdWIyMDggXHVhYzEyXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1ZDIyY1x1ZDQ1Y1x1Yjk3YyBcdWQ1NThcdWFjOGMgXHViNDE4XHViYTc0LCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1ZDQ1Y1x1Yjk3YyBcdWM1YmJcdWM3NDAgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzc0IFx1YzEyMFx1ZDBkZFx1YjQxY1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1ZDQ1Y1x1Yjk3YyBcdWJjMWJcdWM3NDAgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0LCBcdWM3ODRcdWM3NThcdWI4NWMgXHVjMTIwXHVkMGRkXHVkNTVjXHViMmU0LiAoXHVjNzc0IFx1YjU0YywgXHVhYzAxIFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NjAgXHVkNjU1XHViOTYwXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWIyZTQpPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVkNTU5XHVjMGRkXHVjNzc0IFx1Yzc3Y1x1YWNmMSBcdWJhODUsIFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc3NCBcdWMxMzggXHVhYzFjXHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVhZGY4IFx1YzkxMSBcdWIyZTRcdWMxMmYgXHViYTg1XHVjNzc0IFx1YzhmY1x1YjNjNFx1YzgwMVx1Yzc3OCBcdWQ1NTlcdWMwZGRcdWM3NzggXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC4gXHVjMTM4IFx1ZDU1OVx1YzBkZFx1Yzc3NCAxXHViYzg4IFx1ZDYzOFx1ZDUwNFx1YzlkMVx1YzVkMCBcdWQ0NWNcdWI5N2MgXHViMzU4XHVjOWMwXHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzAgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YWMwMVx1YWMwMSAyXHViYzg4XHVhY2ZjIDNcdWJjODggXHVkNjM4XHVkNTA0XHVjOWQxXHVjNWQwIFx1ZDQ1Y1x1Yjk3YyBcdWIzNThcdWM4NGNcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM3NzRcdWM4MWMgXHVhYzAxIFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc3NCBcdWJjMWJcdWM3NDAgXHVkNDVjXHVjNzU4IFx1YzIxOFx1YjI5NCAoMywgMSwgMSlcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM4MWMgXHVjOGZjXHViM2M0XHVjODAxXHVjNzc0XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWQ1NTlcdWMwZGQgXHViNDUwIFx1YmE4NVx1Yzc3NCBcdWQyMmNcdWQ0NWNcdWI5N2MgXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhYzAxIFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVkMjJjXHVkNDVjXHViOTdjIFx1ZDU1Y1x1YjJlNC4gXHViYTNjXHVjODAwLCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDU1OVx1YzBkZFx1Yzc3NCAxXHViYzg4IFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NjAgXHVkNjU1XHViOTYwXHVjNzQwIDNcLzUsIDJcdWJjODhcdWFjZmMgM1x1YmM4OFx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NjAgXHVkNjU1XHViOTYwXHVjNzQwIDFcLzVcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWQ1NTlcdWMwZGRcdWM3NzQgM1x1YmM4OCBcdWQ2MzhcdWQ1MDRcdWM5ZDFcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHViYTc0LCBcdWFjMDEgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzc0IFx1YmMxYlx1Yzc0MCBcdWQ0NWNcdWM3NTggXHVjMjE4XHViMjk0ICgzLCAxLCAyKVx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVkNTU5XHVjMGRkXHVjNzc0IDFcdWJjODggXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWQ2NTVcdWI5NjBcdWM3NDAgMVwvMiwgMlx1YmM4OCBcdWQ2MzhcdWQ1MDRcdWM5ZDFcdWM3NDAgMVwvNiwgM1x1YmM4OCBcdWQ2MzhcdWQ1MDRcdWM5ZDFcdWM3NDAgMVwvM1x1Yzc3NCBcdWI0MWNcdWIyZTQuIFx1Yzc3NCBcdWQ1NTlcdWMwZGRcdWM3NDAgM1x1YmM4OCBcdWQ2MzhcdWQ1MDRcdWM5ZDFcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTg4XHViMmU0XHVhY2UwIFx1ZDU1OFx1YmE3NCwgXHVhYzAxIFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc3NCBcdWJjMWJcdWM3NDAgXHVkNDVjXHVjNzU4IFx1YzIxOFx1YjI5NCAoMywgMSwgMylcdWM3NzQgXHViNDFjXHViMmU0LiAxXHViYzg4IFx1ZDYzOFx1ZDUwNFx1YzlkMVx1YWNmYyAzXHViYzg4IFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc1OCBcdWQ0NWNcdWFjMDAgXHVhYzE5XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViNDUwIFx1ZDYzOFx1ZDUwNFx1YzlkMVx1Yzc0MCAxXC8yXHVjNzU4IFx1ZDY1NVx1Yjk2MFx1Yjg1YyBcdWMxMjBcdWQwZGRcdWM3NDQgXHViYzFiXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOFx1YzY0MCwgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzU4IFx1YzIxOCwgXHVhZGY4XHViOWFjXHVhY2UwIFx1YmFhOFx1YjRlMCBcdWM4ZmNcdWIzYzRcdWM4MDFcdWM3NzggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWQ2MzhcdWQ1MDRcdWM5ZDFcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWFjMDEgXHVkNjM4XHVkNTA0XHVjOWQxXHVjNzQ0IFx1YWMwOCBcdWQ2NTVcdWI5NjBcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWU1XHVjOGZjXHVjOWQxXHVjNzU4IFx1YzIxOCBuIChuICZsZTsgNSlcdWFjZmMgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOCBrXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKGsgJmxlOyA1MCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4ZmNcdWIzYzRcdWM4MDFcdWM3NzggXHVkNTU5XHVjMGRkXHVjNzU4IFx1ZDIyY1x1ZDQ1Y1x1YWMwMCBcdWIwNWRcdWIwOWMgXHVkNmM0XHVjNzU4IFx1YWNiMFx1YWNmYyBhPHN1Yj4xPFwvc3ViPiwgYTxzdWI+MjxcL3N1Yj4sIC4uLiwgYTxzdWI+bjxcL3N1Yj5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQ1NmRcdWMwYzEgXFwoIGsgXFxnZSBcXHN1bV97aT0xfV57bn17YV9pfVxcKVx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFjMDEgXHViOWU1XHVjOGZjXHVjOWQxXHVjNzc0IFx1YzEyMFx1ZDBkZFx1YmMxYlx1Yzc0NCBcdWQ2NTVcdWI5NjBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAmIzM5O3B1YiBpOiBwZXJjZW50YWdlICUmIzM5O1x1YzY0MCBcdWFjMTlcdWM3NzQgXHVjZDljXHViODI1XHVkNTU4XHViYTcwLCBpXHViMjk0IFx1YjllNVx1YzhmY1x1YzlkMVx1Yzc1OCBcdWJjODhcdWQ2MzgsIHBlcmNlbnRhZ2VcdWIyOTQgXHVhZGY4IFx1YjllNVx1YzhmY1x1YzlkMVx1Yzc0NCBcdWMxMjBcdWQwZGRcdWQ1NjAgXHVkNjU1XHViOTYwXHVjNzQ0IFx1YmMxOFx1YzYyY1x1YjliY1x1ZDU3NFx1YzExYyBcdWMxOGNcdWMyMThcdWM4MTAgXHViNDU4XHVjOWY4IFx1Yzc5MFx1YjlhY1x1YWU0Y1x1YzljMCBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzEyXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2NDEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCZWVyIFByZXNzdXJlIiwiZGVzY3JpcHRpb24iOiI8cD5FdmVyIHNpbmNlIHRoZSBtaWRkbGUgb2YgdGhlIDIwdGggY2VudHVyeSwgc29jaW9sb2dpc3RzIGhhdmUgYmVlbiBzdHVkeWluZyB0aGUgZmFzY2luYXRpbmcgdG9waWMgb2YgYmVlci1yZWxhdGVkIGJlaGF2aW91ciBhbW9uZyB0aGUgc3R1ZGVudCBwb3B1bGF0aW9uIGluIERlbGZ0LiBPbmUgb2YgdGhlIGdyZWF0IHN1Y2Nlc3NlcyBoYXMgYmVlbiB0aGUgZGV2ZWxvcG1lbnQgb2YgYSBoaWdobHkgYWNjdXJhdGUgbW9kZWwgdGhhdCBkZXNjcmliZXMgdGhlIGludHJpY2F0ZSByaXR1YWwgb2YgcHViIHNlbGVjdGlvbiwgdGhhdCBjYW4gYmUgb2JzZXJ2ZWQgaW4gdGhlIGFmdGVybm9vbiBhZnRlciB0aGUgY291cnNlcyBmb3IgdGhlIGRheSBhcmUgZG9uZS48XC9wPlxyXG5cclxuPHA+U3R1ZGVudHMgc2VsZWN0IGEgcHViIGJ5IGNhc3Rpbmcgdm90ZXMuIFdoYXQgbWFrZXMgaXQgaW50ZXJlc3RpbmcgZnJvbSBhIHNvY2lvbG9naWNhbCBwZXJzcGVjdGl2ZSBpcyB0aGUgbWl4IG9mIGRvbWluYW50IGJlaGF2aW91ciBieSBzb21lIHN0dWRlbnRzLCBhbmQgYmVoYXZpb3VyIGRyaXZlbiBieSBwZWVyIHByZXNzdXJlIGNvbWJpbmVkIHdpdGggcmFuZG9tbmVzcyBieSBvdGhlciBzdHVkZW50cy48XC9wPlxyXG5cclxuPHA+U3BlY2lcdWZiMDFjYWxseSwgdGhlIG1vZGVsIHVzZWQgdG8gZGVzY3JpYmUgdGhlIHB1YiBzZWxlY3Rpb24gcml0dWFsIGlzIHRoaXM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIGRvbWluYW50IHN0dWRlbnRzLCB3aG8gaGF2ZSBhIHN0cm9uZyBwcmVmZXJlbmNlIGZvciBhIHBhcnRpY3VsYXIgcHViLCB3aWxsIChsb3VkbHkpIGFubm91bmNlIHRoZWlyIHZvdGUuIFNldmVyYWwgZG9taW5hbnQgc3R1ZGVudHMgbWF5IHZvdGUgZm9yIHRoZSBzYW1lIHB1Yi48XC9saT5cclxuXHQ8bGk+TmV4dCwgdGhlIHJlbWFpbmluZyBzdHVkZW50cyB2b3RlLCBvbmUgYnkgb25lLiBUaGVzZSBub24tZG9taW5hbnQgc3R1ZGVudHMgdm90ZSBwcm9iYWJpbGlzdGljYWxseSBhbmQgYXJlIHN1YmplY3QgdG8gcGVlciBwcmVzc3VyZTsgdGhlIHByb2JhYmlsaXR5IHRoYXQgdGhleSB3aWxsIHZvdGUgZm9yIGFueSBzcGVjaVx1ZmIwMWMgcHViIGlzIGVxdWFsIHRvIHRoZSBudW1iZXIgb2Ygdm90ZXMgY2FzdCBmb3IgdGhhdCBzcGVjaVx1ZmIwMWMgcHViIHNvIGZhciwgZGl2aWRlZCBieSB0aGUgdG90YWwgbnVtYmVyIG9mIHZvdGVzIGNhc3Qgc28gZmFyLjxcL2xpPlxyXG5cdDxsaT5GaW5hbGx5LCB3aGVuIGFsbCB2b3RlcyBhcmUgaW4sIHRoZSBwdWIgd2l0aCB0aGUgaGlnaGVzdCBudW1iZXIgb2Ygdm90ZXMgaXMgc2VsZWN0ZWQuIElmIHNldmVyYWwgcHVicyByZWNlaXZlZCB0aGUgc2FtZSBoaWdoZXN0IG51bWJlciBvZiB2b3Rlcywgb25lIG9mIHRob3NlIGlzIHNlbGVjdGVkIGF0IHJhbmRvbSwgd2l0aCBlcXVhbCBwcm9iYWJpbGl0eS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgaW4gb25lIHBhcnRpY3VsYXIgaW5zdGFuY2Ugd2l0aCBzZXZlbiBzdHVkZW50cywgdGhlIFx1ZmIwMXZlIGRvbWluYW50IHN0dWRlbnRzIHN0YXJ0IGJ5IGRlY2xhcmluZyB0aGVpciB2b3RlcyBmb3IgdGhyZWUgZGlmZmVyZW50IHB1YnMuIFRocmVlIGRvbWluYW50IHN0dWRlbnRzIHByb2NsYWltIGEgcHJlZmVyZW5jZSBmb3IgdGhlIFx1ZmIwMXJzdCBwdWI7IHRoZSBmb3VydGggZG9taW5hbnQgc3R1ZGVudCBhbm5vdW5jZXMgaGVyIHByZWZlcmVuY2UgZm9yIGEgc2Vjb25kIHB1YiwgYW5kIHRoZSBsYXN0IGRvbWluYW50IHN0dWRlbnQgdm90ZXMgZm9yIHRoZSB0aGlyZCBwdWIuIFRoaXMgbGVhdmVzIHRoZSBpbml0aWFsIHZvdGUtY291bnQgYXQgKDMsIDEsIDEpLjxcL3A+XHJcblxyXG48cD5BZnRlciB0aGF0LCB0aGUgcmVtYWluaW5nIHR3byBub24tZG9taW5hbnQgc3R1ZGVudHMgc3RhcnQgdG8gdm90ZSwgb25lIGFmdGVyIHRoZSBvdGhlci4gVGhlIGZpcnN0IG9mIHRoZW0gd2lsbCBwaWNrIGVpdGhlciBwdWIgbnVtYmVyIG9uZSB3aXRoIHByb2JhYmlsaXR5IDNcLzUsIHB1YiBudW1iZXIgdHdvIHdpdGggcHJvYmFiaWxpdHkgMVwvNSwgb3IgcHViIG51bWJlciB0aHJlZSB3aXRoIHByb2JhYmlsaXR5IDFcLzUuIEhlIGhhcHBlbnMgdG8gcGljayBwdWIgbnVtYmVyIHRocmVlLCBhbmQgdGhlIHZvdGUtY291bnQgYmVjb21lcyAoMywgMSwgMikuPFwvcD5cclxuXHJcbjxwPkZpbmFsbHksIHRoZSBsYXN0IHN0dWRlbnQgd2lsbCBwaWNrIGVpdGhlciBwdWIgbnVtYmVyIG9uZSB3aXRoIHByb2JhYmlsaXR5IDFcLzIsIHB1YiBudW1iZXIgdHdvIHdpdGggcHJvYmFiaWxpdHkgMVwvNiwgb3IgcHViIG51bWJlciB0aHJlZSB3aXRoIHByb2JhYmlsaXR5IDFcLzMuIFNoZSwgdG9vLCBwaWNrcyBwdWIgbnVtYmVyIHRocmVlLjxcL3A+XHJcblxyXG48cD5UaGlzIGxlYXZlcyB0aGUgXHVmYjAxbmFsIHZvdGUtY291bnQgYXQgKDMsIDEsIDMpOiBhIHRpZSBiZXR3ZWVuIHB1YiBvbmUgYW5kIHB1YiB0aHJlZS4gVGhpcyB0aWUgaXMgYnJva2VuIGJ5IGEgY29pbi10b3NzOyB3aXRoIHByb2JhYmlsaXR5IDFcLzIsIHB1YiBvbmUgaXMgc2VsZWN0ZWQgZm9yIHRoYXQgZXZlbmluZyZyc3F1bztzIGRyaW5raW5nLjxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGEgc29jaW9sb2dpc3Qgb2JzZXJ2aW5nIHRoZSByaXR1YWwgZGVzY3JpYmVkIGFib3ZlLiBBZnRlciB0aGUgZG9taW5hbnQgc3R1ZGVudHMgYXJlIGRvbmUgZGVjbGFyaW5nIHRoZWlyIHZvdGVzLCB5b3Ugd2FudCB0byBrbm93IHdoYXQgdGhlIHByb2JhYmlsaXRpZXMgYXJlIGZvciBlYWNoIHB1YiB0aGF0IHRoZXkgd2lsbCBiZSBzZXJ2aW5nIGRyaW5rcyB0byB0aGUgc3R1ZGVudHMgdGhhdCBuaWdodC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIGlucHV0IGNvbnNpc3RzIG9mIHR3byBsaW5lczo8XC9wPlxyXG5cclxuPHA+YSBsaW5lIGNvbnRhaW5pbmcgdHdvIHBvc2l0aXZlIGludGVnZXJzOiBuLCBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHB1YnMgaW4gdGhpcyB0cmlhbCAobiAmbGU7IDUpOyBhbmQgaywgdGhlIHRvdGFsIG51bWJlciBvZiBzdHVkZW50cywgYm90aCBkb21pbmFudCBhbmQgbm9uLWRvbWluYW50IChrICZsZTsgNTApLjxiciBcLz5cclxuYSBsaW5lIGNvbnRhaW5pbmcgbiBwb3NpdGl2ZSBpbnRlZ2VycyAoYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+KSwgZGVub3RpbmcgdGhlIHZvdGUtY291bnQgcmlnaHQgYWZ0ZXIgYWxsIGRvbWluYW50IHN0dWRlbnRzIGhhdmUgY2FzdCB0aGVpciB2b3RlLjxcL3A+XHJcblxyXG48cD5GdXJ0aGVybW9yZSwgaXQgaXMgZ3VhcmFudGVlZCB0aGF0Jm5ic3A7XFwoIGsgXFxnZSBcXHN1bV97aT0xfV57bn17YV9pfVxcKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgd3JpdGUgbiBsaW5lcyBvZiBvdXRwdXQgY29udGFpbmluZyB0aGUgcHJvYmFiaWxpdHkgdGhhdCB0aGUgaSZyc3F1bzt0aCBwdWIgd2lsbCBiZSBzZWxlY3RlZCAoMSAmbGU7IGkgJmxlOyBuKSwgb3JkZXJlZCBieSBhc2NlbmRpbmcgaS48XC9wPlxyXG5cclxuPHA+RWFjaCBsaW5lIHNoYWxsIGJlIG9mIHRoZSBmb3JtICZsc3F1bztwdWIgaTogcGVyY2VudGFnZSAlJnJzcXVvOywgd2hlcmUgcGVyY2VudGFnZSBpcyBhIFx1ZmIwMm9hdGluZyBwb2ludCBudW1iZXIgcm91bmRlZCB0byAyIGRpZ2l0cyBhZnRlciB0aGUgZGVjaW1hbCBwb2ludC48XC9wPlxyXG5cclxuPHA+QSBzcGFjZSBzaG91bGQgc2VwYXJhdGUgdGhlIHBlcmNlbnRhZ2UgbnVtYmVyIGFuZCB0aGUgc3Vic2VxdWVudCBwZXJjZW50IHNpZ24uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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