forked from keshavnandan/Topcoder
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBuyingTshirts.html
29 lines (29 loc) · 5.91 KB
/
BuyingTshirts.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
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td>A local store is selling T-shirts with the face of Fox Ciel printed on them.
Each such T-shirt costs <b>T</b> pesos.
Quimey and Pablo love those T-shirts.
They each buy a new T-shirt whenever they have the money to do so.
<br></br>
Currently, Quimey and Pablo have no money at all.
During the following N days they are going to earn some money and they will use it to buy the T-shirts.
The days are numbered from 0 (today) to N-1 (the day N-1 days in the future).
<br></br>
For each valid i, <b>Q</b>[i] and <b>P</b>[i] are the amounts in pesos Quimey and Pablo will earn on day i.
(Note that each of those amounts is at most <b>T</b>.
Therefore, Quimey and Pablo will be able to buy at most one T-shirt each day.)
<br></br>
For example, suppose that a T-shirt costs <b>T</b>=10 pesos.
If <b>Q</b>={2,3,5,10}, the following will happen to Quimey:
<ul>
<li>On day 0, he earns 2 pesos. He now has 2 pesos.</li>
<li>On day 1, he earns 3 pesos. He now has 5 pesos.</li>
<li>On day 2, he earns 5 pesos. He now has 10 pesos, which is enough to buy a T-shirt. He goes to the store and buys one. Afterwards, he has 0 pesos left.</li>
<li>On day 3, he earns 10 pesos. He then goes to buy a second T-shirt. Afterwards, he again has 0 pesos left.</li>
</ul>
If <b>P</b>={10,8,6,4}, Pablo would buy one T-shirt on day 0, and then another T-shirt on day 2. After buying the T-shirt on day 2 he would have 4 pesos left. After day 3 he would then have a total of 8 pesos, which is still not enough for a T-shirt.
Note that in this example Quimey and Pablo would go to the store together on day 2.
<br></br>
You are given the int <b>T</b>: the price of a single T-shirt.
You are also given the vector <int>s <b>Q</b> and <b>P</b> with N elements each: the amounts Quimey and Pablo earn each day.
Compute and return the number of days on which Quimey and Pablo both go to the store</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>BuyingTshirts</td></tr><tr><td>Method:</td><td>meet</td></tr><tr><td>Parameters:</td><td>int, vector <int>, vector <int></td></tr><tr><td>Returns:</td><td>int</td></tr><tr><td>Method signature:</td><td>int meet(int T, vector <int> Q, vector <int> P)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td colspan="2"><h3>Limits</h3></td></tr><tr><td>    </td><td><table><tr><td>Time limit (s):</td><td>2.000</td></tr><tr><td>Memory limit (MB):</td><td>256</td></tr><tr><td>Stack limit (MB):</td><td>256</td></tr></table></td></tr><tr><td colspan="2"><h3>Notes</h3></td></tr><tr><td align="center" valign="top">-</td><td>If you need the number <b>N</b> in your solution, you can determine it as the number of elements in <b>Q</b>.</td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>T</b> will be between 1 and 100.</td></tr><tr><td align="center" valign="top">-</td><td><b>Q</b> will contain between 1 and 100 elements.</td></tr><tr><td align="center" valign="top">-</td><td><b>Q</b> and <b>P</b> will contain the same number of elements.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>Q</b> will be between 1 and T.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>P</b> will be between 1 and T.</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>5</pre></td></tr><tr><td><pre>{1,2,3,4,5}</pre></td></tr><tr><td><pre>{5,4,3,2,1}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 2</pre></td></tr><tr><td><table><tr><td colspan="2">Quimey will buy his T-shirts on days 2, 3, and 4.<br></br>
Pablo will buy his on days 0, 2, and 4.<br></br>
They will go to the store together twice: first on day 2 and then on day 4.</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>10</pre></td></tr><tr><td><pre>{10,10,10}</pre></td></tr><tr><td><pre>{10,10,10}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 3</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>2</pre></td></tr><tr><td><pre>{1,2,1,2,1,2,1,2}</pre></td></tr><tr><td><pre>{1,1,1,1,2,2,2,2}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 5</pre></td></tr><tr><td><table><tr><td colspan="2">They will both go to the store on the following days: 1, 3, 5, 6, and 7.</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>100</pre></td></tr><tr><td><pre>{1,2,3}</pre></td></tr><tr><td><pre>{4,5,6}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 0</pre></td></tr><tr><td><table><tr><td colspan="2">In this test case they do not buy any T-shirts at all.</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>10</pre></td></tr><tr><td><pre>{10,1,10,1}</pre></td></tr><tr><td><pre>{1,10,1,10}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 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>