3641번 - 호프집 선택 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 127 | 11 | 9 | 12.857% |
문제
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 %
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2012 B번
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호