시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 64 5 3 13.636%

문제

N명의 카우보이가 있다. 그런데 1번 카우보이부터 N번 카우보이까지 차례로 총을 쏴 다른 사람을 맞추려 한다. (N번 사람이 총을 쏜 후에는 1번 사람이 총을 쏘게 될 것이다.) 총을 맞은 사람은 죽게 되어서 더 이상 총을 쏘지 못하게 된다. 이렇게 계속 반복을 하다가 1명이 남게 되면 그 사람이 승자가 된다고 한다.

그런데 N명의 사람들은 모두 총을 쏠 수 있는 능력이 다르기 때문에 총을 쏴서 다른 사람을 맞힐 수 있는 확률이 다르다. 그렇기 때문에 N명의 카우보이는 모두 이러한 확률을 이용하여서 자기가 이길 수 있는 전략을 짜서 자신이 총을 겨눌 사람을 정하게 된다. 쏘아서 자신의 생존 확률이 가장 커지는 상대가 여러 명일 때,  그 중 무작위로한 명을 쏜다.

N명의 사람들의 총을 쏘는 능력이 주어져 있을 때, 각각의 사람이 최후의 1인이 되는 확률을 구하는 프로그램을 작성하시오.

카우보이들은 투철한 직업관을 가지고 있기 때문에, 허공에 총을 쏠 때 자신의 생존 확률이 가장 높은 경우라도, 항상 다른 사람을 맞추기 위해 최선을 다할 것이다.

입력

첫째 줄에 카우보이의 숫자 N(2 ≤ N ≤ 13)이 주어지고 두 번째 줄에는 N개의 정수 Pi (1 ≤ Pi ≤ 100)가 주어진다. Pi는 i번째 사람이 총을 쏴서 다른 사람을 맞추는 확률을 의미한다.

출력

첫째 줄에 N개의 소수 Qi 를 출력한다 Qi는 i번째 사람이 최후의 1인이 될 확률을 의미한다. 절대/상대 오차는 10-2까지 허용한다.

예제 입력 1

2
1 100

예제 출력 1

1.00 99.00

예제 입력 2

3
100 99 98

예제 출력 2

2.00 0.00 98.00

예제 입력 3

3
50 99 100

예제 출력 3

25.38 74.37 0.25

예제 입력 4

3
50 99 99

예제 출력 4

25.38 49.50 25.12

예제 입력 5

3
50 99 98

예제 출력 5

25.63 24.63 49.74
W3sicHJvYmxlbV9pZCI6IjE4MzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlNzRcdWM2YjBcdWJjZjRcdWM3NzQiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWJhODVcdWM3NTggXHVjZTc0XHVjNmIwXHViY2Y0XHVjNzc0XHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIDFcdWJjODggXHVjZTc0XHVjNmIwXHViY2Y0XHVjNzc0XHViZDgwXHVkMTMwIE5cdWJjODggXHVjZTc0XHVjNmIwXHViY2Y0XHVjNzc0XHVhZTRjXHVjOWMwIFx1Y2MyOFx1Yjg0MFx1Yjg1YyBcdWNkMWRcdWM3NDQgXHVjM2Y0IFx1YjJlNFx1Yjk3OCBcdWMwYWNcdWI3OGNcdWM3NDQgXHViOWRlXHVjZDk0XHViODI0IFx1ZDU1Y1x1YjJlNC4gKE5cdWJjODggXHVjMGFjXHViNzhjXHVjNzc0IFx1Y2QxZFx1Yzc0NCBcdWMzZGMgXHVkNmM0XHVjNWQwXHViMjk0IDFcdWJjODggXHVjMGFjXHViNzhjXHVjNzc0IFx1Y2QxZFx1Yzc0NCBcdWMzZDhcdWFjOGMgXHViNDIwIFx1YWM4M1x1Yzc3NFx1YjJlNC4pIFx1Y2QxZFx1Yzc0NCBcdWI5ZGVcdWM3NDAgXHVjMGFjXHViNzhjXHVjNzQwIFx1YzhmZFx1YWM4YyBcdWI0MThcdWM1YjRcdWMxMWMgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWNkMWRcdWM3NDQgXHVjM2Q4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWFjYzRcdWMxOGQgXHViYzE4XHViY2Y1XHVjNzQ0IFx1ZDU1OFx1YjJlNFx1YWMwMCAxXHViYTg1XHVjNzc0IFx1YjBhOFx1YWM4YyBcdWI0MThcdWJhNzQgXHVhZGY4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWMyYjlcdWM3OTBcdWFjMDAgXHViNDFjXHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViN2YwXHViMzcwIE5cdWJhODVcdWM3NTggXHVjMGFjXHViNzhjXHViNGU0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWNkMWRcdWM3NDQgXHVjM2UwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMmE1XHViODI1XHVjNzc0IFx1YjJlNFx1Yjk3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjZDFkXHVjNzQ0IFx1YzNmNFx1YzExYyBcdWIyZTRcdWI5NzggXHVjMGFjXHViNzhjXHVjNzQ0IFx1YjlkZVx1ZDc5MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDY1NVx1Yjk2MFx1Yzc3NCBcdWIyZTRcdWI5NzRcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgTlx1YmE4NVx1Yzc1OCBcdWNlNzRcdWM2YjBcdWJjZjRcdWM3NzRcdWIyOTQgXHViYWE4XHViNDUwIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWQ2NTVcdWI5NjBcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjXHVjMTFjIFx1Yzc5MFx1YWUzMFx1YWMwMCBcdWM3NzRcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM4MDRcdWI3YjVcdWM3NDQgXHVjOWRjXHVjMTFjIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWNkMWRcdWM3NDQgXHVhY2E4XHViMjBjIFx1YzBhY1x1Yjc4Y1x1Yzc0NCBcdWM4MTVcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LiZuYnNwO1x1YzNkOFx1YzU0NFx1YzExYyBcdWM3OTBcdWMyZTBcdWM3NTggXHVjMGRkXHVjODc0IFx1ZDY1NVx1Yjk2MFx1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjZWU0XHVjOWMwXHViMjk0IFx1YzBjMVx1YjMwMFx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHViYTg1XHVjNzdjIFx1YjU0YywgJm5ic3A7XHVhZGY4IFx1YzkxMSBcdWJiMzRcdWM3OTFcdWM3MDRcdWI4NWNcdWQ1NWMgXHViYTg1XHVjNzQ0IFx1YzNkY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+Tlx1YmE4NVx1Yzc1OCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NTggXHVjZDFkXHVjNzQ0IFx1YzNkOFx1YjI5NCBcdWIyYTVcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODM4IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjZDVjXHVkNmM0XHVjNzU4IDFcdWM3NzhcdWM3NzQgXHViNDE4XHViMjk0IFx1ZDY1NVx1Yjk2MFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHVjZTc0XHVjNmIwXHViY2Y0XHVjNzc0XHViNGU0XHVjNzQwIFx1ZDIyY1x1Y2NhMFx1ZDU1YyBcdWM5YzFcdWM1YzVcdWFkMDBcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1ZDVjOFx1YWNmNVx1YzVkMCBcdWNkMWRcdWM3NDQgXHVjM2UwIFx1YjU0YyBcdWM3OTBcdWMyZTBcdWM3NTggXHVjMGRkXHVjODc0IFx1ZDY1NVx1Yjk2MFx1Yzc3NCBcdWFjMDBcdWM3YTUgXHViMTkyXHVjNzQwIFx1YWNiZFx1YzZiMFx1Yjc3Y1x1YjNjNCwgXHVkNTZkXHVjMGMxIFx1YjJlNFx1Yjk3OCBcdWMwYWNcdWI3OGNcdWM3NDQgXHViOWRlXHVjZDk0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWNkNWNcdWMxMjBcdWM3NDQgXHViMmU0XHVkNTYwIFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZTc0XHVjNmIwXHViY2Y0XHVjNzc0XHVjNzU4IFx1YzIyYlx1Yzc5MCBOKDIgJmxlOyBOICZsZTsgMTMpXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBQPHN1Yj5pPFwvc3ViPiZuYnNwOygxICZsZTsgUDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gUDxzdWI+aTxcL3N1Yj5cdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjZDFkXHVjNzQ0IFx1YzNmNFx1YzExYyBcdWIyZTRcdWI5NzggXHVjMGFjXHViNzhjXHVjNzQ0IFx1YjlkZVx1Y2Q5NFx1YjI5NCBcdWQ2NTVcdWI5NjBcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWMxY1x1Yzc1OCBcdWMxOGNcdWMyMTggUTxzdWI+aTxcL3N1Yj4gXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNCBRPHN1Yj5pPFwvc3ViPlx1YjI5NCBpXHViYzg4XHVjOWY4IFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWNkNWNcdWQ2YzRcdWM3NTggMVx1Yzc3OFx1Yzc3NCBcdWI0MjAgXHVkNjU1XHViOTYwXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4gXHVjODA4XHViMzAwXC9cdWMwYzFcdWIzMDAgXHVjNjI0XHVjYzI4XHViMjk0IDEwPHN1cD4tMjxcL3N1cD5cdWFlNGNcdWM5YzAgXHVkNWM4XHVjNmE5XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE4MzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTaG9vdC1vdXQiLCJkZXNjcmlwdGlvbiI6IjxwPlRoaXMgaXMgYmFjayBpbiB0aGUgV2lsZCBXZXN0IHdoZXJlIGV2ZXJ5Ym9keSBpcyBcdWZiMDFnaHRpbmcgZXZlcnlib2R5LiBJbiBwYXJ0aWN1bGFyLCB0aGVyZSBhcmUgbiBjb3dib3lzLCBlYWNoIHdpdGggYSByZXZvbHZlci4gVGhlc2UgYXJlIHJhdGhlciBjaXZpbGl6ZWQgY293Ym95cywgc28gdGhleSBoYXZlIGRlY2lkZWQgdG8gdGFrZSB0dXJucyBcdWZiMDFyaW5nIHRoZWlyIGd1bnMgdW50aWwgb25seSBvbmUgaXMgbGVmdCBzdGFuZGluZy4gRWFjaCBvZiB0aGVtIGhhcyBhIGdpdmVuIHByb2JhYmlsaXR5IG9mIGhpdHRpbmcgaGlzIHRhcmdldCwgYW5kIHRoZXkgYWxsIGtub3cgZWFjaCBvdGhlciZyc3F1bztzIHByb2JhYmlsaXR5LiBGdXJ0aGVybW9yZSwgdGhleSBhcmUgZ2VuaXVzZXMgYW5kIGFsd2F5cyBrbm93IHdoaWNoIHBlcnNvbiB0byBhaW0gYXQgaW4gb3JkZXIgdG8gbWF4aW1pemUgdGhlaXIgd2lubmluZyBjaGFuY2UsIHNvIHRoZXkgYXJlIGluZGVlZCBwZWN1bGlhciBjb3dib3lzLiBJZiB0aGVyZSBhcmUgc2V2ZXJhbCBlcXVhbGx5IGdvb2QgdGFyZ2V0cywgb25lIG9mIHRob3NlIHdpbGwgYmUgY2hvc2VuIGF0IHJhbmRvbS4gTm90ZSB0aGF0IGEgY293Ym95JnJzcXVvO3MgY29kZSBvZiBldGhpY3MgZm9yY2VzIGhpbSB0byBkbyBoaXMgYmVzdCBhdCBraWxsaW5nIG9uZSBvZiBoaXMgb3Bwb25lbnRzLCBldmVuIGlmIGludGVudGlvbmFsbHkgbWlzc2luZyB3b3VsZCBoYXZlIGluY3JlYXNlZCBoaXMgb2RkcyAoeWVzLCB0aGlzIGNhbiBoYXBwZW4hKTxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBpcyBhIHNpbmdsZSBwb3NpdGl2ZSBpbnRlZ2VyIHQsIHRlbGxpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRvIGZvbGxvdy4gRWFjaCBjYXNlIGNvbnNpc3RzIG9mIG9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciAyICZsZTsgbiAmbGU7IDEzIGdpdmluZyB0aGUgbnVtYmVyIG9mIGNvd2JveXMsIGZvbGxvd2VkIGJ5IG4gcG9zaXRpdmUgaW50ZWdlcnMgZ2l2aW5nIGhpdCBwZXJjZW50YWdlcyBmb3IgdGhlIGNvd2JveXMgaW4gdGhlIG9yZGVyIG9mIHRoZWlyIHR1cm5zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IG9uZSBsaW5lIHdpdGggdGhlIHBlcmNlbnQgcHJvYmFiaWxpdGllcyBmb3IgZWFjaCBvZiB0aGVtIHN1cnZpdmluZywgaW4gdGhlIHNhbWUgb3JkZXIgYXMgdGhlIGlucHV0LiBUaGUgbnVtYmVycyBzaG91bGQgYmUgc2VwYXJhdGVkIGJ5IGEgc3BhY2UgYW5kIGJlIGNvcnJlY3RseSByb3VuZGVkIHRvIHR3byBkZWNpbWFsIHBsYWNlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2006 A번