prithivMLmods/Coder-Stat

1 2 3<h1><font color="#000">Problem A:</font> Ohgas' Fortune</h1>4 5<p>6The Ohgas are a prestigious family based on Hachioji.  The head of the family,7Mr. Nemochi Ohga, a famous wealthy man, wishes to increase his fortune8by depositing his money to an operation company. You are asked to help9Mr. Ohga maximize his profit by operating the given money during a specified10period.11</p>12 13<p>14From a given list of possible operations, 15you choose an operation to deposit the given fund to. 16You commit on the single operation throughout the period and17deposit all the fund to it.18 19Each operation specifies an annual interest rate, whether the interest20is simple or compound, and an annual operation charge.21 22An annual operation charge is a constant 23not depending on the balance of the fund.24 25The amount of interest is calculated at the end of every year, by26multiplying the balance of the fund under operation by the annual27interest rate, and then rounding off its fractional part. For compound28interest, it is added to the balance of the fund under operation, and29thus becomes a subject of interest for the following years.  For30simple interest, on the other hand, it is saved somewhere else and31does not enter the balance of the fund under operation (i.e. it is32not a subject of interest in the following years).33 34An operation charge is then subtracted from the balance of the fund35under operation.  You may assume here that you can always pay the36operation charge (i.e. the balance of the fund under operation is37never less than the operation charge).38 39The amount of money you obtain after the specified years of operation40is called ``the final amount of fund.''  For simple interest, it is41the sum of the balance of the fund under operation at the end of the42final year, plus the amount of interest accumulated throughout the43period. For compound interest, it is simply the balance of the fund44under operation at the end of the final year.45 46</p>47 48<p>49Operation companies use C, C++, Java, etc., to perform their50calculations, so they pay a special attention to their interest51rates. That is, in these companies, an interest rate is always an52integral multiple of 0.0001220703125 and between 0.0001220703125 and530.125 (inclusive).  0.0001220703125 is a decimal representation of541/8192. Thus, interest rates' being its multiples means that they can55be represented with no errors under the double-precision binary56representation of floating-point numbers.57</p>58 59<p>60For example, if you operate 1000000 JPY for five years with an annual,61compound interest rate of 0.03125 (3.125 %) and an annual operation charge of 3000 JPY, the balance changes as62follows.63</p>64 65<table border>66<tr align=right rowspan=2><td>The balance of the fund under operation67(at the beginning of year)</td>68<td>Interest</td><td>69The balance of the fund under operation (at the end of year)</td></tr>70<tr align=right><td>A</td><td>B = A &times; 0.03125 (and rounding off fractions)</td>71<td>A + B - 3000</td></tr>72<tr align=right><td>1000000</td><td>31250</td><td>1028250</td></tr>73<tr align=right><td>1028250</td><td>32132</td><td>1057382</td></tr>74<tr align=right><td>1057382</td><td>33043</td><td>1087425</td></tr>75<tr align=right><td>1087425</td><td>33982</td><td>1118407</td></tr>76<tr align=right><td>1118407</td><td>34950</td><td>1150357</td></tr>77</table>78<p>79After the five years of operation, the final amount of fund is 1150357 JPY.80</p>81 82<p>83If the interest is simple with all other parameters being equal, 84it looks like:85</p>86 87<table border>88<tr align=right rowspan=2>89<td>90The balance of the fund under operation (at the beginning of year)</td>91<td>Interest</td>92<td>The balance of the fund under operation (at the end of year)</td>93<td>Cumulative interest </td></tr>94<tr align=right>95<td>A</td><td>B = A &times; 0.03125 (and rounding off fractions)</td><td>A - 3000</td><td></td>96</tr>97<tr align=right><td>1000000</td><td>31250</td><td>997000</td><td>31250</td></tr>98<tr align=right><td>997000</td><td>31156</td><td>994000</td><td>62406</td></tr>99<tr align=right><td>994000</td><td>31062</td><td>991000</td><td>93468</td></tr>100<tr align=right><td>991000</td><td>30968</td><td>988000</td><td>124436</td></tr>101<tr align=right><td>988000</td><td>30875</td><td>985000</td><td>155311</td></tr>102</table border>103 104<p>In this case the final amount of fund is the total of the fund under105operation, 985000 JPY, and the cumulative interests, 155311 JPY, which106is 1140311 JPY.107</p>108 109<h2>Input</h2>110<p>111The input consists of datasets. The entire input looks like:112</p>113 114<blockquote>115<i>the number of datasets (=m)</i> <br>116<i>1st dataset</i>                 <br>117<i>2nd dataset</i>                 <br>118...                                <br>119<i>m-th dataset</i>                <br>120</blockquote>121 122<p>123The number of datasets, <i>m</i>, is no more than 100.124Each dataset is formatted as follows.125</p>126 127<blockquote>128<i>the initial amount of the fund for operation</i>  <br>129<i>the number of years of operation</i>              <br>130<i>the number of available operations (=n)</i>       <br>131<i>operation 1</i>                                   <br>132<i>operation 2</i>                                   <br>133...                                                  <br>134<i>operation n</i>                                   <br>135</blockquote>136 137<p>138The initial amount of the fund for operation, the number of years of operation, 139and the number of available operations are all positive integers.140The first is no more than 100000000, the second no more than 10, and 141the third no more than 100.142</p>143 144<p>145Each ``operation'' is formatted as follows.146</p>147 148<blockquote>149<i>simple-or-compound annual-interest-rate annual-operation-charge</i>150</blockquote>151 152<p>153where <i>simple-or-compound</i> is a single character of either '0' or '1', 154with '0' indicating155simple interest and '1' compound. <i>annual-interest-rate</i> is represented156by a decimal fraction and is an integral multiple of 1/8192.157<i>annual-operation-charge</i> is an integer not exceeding 100000.158</p>159 160<h2>Output</h2>161<p>162For each dataset, print a line having a decimal integer indicating the163final amount of fund for the best operation. The best operation is the164one that yields the maximum final amount among the available165operations. Each line should not have any character other than 166this number.167</p>168 169<p>170You may assume the final balance never exceeds 1000000000.171You may also assume that at least one operation has the final amount of the172fund no less than the initial amount of the fund.173</p>174 175<h2>Sample Input</h2>176<pre>17741781000000179518021810 0.03125 30001821 0.03125 30001836620000184718521860 0.0732421875 423071871 0.0740966796875 4094218839677000189419041910 0.0709228515625 307541921 0.00634765625 261651930 0.03662109375 794681940 0.0679931640625 1093219510585000196619741981 0.0054931640625 597591991 0.12353515625 564642000 0.0496826171875 981932010 0.0887451171875 78966202</pre>203 204<h2>Output for the Sample Input</h2>205<pre>2061150357207105596832085079691820920829397210</pre>211 212 213 214 215 216 217 218