This repository has been archived by the owner on Apr 22, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path1038.html
123 lines (122 loc) · 10.4 KB
/
1038.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
<meta content="text/html; charset=utf-8" http-equiv="Content-Type" />
<meta content="Word.Document" name="ProgId" />
<meta content="Microsoft Word 11" name="Generator" />
<meta content="Microsoft Word 11" name="Originator" />
<link href="file:///C:\DOCUME~1\DEFEND~1\LOCALS~1\Temp\msohtml1\01\clip_filelist.xml" rel="File-List" />
<title></title>
<!--[if gte mso 9]><xml>
<o:DocumentProperties>
<o:Author>Lovro Puzar</o:Author>
<o:Version>11.9999</o:Version>
</o:DocumentProperties>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:PunctuationKerning />
<w:ValidateAgainstSchemas />
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:Compatibility>
<w:BreakWrappedTables />
<w:SnapToGridInCell />
<w:ApplyBreakingRules />
<w:WrapTextWithPunct />
<w:UseAsianBreakRules />
<w:DontGrowAutofit />
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
</w:WordDocument>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" LatentStyleCount="156">
</w:LatentStyles>
</xml><![endif]--><style type="text/css">
<!--
/* Font Definitions */
@font-face
{font-family:"Angsana New";
panose-1:2 2 6 3 5 4 5 2 3 4;
mso-font-charset:0;
mso-generic-font-family:roman;
mso-font-pitch:variable;
mso-font-signature:16777219 0 0 0 65537 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{mso-style-parent:"";
margin:0cm;
margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:12.0pt;
mso-bidi-font-size:14.0pt;
font-family:"Times New Roman";
mso-fareast-font-family:"Times New Roman";
mso-bidi-font-family:"Angsana New";}
@page Section1
{size:612.0pt 792.0pt;
margin:72.0pt 90.0pt 72.0pt 90.0pt;
mso-header-margin:36.0pt;
mso-footer-margin:36.0pt;
mso-paper-source:0;}
div.Section1
{page:Section1;}
-->
</style><!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:"Table Normal";
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman";
mso-ansi-language:#0400;
mso-fareast-language:#0400;
mso-bidi-language:#0400;}
</style>
<![endif]-->
<p class="MsoNormal"><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ทุกคนคงจะรู้จักสายลับศูนย์ศูนย์เจ็ด เจมส์ บอนด์ ผู้โด่งดัง แต่ก็ยังไม่มีคนทราบว่าความจริงแล้ว เขาไม่ได้ปฏิบัติภารกิจส่วนใหญ่ด้วยตัวเขาเอง แต่เป็นลูกพี่ลูกน้องของเขา จิมมี่ บอนด์ ต่างหาก ส่วนเจมส์บอนด์จะเป็นคนกำหนดลำดับภารกิจสำหรับจิมมี่ ทุกครั้งที่มีภารกิจใหม่เข้ามา ดังนั้นเขาจึงต้องการให้คุณช่วย</span></p>
<p class="MsoNormal"><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ทุกเดือนจะมีรายการของภารกิจเข้ามา ด้วยความอัจฉริยะและประสบการณ์ของเจมส์ เขาสามารถคาดคะเนความน่าจะเป็นที่จิมมี่จะปฏิบัติภารกิจนั้นๆ สำเร็จได้ เมื่อเขาลงมือปฏิบัติภารกิจนั้นเป็นลำดับที่ต่างๆกันไป (ภารกิจหนึ่งอาจจะมีความน่าจะเป็นไม่เท่ากัน เมื่อเลือกทำเป็นลำดับแรก หรือ ลำดับที่สอง หรือ ลำดับที่สาม</span> …<span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">)<o:p></o:p></span></p>
<p class="MsoNormal"><b><u><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">โจทย์</span><o:p></o:p></u></b></p>
<p class="MsoNormal"><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">จงเขียนโปรแกรมที่รับจำนวนภารกิจและความน่าจะเป็นของความสำเร็จของภารกิจต่างๆ และหาว่าความน่าจะเป็น<b>สูงสุด</b>ที่จิมมี่จะปฏิบัติภารกิจ<b>ทุกภารกิจ</b>สำเร็จเป็นเท่าใด โดยที่ความน่าจะเป็นที่จะปฏิบัติภารกิจทุกภารกิจสำเร็จคือผลคูณของความน่าจะเป็นของทุกภารกิจที่ปฏิบัติ</span></p>
<p class="MsoNormal"><b><u><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ข้อมูลนำเข้า</span><o:p></o:p></u></b></p>
<p class="MsoNormal"><b><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">บรรทัดแรก</span></b><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";"> เป็นจำนวนเต็ม</span> N (1 ≤ N ≤ 20) <span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">คือจำนวนภารกิตที่ได้รับมอบหมาย</span></p>
<p class="MsoNormal"><b><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">บรรทัดอีก </span>N </b><b><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">บรรทัดถัดมา</span></b><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";"> จะประกอบไปด้วยจำนวนเต็ม </span>N <span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">จำนวนคือความน่าจะเป็นที่จะปฏิบัติภารกิจ โดยในบรรทัดที่ </span>i <span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ตัวเลขตัวที่ </span>j<span lang="TH" style="font-size: 14pt; font-family: "Angsana New";"> คือความน่าจะเป็นของภารกิจที่ </span>j <span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">เมื่อเลือกทำเป็นลำดับที่ </span>i <span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">โดยค่าเหล่านี้จะเป็นร้อยละ ซึ่งมีค่าในช่วง </span>0 <span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ถึง </span>100</p>
<p class="MsoNormal"><b><u><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ข้อมูลส่งออก</span><o:p></o:p></u></b></p>
<p class="MsoNormal"><b><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">บรรทัดเดียว</span></b><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";"> แสดงความน่าจะเป็นที่สูงที่สุดของการปฏิบัติภารกิจของจิมมี่ ด้วยร้อยละเป็นจำนวนทศนิยม โดยผลลัพธ์จะต้องต่างกับคำตอบไม่เกิน </span>0.000001 <span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">(หนึ่งในล้านส่วน) จึงจะถือว่าถูกต้อง</span></p>
<p class="MsoNormal"><b><u><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">อธิบายตัวอย่างที่สาม (ด้านล่าง)</span><o:p></o:p></u></b></p>
<p class="MsoNormal"><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ถ้าจิมมี่เลือกทำภารกิจตามลำดับเป็น ภารกิจที่ </span>3 <span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ภารกิจที่ </span>1 <span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">และภารกิจที่ </span>2 <span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ตามลำดับ</span></p>
<p class="MsoNormal"><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">จะได้ความน่าจะเป็นเท่ากับ </span>1.0 * 0.13 * 0.7 = 0.091 = 9.1%</p>
<p class="MsoNormal"><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ส่วนรูปแบบลำดับของภารกิจอื่นนั้นจะได้ความน่าจะเป็นที่น้อยกว่าเสมอ</span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<b><u><span lang="TH" style="font-size: 14pt; font-family: "Angsana New";">ที่มา</span><span style="font-size: 12pt; font-family: "Angsana New";">:</span></u></b><span style="font-size: 12pt; font-family: "Times New Roman";"> <strong>COCI 2006/2007, Contest #1 – October 28, 2008</strong></span>
<table>
<tr>
<th>ข้อมูลนำเข้า</th>
<th>ข้อมูลส่งออก</th>
</tr>
<tr>
<td>2
<br />100 100
<br />50 50</td>
<td>50.000000</td>
</tr>
<tr>
<td>2
<br />0 50
<br />50 0</td>
<td>25.00000</td>
</tr>
<tr>
<td>3
<br />25 60 100
<br />13 0 50
<br />12 70 90</td>
<td>9.10000</td>
</tr></table>