forked from daiwb/Algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathAgeEncoding.html
More file actions
10 lines (7 loc) · 6.1 KB
/
AgeEncoding.html
File metadata and controls
10 lines (7 loc) · 6.1 KB
1
2
3
4
5
6
7
8
9
10
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td><i>NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet.</i>
<br></br><br></br>
Your friend's birthday is approaching, and he wants his age to be written in candles on his cake. In fact, he has already placed several candles on the cake. The candles are arranged in a single row, and there are two different colors of candles. One color represents the digit '0' and the other color represents the digit '1'. You don't want to relayout the candles from scratch, so you have to determine if there's a base for which the existing candles spell out your friend's age. To simplify the task, you can choose any strictly positive base, not necessarily an integer one.
<br></br><br></br>
For example, if the candles are "00010" and your friend's age is 10, then the candles spell out 10 in base 10 (decimal). If the candles are "10101" and your friend's age is 21, then you can say that "10101" is 21 in base 2 (binary). If the candles are "10100" and your friend's age is 6, then the candles spell out 6 in base sqrt(2)=1.41421356237.... Note that you are not allowed to rotate the cake, so "10" cannot be read as "01".
<br></br><br></br>
You are given a string <b>candlesLine</b>, where the i-th character is the digit ('0' or '1') represented by the i-th candle in the row of candles on the cake. You are also given an int <b>age</b>, which is your friend's age. Return the positive base for which the candles represent your friend's age. If there is no such base, return -1, and if there are multiple such bases, return -2.</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>AgeEncoding</td></tr><tr><td>Method:</td><td>getRadix</td></tr><tr><td>Parameters:</td><td>int, string</td></tr><tr><td>Returns:</td><td>double</td></tr><tr><td>Method signature:</td><td>double getRadix(int age, string candlesLine)</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>The number a<sub>n</sub>a<sub>n-1</sub>...a<sub>1</sub>a<sub>0</sub> in base B is equal to a<sub>n</sub>*B<sup>n</sup> + a<sub>n-1</sub>*B<sup>n-1</sup> + ... + a<sub>1</sub>*B + a<sub>0</sub>.</td></tr><tr><td align="center" valign="top">-</td><td>The returned value 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>age</b> will be between 1 and 100, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>candlesLine</b> will contain between 1 and 50 characters, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each character in <b>candlesLine</b> will be '0' (zero) or '1' (one).</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>10</pre></td></tr><tr><td><pre>"00010"</pre></td></tr></table></td></tr><tr><td><pre>Returns: 10.0</pre></td></tr><tr><td><table><tr><td colspan="2">This is the first example from the statement: simply a decimal notation of the given age. Note that notation can have leading zeroes.</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>21</pre></td></tr><tr><td><pre>"10101"</pre></td></tr></table></td></tr><tr><td><pre>Returns: 2.0</pre></td></tr><tr><td><table><tr><td colspan="2">This is the second example from the statement: "10101" is a binary notation of the given age.</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>6</pre></td></tr><tr><td><pre>"10100"</pre></td></tr></table></td></tr><tr><td><pre>Returns: 1.414213562373095</pre></td></tr><tr><td><table><tr><td colspan="2">This is the third example from the statement.</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>21</pre></td></tr><tr><td><pre>"10111111110111101111111100111111110111111111111100"</pre></td></tr></table></td></tr><tr><td><pre>Returns: 0.9685012944510603</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>16</pre></td></tr><tr><td><pre>"1"</pre></td></tr></table></td></tr><tr><td><pre>Returns: -1.0</pre></td></tr><tr><td><table><tr><td colspan="2">In any base, "1" represents the age of 1, so it's impossible to get the age of 16.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">5)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>1</pre></td></tr><tr><td><pre>"1"</pre></td></tr></table></td></tr><tr><td><pre>Returns: -2.0</pre></td></tr><tr><td><table><tr><td colspan="2">In any base, "1" represents the age of 1.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">6)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>1</pre></td></tr><tr><td><pre>"001000"</pre></td></tr></table></td></tr><tr><td><pre>Returns: 1.0</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>