5216번
- 축구
스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 15 | 2 | 2 | 66.667% |
문제
2N명이 두 팀으로 나누어서 축구를 하고 있다. 각 플레이어는 자기 팀의 유니폼을 입고 있고, 등번호는 1번부터 N번까지이다.
각 플레이어는 자신의 정확도를 알고 있고, 패스를 할 수 있는 팀 동료의 집합 F와 자신의 공을 빼았을 수 있는 상대팀 선수의 집합 E를 알고 있다.
플레이어가 공을 소유하게 되면, 그 순간부터 1초동안 아래 세 가지 중 하나의 사건이 발생한다.
- F에 속해있는 동료 중 한 명에게 패스를 한다. (랜덤)
- E에 속해있는 상대팀 선수 중 한 명에게 공을 빼앗긴다. (랜덤)
- 골대를 향해서 슛을 쏜다.
플레이어가 골대를 향해서 슛을 쏠 때, 득점할 확률은 자신의 정확도와 같다. 슛을 쏜 이후에는 결과에 상관없이 상대편 1번 선수가 공을 소유하게 된다.
위의 각 사건이 발생할 확률은 |F| : |E| : 1이고, 이전에 일어났던 사건은 여기에 영향을 미치지 않는다. (|S|는 집합 S의 크기이다) 각 사건의 설명 중에 랜덤은 각 집합에 포함되는 한 선수를 선택할 확률이 모두 같다는 것을 의미한다. 선수가 공을 소유하고 있지 않는 시간은 무시할 수 있을 만큼 매우 작다.
경기는 첫 번째 팀의 1번 선수가 공을 소유하면서 시작한다. 경기는 R 골을 득점한 팀이 있거나, 경기가 시작한지 T초가 지나면 끝나게 된다. 가능한 모든 최종 스코어에 대해서, 그 스코어로 경기가 끝날 확률을 계산하는 프로그램을 작성하시오.
아래 그림은 예제를 그림으로 나타낸 것이다.
입력
첫째 줄에 N, R, T가 주어진다. (1 ≤ N ≤ 100, 1 ≤ R ≤ 10, 1 ≤ T ≤ 500)
다음 N개 줄에는 첫 번째 팀에 속하는 각 선수의 설명이 주어지며, 그 다음 N개 줄에는 두 번째 팀에 속하는 각 선수의 설명이 주어진다.
선수의 설명에서 첫 번째 숫자는 그 선수의 정확도 p이다. (0 ≤ p ≤ 1) 그 다음에는 두 양의 정수 집합 F의 크기 nF와 집합 E의 크기 nE가 주어진다. (0 ≤ nF ≤ N-1, 0 ≤ nE ≤ N) 다음 nF+nE개 숫자는 각각 집합 F와 E에 포함되는 선수의 번호가 순서대로 주어지며, 공백으로 구분되어져 있다. 집합 F에는 자기 자신 번호를 포함하지 않는다.
출력
이론상 가능한 최종 스코어는 R*(R+2)개이다. 각 스코어에 대해서 그 결과가 나올 확률을 한 줄에 하나씩 출력한다.
출력하는 순서는 첫 번째 팀의 점수가 증가하는 순서로, 같은 경우에는 두 번째 팀의 점수가 증가하는 순서로 출력한다.
확률의 오차는 0.000001까지 허용한다.
제한
예제 입력 1
1 1 2 0.5 0 1 1 0.5 0 1 1
예제 출력 1
0.56250 0.18750 0.25000
예제 입력 2
2 2 5 0.0 1 2 2 1 2 1.0 0 0 0.5 1 0 2 0.5 1 0 1
예제 출력 2
0.2578125 0.2812500 0.0703125 0.1718750 0.1640625 0.0234375 0.0156250 0.0156250
힌트
W3sicHJvYmxlbV9pZCI6IjUyMTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkOTVcdWFkNmMiLCJkZXNjcmlwdGlvbiI6IjxwPjJOXHViYTg1XHVjNzc0IFx1YjQ1MCBcdWQzMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA0XHVjNWI0XHVjMTFjIFx1Y2Q5NVx1YWQ2Y1x1Yjk3YyBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHViMjk0IFx1Yzc5MFx1YWUzMCBcdWQzMDBcdWM3NTggXHVjNzIwXHViMmM4XHVkM2ZjXHVjNzQ0IFx1Yzc4NVx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YjRmMVx1YmM4OFx1ZDYzOFx1YjI5NCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHVjNzkwXHVjMmUwXHVjNzU4IFx1YzgxNVx1ZDY1NVx1YjNjNFx1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHVhY2UwLCBcdWQzMjhcdWMyYTRcdWI5N2MgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkMzAwIFx1YjNkOVx1YjhjY1x1Yzc1OCBcdWM5ZDFcdWQ1NjkgRlx1YzY0MCBcdWM3OTBcdWMyZTBcdWM3NTggXHVhY2Y1XHVjNzQ0IFx1YmU3Y1x1YzU1OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzBjMVx1YjMwMFx1ZDMwMCBcdWMxMjBcdWMyMThcdWM3NTggXHVjOWQxXHVkNTY5IEVcdWI5N2MgXHVjNTRjXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YWNmNVx1Yzc0NCBcdWMxOGNcdWM3MjBcdWQ1NThcdWFjOGMgXHViNDE4XHViYTc0LCBcdWFkZjggXHVjMjFjXHVhYzA0XHViZDgwXHVkMTMwIDFcdWNkMDhcdWIzZDlcdWM1NDggXHVjNTQ0XHViNzk4IFx1YzEzOCBcdWFjMDBcdWM5YzAgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMwYWNcdWFjNzRcdWM3NzQgXHViYzFjXHVjMGRkXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkZcdWM1ZDAgXHVjMThkXHVkNTc0XHVjNzg4XHViMjk0IFx1YjNkOVx1YjhjYyBcdWM5MTEgXHVkNTVjIFx1YmE4NVx1YzVkMFx1YWM4YyBcdWQzMjhcdWMyYTRcdWI5N2MgXHVkNTVjXHViMmU0LiAoXHViNzljXHViMzY0KTxcL2xpPlxyXG5cdDxsaT5FXHVjNWQwIFx1YzE4ZFx1ZDU3NFx1Yzc4OFx1YjI5NCBcdWMwYzFcdWIzMDBcdWQzMDAgXHVjMTIwXHVjMjE4IFx1YzkxMSBcdWQ1NWMgXHViYTg1XHVjNWQwXHVhYzhjIFx1YWNmNVx1Yzc0NCBcdWJlN2NcdWM1NTdcdWFlMzRcdWIyZTQuIChcdWI3OWNcdWIzNjQpPFwvbGk+XHJcblx0PGxpPlx1YWNlOFx1YjMwMFx1Yjk3YyBcdWQ1YTVcdWQ1NzRcdWMxMWMgXHVjMjliXHVjNzQ0IFx1YzNkY1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVhY2U4XHViMzAwXHViOTdjIFx1ZDVhNVx1ZDU3NFx1YzExYyBcdWMyOWJcdWM3NDQgXHVjM2UwIFx1YjU0YywgXHViNGRkXHVjODEwXHVkNTYwIFx1ZDY1NVx1Yjk2MFx1Yzc0MCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjODE1XHVkNjU1XHViM2M0XHVjNjQwIFx1YWMxOVx1YjJlNC4gXHVjMjliXHVjNzQ0IFx1YzNkYyBcdWM3NzRcdWQ2YzRcdWM1ZDBcdWIyOTQgXHVhY2IwXHVhY2ZjXHVjNWQwIFx1YzBjMVx1YWQwMFx1YzVjNlx1Yzc3NCBcdWMwYzFcdWIzMDBcdWQzYjggMVx1YmM4OCBcdWMxMjBcdWMyMThcdWFjMDAgXHVhY2Y1XHVjNzQ0IFx1YzE4Y1x1YzcyMFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWFjMDEgXHVjMGFjXHVhYzc0XHVjNzc0IFx1YmMxY1x1YzBkZFx1ZDU2MCBcdWQ2NTVcdWI5NjBcdWM3NDAgfEZ8IDogfEV8IDogMVx1Yzc3NFx1YWNlMCwgXHVjNzc0XHVjODA0XHVjNWQwIFx1Yzc3Y1x1YzViNFx1YjBhY1x1YjM1OCBcdWMwYWNcdWFjNzRcdWM3NDAgXHVjNWVjXHVhZTMwXHVjNWQwIFx1YzYwMVx1ZDVhNVx1Yzc0NCBcdWJiZjhcdWNlNThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiAofFN8XHViMjk0IFx1YzlkMVx1ZDU2OSBTXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yzc3NFx1YjJlNCkgXHVhYzAxIFx1YzBhY1x1YWM3NFx1Yzc1OCBcdWMxMjRcdWJhODUgXHVjOTExXHVjNWQwIFx1Yjc5Y1x1YjM2NFx1Yzc0MCBcdWFjMDEgXHVjOWQxXHVkNTY5XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWQ1NWMgXHVjMTIwXHVjMjE4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWQ2NTVcdWI5NjBcdWM3NzQgXHViYWE4XHViNDUwIFx1YWMxOVx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWMxMjBcdWMyMThcdWFjMDAgXHVhY2Y1XHVjNzQ0IFx1YzE4Y1x1YzcyMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWJiMzRcdWMyZGNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWI5Y2NcdWQwN2MgXHViOWU0XHVjNmIwIFx1Yzc5MVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhY2JkXHVhZTMwXHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkMzAwXHVjNzU4IDFcdWJjODggXHVjMTIwXHVjMjE4XHVhYzAwIFx1YWNmNVx1Yzc0NCBcdWMxOGNcdWM3MjBcdWQ1NThcdWJhNzRcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWFjYmRcdWFlMzBcdWIyOTQgUiBcdWFjZThcdWM3NDQgXHViNGRkXHVjODEwXHVkNTVjIFx1ZDMwMFx1Yzc3NCBcdWM3ODhcdWFjNzBcdWIwOTgsIFx1YWNiZFx1YWUzMFx1YWMwMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWM5YzAgVFx1Y2QwOFx1YWMwMCBcdWM5YzBcdWIwOThcdWJhNzQgXHViMDVkXHViMDk4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVhYzAwXHViMmE1XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWNkNWNcdWM4ODUgXHVjMmE0XHVjZjU0XHVjNWI0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhZGY4IFx1YzJhNFx1Y2Y1NFx1YzViNFx1Yjg1YyBcdWFjYmRcdWFlMzBcdWFjMDAgXHViMDVkXHViMGEwIFx1ZDY1NVx1Yjk2MFx1Yzc0NCBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWM2MDhcdWM4MWNcdWI5N2MgXHVhZGY4XHViOWJjXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZWNjZWIxNDktYTUxZS00NTEyLWFmMjMtODU1NDU3NWM2MjI1XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA0NjFweDsgaGVpZ2h0OiAxODlweDtcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTiwgUiwgVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCwgMSAmbGU7IFIgJmxlOyAxMCwgMSAmbGU7IFQgJmxlOyA1MDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDMwMFx1YzVkMCBcdWMxOGRcdWQ1NThcdWIyOTQgXHVhYzAxIFx1YzEyMFx1YzIxOFx1Yzc1OCBcdWMxMjRcdWJhODVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWFkZjggXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVkMzAwXHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWFjMDEgXHVjMTIwXHVjMjE4XHVjNzU4IFx1YzEyNFx1YmE4NVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEyMFx1YzIxOFx1Yzc1OCBcdWMxMjRcdWJhODVcdWM1ZDBcdWMxMWMgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVhZGY4IFx1YzEyMFx1YzIxOFx1Yzc1OCBcdWM4MTVcdWQ2NTVcdWIzYzQgcFx1Yzc3NFx1YjJlNC4gKDAgJmxlOyBwICZsZTsgMSkgXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkMFx1YjI5NCBcdWI0NTAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBcdWM5ZDFcdWQ1NjkgRlx1Yzc1OCBcdWQwNmNcdWFlMzAgbkZcdWM2NDAgXHVjOWQxXHVkNTY5IEVcdWM3NTggXHVkMDZjXHVhZTMwIG5FXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBuRiAmbGU7IE4tMSwgMCAmbGU7IG5FICZsZTsgTikgXHViMmU0XHVjNzRjIG5GK25FXHVhYzFjIFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWFjMDFcdWFjMDEgXHVjOWQxXHVkNTY5IEZcdWM2NDAgRVx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHVjMTIwXHVjMjE4XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjOWQxXHVkNTY5IEZcdWM1ZDBcdWIyOTQgXHVjNzkwXHVhZTMwIFx1Yzc5MFx1YzJlMCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM3NzRcdWI4NjBcdWMwYzEgXHVhYzAwXHViMmE1XHVkNTVjIFx1Y2Q1Y1x1Yzg4NSBcdWMyYTRcdWNmNTRcdWM1YjRcdWIyOTQgUiooUisyKVx1YWMxY1x1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YzJhNFx1Y2Y1NFx1YzViNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHVhZGY4IFx1YWNiMFx1YWNmY1x1YWMwMCBcdWIwOThcdWM2MmMgXHVkNjU1XHViOTYwXHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1YjI5NCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1ZDMwMFx1Yzc1OCBcdWM4MTBcdWMyMThcdWFjMDAgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1Yjg1YywgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1ZDMwMFx1Yzc1OCBcdWM4MTBcdWMyMThcdWFjMDAgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDY1NVx1Yjk2MFx1Yzc1OCBcdWM2MjRcdWNjMjhcdWIyOTQgMC4wMDAwMDFcdWFlNGNcdWM5YzAgXHVkNWM4XHVjNmE5XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjUyMTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNTk9HT01FVCIsImRlc2NyaXB0aW9uIjoiPHA+Mk4gcGVvcGxlIGFyZSBwbGF5aW5nIGZvb3RiYWxsIChzb2NjZXIpLCBkaXZpZGVkIGludG8gdHdvIHRlYW1zLiBFYWNoIHBsYXllciB3ZWFycyBhIGRyZXNzIHdpdGggdGhlIHRlYW0gbG9nbyBhbmQgYSB1bmlxdWUgKGluIHRoZSB0ZWFtKSBwb3NpdGl2ZSBpbnRlZ2VyIGJldHdlZW4gMSBhbmQgTiwgaW5jbHVzaXZlLiBGb3IgZWFjaCBwbGF5ZXIsIHdlIGtub3cgaGlzIHByZWNpc2lvbiwgdGhlIHNldCBvZiB0ZWFtbWF0ZXMgd2hvbSBoZSBjYW4gcGFzcyB0aGUgYmFsbCB0byAoRikgYW5kIHRoZSBzZXQgb2Ygb3Bwb25lbnRzIHdobyBjYW4gdGFrZSB0aGUgYmFsbCBmcm9tIGhpbSAoRSkuIFdoZW4gYSBwbGF5ZXIgY29tZXMgaW50byBwb3NzZXNzaW9uIG9mIHRoZSBiYWxsLCBhZnRlciBleGFjdGx5IG9uZSBzZWNvbmQgb25lIG9mIHRoZSBmb2xsb3dpbmcgZXZlbnRzIHdpbGwgaGFwcGVuOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnRoZSBwbGF5ZXIgcGFzc2VzIHRoZSBiYWxsIHRvIGEgcmFuZG9tIHRlYW1tYXRlIGZyb20gdGhlIHNldCBGLDxcL2xpPlxyXG5cdDxsaT5hIHJhbmRvbSBvcHBvbmVudCBmcm9tIHRoZSBzZXQgRSB0YWtlcyB0aGUgYmFsbCBmcm9tIGhpbSw8XC9saT5cclxuXHQ8bGk+dGhlIHBsYXllciBhdHRlbXB0cyBhIHNob3QgYXQgdGhlIGdvYWwuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SWYgdGhlIHBsYXllciBhdHRlbXB0cyBhIHNob3QsIHRoZSBwcm9iYWJpbGl0eSBvZiBzY29yaW5nIGEgZ29hbCBpcyBlcXVhbCB0byBoaXMgcHJlY2lzaW9uLiBBZnRlciB0aGUgc2hvdCwgd2hldGhlciBpdCB3YXMgc3VjY2Vzc2Z1bCBvciBub3QsIHRoZSBiYWxsIGlzIGF3YXJkZWQgdG8gdGhlIHBsYXllciBudW1iZXIgMSBmcm9tIHRoZSBvcHBvc2luZyB0ZWFtLjxcL3A+XHJcblxyXG48cD5UaGUgcHJvYmFiaWxpdGllcyBvZiBkaWZmZXJlbnQgZXZlbnRzIGFyZSBpbiB0aGUgcHJvcG9ydGlvbiB8RnwgOiB8RXwgOiAxLCBpbiBvcmRlciwgYW5kIGRlcGVuZCBvbmx5IG9uIHRoZSBwbGF5ZXIgY3VycmVudGx5IGluIHBvc3Nlc3Npb24gb2YgdGhlIGJhbGwgKHxTfCBkZXRlcm1pbmVzIHRoZSBzaXplIG9mIHRoZSBzZXQgUyBjb3JyZXNwb25kaW5nIHRvIHRoZSBjdXJyZW50IHBsYXllciksIG5vdCBvbiBhbnkgcHJldmlvdXMgZXZlbnRzIGluIHRoZSBnYW1lLiBUaGUgd29yZCAmbGRxdW87cmFuZG9tJnJkcXVvOyBtZWFucyB0aGF0IGFsbCBwbGF5ZXJzIGZyb20gdGhlIHNldCBGIChvciBFKSBoYXZlIHRoZSBzYW1lIHByb2JhYmlsaXR5IG9mIGJlaW5nIHBhc3NlZCAob3IgdGFraW5nKSB0aGUgYmFsbCBieSAoZnJvbSkgdGhlIHBsYXllciB0aGF0IGlzIGN1cnJlbnRseSBpbiB0aGUgYmFsbCYjMzk7cyBwb3NzZXNzaW9uLiBUaGUgdGltZSB0aGF0IGEgYmFsbCBzcGVuZHMgb3V0c2lkZSBvZiBhIHBsYXllciYjMzk7cyBwb3NzZXNzaW9uIGlzIG5lZ2xpZ2libGUuPFwvcD5cclxuXHJcbjxwPlRoZSBtYXRjaCBiZWdpbnMgd2l0aCBwbGF5ZXIgMSBmcm9tIHRoZSBmaXJzdCB0ZWFtIGluIHBvc3Nlc3Npb24gb2YgdGhlIGJhbGwgYW5kIGVuZHMgZWl0aGVyIHdoZW4gb25lIHRlYW0gaGFzIHNjb3JlZCBSIGdvYWxzIG9yIHdoZW4gVCBzZWNvbmRzIGhhdmUgZWxhcHNlZCwgd2hpY2hldmVyIGhhcHBlbnMgZmlyc3QuIEZvciBlYWNoIHBvc3NpYmxlIGZpbmFsIHNjb3JlLCBkZXRlcm1pbmUgdGhlIHByb2JhYmlsaXR5IHRoYXQgdGhlIG1hdGNoIHdpbGwgZW5kIHdpdGggaXQuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgaW1hZ2UgaWxsdXN0cmF0ZXMgdGhlIHBsYXllciBhcnJhbmdlbWVudCBmb3IgdGhlIHNlY29uZCB0ZXN0IGV4YW1wbGU6PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZWNjZWIxNDktYTUxZS00NTEyLWFmMjMtODU1NDU3NWM2MjI1XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA0NjFweDsgaGVpZ2h0OiAxODlweDtcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRocmVlIHBvc2l0aXZlIGludGVnZXJzOiBOICgxICZsZTsgTiAmbGU7IDEwMCksIHRoZSBudW1iZXIgb2YgcGxheWVycyBpbiBlYWNoIHRlYW0sIFIgKDEgJmxlOyBSICZsZTsgMTApLCB0aGUgbnVtYmVyIG9mIGdvYWxzIG5lZWRlZCBmb3IgdmljdG9yeSwgYW5kIFQgKDEgJmxlOyBUICZsZTsgNTAwKSwgdGhlIG1heGltdW0gZHVyYXRpb24gb2YgdGhlIG1hdGNoLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbiBkZXNjcmlwdGlvbnMgb2YgdGhlIGZpcnN0IHRlYW0mIzM5O3MgcGxheWVycywgb25lIHBlciBsaW5lLCB3aGlsZSB0aGUgbmV4dCBOIGxpbmVzIGFmdGVyIHRoYXQgY29udGFpbiBkZXNjcmlwdGlvbnMgb2YgdGhlIHNlY29uZCB0ZWFtJiMzOTtzIHBsYXllcnMuIEEgZGVzY3JpcHRpb24gb2YgYSBzaW5nbGUgcGxheWVyIGNvbnNpc3RzIG9mIGEgcmVhbCBudW1iZXIgcCAoMCAmbGU7IHAgJmxlOyAxKSwgdGhlIHBsYXllciYjMzk7cyBwcmVjaXNpb24sIGZvbGxvd2VkIGJ5IHR3byBwb3NpdGl2ZSBpbnRlZ2VycywgbkYgKDAgJmxlOyBuRiAmbGU7IE4gLSAxKSBhbmQgbkUgKDAgJmxlOyBuRSAmbGU7IE4pLCB0aGUgc2l6ZXMgb2YgdGhlIHNldHMgRiBhbmQgRSwgcmVzcGVjdGl2ZWx5LCBmb2xsb3dlZCBieSBuRiArIG5FIHBsYXllciBsYWJlbHMgcmVwcmVzZW50aW5nIHRoZSBzZXRzIEYgYW5kIEUgdGhlbXNlbHZlcyAoaW4gdGhhdCBvcmRlciksIGFsbCBzcGFjZS1zZXBhcmF0ZWQuIE5vdGUgdGhhdCB0aGUgbGFiZWxzIGZyb20gRiByZXByZXNlbnQgcGxheWVycyBmcm9tIG9uZSB0ZWFtLCBhbmQgbGFiZWxzIGZyb20gRSB0aGUgb3RoZXIgdGVhbS4gVGhlIHNldCBGIHdpbGwgbm90IGNvbnRhaW4gdGhlIGxhYmVsIG9mIHRoZSBwbGF5ZXIgY3VycmVudGx5IGJlaW5nIGRlc2NyaWJlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgbWF0Y2ggY2FuIHRoZW9yZXRpY2FsbHkgZW5kIHdpdGggb25lIG9mIFIgKiAoUiArIDIpIGRpZmZlcmVudCBmaW5hbCByZXN1bHRzLiBGb3IgZWFjaCByZXN1bHQsIG91dHB1dCB0aGUgcHJvYmFiaWxpdHkgb2YgaXRzIHJlYWxpemF0aW9uIGFzIGEgcmVhbCBudW1iZXIsIG9uZSBwZXIgbGluZS4gT3JkZXIgdGhlIHJlc3VsdHMgZmlyc3QgYnkgdGhlIG51bWJlciBvZiBnb2FscyBzY29yZWQgYnkgdGhlIGZpcnN0IHRlYW0sIHRoZW4gYnkgdGhlIG51bWJlciBvZiBnb2FzIHNjb3JlZCBieSB0aGUgc2Vjb25kIHRlYW0sIGluIGFzY2VuZGluZyBvcmRlci4gVGhlIHBlcm1pdHRlZCBkaWZmZXJlbmNlIGZyb20gdGhlIGV4YWN0IHZhbHVlIGZvciBlYWNoIHByb2JhYmlsaXR5IGlzIDAuMDAwMDAxLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5DbGFyaWZpY2F0aW9uIG9mIHRoZSBmaXJzdCBleGFtcGxlOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzYyZjA3NmVjLTcwOWQtNDBiNC1iMGE1LTk3MmM2N2Q5ZjVjMlwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMjY4cHg7IGhlaWdodDogMTU2cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBzdGFyIGRlbm90ZXMgdGhlIHBsYXllciBpbiBwb3NzZXNzaW9uIG9mIHRoZSBiYWxsIGluIHRoZSBiZWdpbm5pbmcuIFRoZSBtYXRjaCBsYXN0cyBmb3Igb25seSBUID0gMiBtb3ZlcyBvciB1bnRpbCBzb21lb25lIHNjb3JlcyBSID0gMSBnb2FsLiBTaW5jZSBOID0gMSwgdGhlcmUgYXJlIG9ubHkgdHdvIHBsYXllcnMgaW4gdGhlIG1hdGNoLCBwbGF5aW5nIG9uZSBhZ2FpbnN0IHRoZSBvdGhlci4gQm90aCBwbGF5ZXJzIGhhdmUgdGhlIHByZWNpc2lvbiBvZiAwLjUsIHdoaWNoIG1lYW5zIHRoYXQgZWFjaCBoYXMgYSA1MCUgY2hhbmNlIG9mIHNjb3JpbmcgYSBnb2FsIHdoZW4gdHJ5aW5nIHRvIHNob290LCBhZnRlciB3aGljaCB0aGUgYmFsbCBpcyBhd2FyZGVkIHRvIHRoZSBvcHBvbmVudC48XC9wPlxyXG5cclxuPHA+TGV0IHVzIGxhYmVsIHRoZSBncmV5IHBsYXllciBhcyBBLCBhbmQgdGhlIHdoaXRlIHBsYXllciBhcyBCLiBVbmRlciB0aGVzZSBhc3N1bXB0aW9ucywgdGhlcmUgYXJlIG9ubHkgNiBwb3NzaWJsZSBtYXRjaGVzLiBFYWNoIG9mIHRoZW0gaXMgZGVzY3JpYmVkIGluIHRoZSB0YWJsZSBiZWxvdywgd2l0aCB0aGUgY29ycmVzcG9uZGluZyBwcm9iYWJpbGl0eSwgZGVzY3JpcHRpb24gYW5kIG91dGNvbWU6PFwvcD5cclxuXHJcbjx0YWJsZSBjbGFzcz1cInRhYmxlIHRhYmxlLWJvcmRlcmVkXCI+XHJcblx0PHRib2R5PlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MC4yNTxcL3RkPlxyXG5cdFx0XHQ8dGQ+QSBkZWNpZGVzIHRvIHNob290IGFuZCBzY29yZXMhPFwvdGQ+XHJcblx0XHRcdDx0ZD4xOjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MC4yNSAqIDAuMjU8XC90ZD5cclxuXHRcdFx0PHRkPkEgZGVjaWRlcyB0byBzaG9vdCwgYnV0IG1pc3Nlcy4gQiBkZWNpZGVzIHRvIHNob290IGFuZCBzY29yZXMhPFwvdGQ+XHJcblx0XHRcdDx0ZD4wOjE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MC4yNSAqIDAuMjU8XC90ZD5cclxuXHRcdFx0PHRkPkEgZGVjaWRlcyB0byBzaG9vdCwgYnV0IG1pc3Nlcy4gQiBkZWNpZGVzIHRvIHNob290LCBidXQgYWxzbyBtaXNzZXMuPFwvdGQ+XHJcblx0XHRcdDx0ZD4wOjA8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MC41MCAqIDAuMjU8XC90ZD5cclxuXHRcdFx0PHRkPkEgbG9zZXMgdGhlIGJhbGwgdG8gQi4gQiBkZWNpZGVzIHRvIHNob290IGFuZCBzY29yZXMhPFwvdGQ+XHJcblx0XHRcdDx0ZD4wOjE8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MC41MCAqIDAuNTA8XC90ZD5cclxuXHRcdFx0PHRkPkEgbG9zZXMgdGhlIGJhbGwgdG8gQi4gQiBsb3NlcyB0aGUgYmFsbCB0byBBLjxcL3RkPlxyXG5cdFx0XHQ8dGQ+MDowPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjAuNTAgKiAwLjI1PFwvdGQ+XHJcblx0XHRcdDx0ZD5BIGxvc2VzIHRoZSBiYWxsIHRvIEIuIEIgZGVjaWRlcyB0byBzaG9vdCwgYnV0IG1pc3Nlcy48XC90ZD5cclxuXHRcdFx0PHRkPjA6MDxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0PFwvdGJvZHk+XHJcbjxcL3RhYmxlPlxyXG5cclxuPHA+Qnkgc3VtbWluZyBwcm9iYWJpbGl0aWVzIGZvciBwYXJ0aWN1bGFyIGZpbmFsIHJlc3VsdHMsIHdlIG9idGFpbiB0aGUgZm9sbG93aW5nIHNvbHV0aW9uOjxcL3A+XHJcblxyXG48dGFibGUgY2xhc3M9XCJ0YWJsZSB0YWJsZS1ib3JkZXJlZFwiPlxyXG5cdDx0Ym9keT5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPjA6MDxcL3RkPlxyXG5cdFx0XHQ8dGQ+MC4yNSAqIDAuMjUgKyAwLjUgKiAwLjUgKyAwLjUgKiAwLjI1PFwvdGQ+XHJcblx0XHRcdDx0ZD4wLjU2MjU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+MDoxPFwvdGQ+XHJcblx0XHRcdDx0ZD4wLjI1ICogMC4yNSArIDAuNSAqIDAuMjU8XC90ZD5cclxuXHRcdFx0PHRkPjAuMTc3NTxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD4xOjA8XC90ZD5cclxuXHRcdFx0PHRkPjAuMjU8XC90ZD5cclxuXHRcdFx0PHRkPjAuMjU8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdDxcL3Rib2R5PlxyXG48XC90YWJsZT5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d
출처
Contest > Croatian Open Competition in Informatics > COCI 2012/2013 > Contest #5 6번
- 문제를 번역한 사람: baekjoon
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호