-
Notifications
You must be signed in to change notification settings - Fork 1
/
FoxListeningToMusic.html
13 lines (13 loc) · 4.45 KB
/
FoxListeningToMusic.html
1
2
3
4
5
6
7
8
9
10
11
12
13
<html><body bgcolor="#ffffff" text="#000000"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td><p>Fox Jiro is going to listen to some music. He has N songs, numbered 0 to N-1, inclusive. The lengths of the songs are given in the int[] <b>length</b>, where the i-th element is the length in seconds of song i.</p>
<br></br>
<p>The music player he uses has a shuffle feature. Using this feature, he can listen to the songs in random order. More precisely, first the player chooses one song among all songs with equal probability and plays it. When the song ends, the player chooses the next song in the same fashion and plays it immediately. Note that the player may choose the same song more than once in a row.</p>
<br></br>
<p>You are given an int <b>T</b>. Return a double[] P, where P[i] indicates the probability that the player is playing the i-th song <b>T</b>+0.5 seconds after Jiro starts listening to the music in shuffle mode.</p></td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>FoxListeningToMusic</td></tr><tr><td>Method:</td><td>getProbabilities</td></tr><tr><td>Parameters:</td><td>int[], int</td></tr><tr><td>Returns:</td><td>double[]</td></tr><tr><td>Method signature:</td><td>double[] getProbabilities(int[] length, int T)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td>    </td></tr><tr><td></td></tr><tr><td colspan="2"><h3>Notes</h3></td></tr><tr><td align="center" valign="top">-</td><td>Each element of the returned array must have an absolute or relative error less than 1e-9.</td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>length</b> will contain 1 and 50 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>length</b> will be between 1 and 80,001, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>T</b> will be between 0 and 80,000, inclusive.</td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{1, 2}</pre></td></tr><tr><td><pre>1</pre></td></tr></table></td></tr><tr><td><pre>Returns: {0.25, 0.75 }</pre></td></tr><tr><td><table><tr><td colspan="2"><p>There are three possible scenarios that lead up to time 1.5:</p>
<ul>
<li>song 0 -> song 0 (with probability 1/4)</li>
<li>song 0 -> song 1 (with probability 1/4)</li>
<li>song 1 (with probability 1/2)</li>
</ul>
</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{1, 10, 100, 1000, 10000}</pre></td></tr><tr><td><pre>0</pre></td></tr></table></td></tr><tr><td><pre>Returns: {0.2, 0.2, 0.2, 0.2, 0.2 }</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{5, 8, 4, 7}</pre></td></tr><tr><td><pre>10</pre></td></tr></table></td></tr><tr><td><pre>Returns: {0.1875, 0.3125, 0.1875, 0.3125 }</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{10, 1}</pre></td></tr><tr><td><pre>9</pre></td></tr></table></td></tr><tr><td><pre>Returns: {0.9990234375, 9.765625E-4 }</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">4)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{58, 47, 36, 25, 14, 3}</pre></td></tr><tr><td><pre>100</pre></td></tr></table></td></tr><tr><td><pre>Returns:
{0.32895835374381194, 0.26291497538241776, 0.18463894970453887, 0.1312301113062895,
0.07518634032025856, 0.017071269542683242 }</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr></table><p>This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. </p></body></html>