forked from keshavnandan/Topcoder
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathTravellingSalesmanEasy.html
50 lines (45 loc) · 7.09 KB
/
TravellingSalesmanEasy.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
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td><p>
You are a traveling salesman.
You have already heard a lot about how hard the problems of a traveling salesman can be.
Luckily, the one you currently have seems easier.
</p>
<p>
There are <b>M</b> cities where you can sell products.
The cities are conveniently numbered 1 through <b>M</b>.
</p>
<p>
You have a case that contains multiple items.
Each of those items can only be sold in one of the cities.
You are given information about those items in vector <int>s <b>profit</b> and <b>city</b>.
For each valid i, you have an item that can be sold in <b>city</b>[i], and doing so would bring you <b>profit</b>[i] dollars of profit.
Obviously, you can only sell each item at most once.
</p>
<p>
You have already planned your business trip: a sequence of cities you are going to visit.
These are given in the vector <int> <b>visit</b>.
Each time you visit a city you may sell at most one item.
</p>
<p>
Compute and return the maximum total profit you can obtain.
</p></td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>TravellingSalesmanEasy</td></tr><tr><td>Method:</td><td>getMaxProfit</td></tr><tr><td>Parameters:</td><td>int, vector <int>, vector <int>, vector <int></td></tr><tr><td>Returns:</td><td>int</td></tr><tr><td>Method signature:</td><td>int getMaxProfit(int M, vector <int> profit, vector <int> city, vector <int> visit)</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>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>M</b> will be between 1 and 100, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>profit</b> will have between 1 and 2500 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>city</b> will have exactly the same number of elements as <b>profit</b>.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>profit</b> will between 1 and 100, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>city</b> will be between 1 and <b>M</b>, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td><b>visit</b> will have between 1 and 2500 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>visit</b> will be between 1 and <b>M</b>, 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>2</pre></td></tr><tr><td><pre>{3,10}</pre></td></tr><tr><td><pre>{1,1}</pre></td></tr><tr><td><pre>{2,1}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 10</pre></td></tr><tr><td><table><tr><td colspan="2"><p>
There are 2 cities, and you have 2 items. Both of these two items can only be sold to city 1, with one giving you profit 10, and the other giving profit 3.
Your trip consists of a visit to city 2 and then a visit to city 1. At city 2, you cannot sell any item, so your profit in this case is zero. At city 1, you can sell the item with profit 10. Thus, the total answer is 0+10=10, which is the maximum profit you can achieve.
</p></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</pre></td></tr><tr><td><pre>{3,5,2,6,4}</pre></td></tr><tr><td><pre>{1,1,1,1,1}</pre></td></tr><tr><td><pre>{1,1,1}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 15</pre></td></tr><tr><td><table><tr><td colspan="2">It is possible for you to visit a city multiple times. Each time you visit the city, you may sell another item.</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>{77,33,10,68,71,50,89}</pre></td></tr><tr><td><pre>{4,1,5,6,2,2,1}</pre></td></tr><tr><td><pre>{6,5,5,6,4}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 155</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>7</pre></td></tr><tr><td><pre>{22,91,53,7,80,100,36,65,92,93,19,92,95,3,60,50,39,36,2,30,63,84,2}</pre></td></tr><tr><td><pre>{5,3,4,3,6,5,6,6,5,2,7,6,3,2,6,1,7,4,6,3,7,2,5}</pre></td></tr><tr><td><pre>{5,7,1,3,6,2,5,7,3,6,3,2,7,3,1,3,1,7,2,3,1,1,3,1,6,1}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 1003</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>85</pre></td></tr><tr><td><pre>{94,21,99,27,91,1,64,96,32,39,84,71,97,53,73,20,7,13,33,45,5,85,7,87,
94,37,48,30,5,85,47,62,91,18,71,37,7,25,75,17,40,19,89,85,86,87,45,
12,61,71,32,73,63,89,25,51,60,76,32,2,69,78,28,32,74,44,47,11,82,5,
2,28,54,35,67,44,35,6,70,66,77,7,60,67,33,66,21,91,76,75,16,79,20,24,
91,31,2,50,11,19,93,49,4,7,55,9,95,39,54,12,48,38,73,100,57,97,44,2,
2,51,40,4,51,3,95,93,56,88,60,98,67,7,99,46,71,75,24,82,87,29,92,92,
81,87,34,83,58,46,79,53,38,32,97,41,65,10,54,81,42,37,76,28,11,50,
13,29,15,99,73,72,2,81,39,75,1,54}</pre></td></tr><tr><td><pre>{72,69,19,25,3,65,10,42,37,76,29,34,41,14,46,46,37,55,30,32,84,57,74,
16,10,48,67,31,44,84,11,59,67,63,5,31,28,71,3,21,42,21,61,50,5,79,79,
27,69,33,47,70,76,70,17,73,28,64,77,84,9,6,63,71,17,71,40,9,8,16,76,
76,6,53,47,10,45,31,78,55,13,35,50,43,32,78,78,44,20,56,24,43,80,62,
72,16,5,72,67,29,11,51,64,27,7,44,59,1,40,71,64,63,67,81,72,22,73,59,
21,44,3,18,9,75,72,43,13,44,79,42,58,49,81,44,42,41,35,81,63,74,42,79,
42,39,45,49,18,73,53,36,80,34,75,57,10,79,79,33,48,18,81,3,69,36,37,
49,54,29,17,81,83,13,8,69,5,84}</pre></td></tr><tr><td><pre>{39,29,15,5,3,65,29,64,60,21,13,10,73,75,44,84,15,61,26,49,31,27,83,24,
16,55,60,74,71,53,68,15,75,15,36,4,47,9,77,45,63,32,77,84,8,68,11,5,18,
80,36,52,42,59,79,83,81,29,43,70,29,19,68,5,83,60,71,66,62,81,85,39,42,
40,69,60,34,12,2,4,31,36,81,33,71,32,68,5,30,59,61,10,71,49,63,30,62,
83,35,56,82,2,14,59,68,74,32,31,3,28,38,54,38}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 4369</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>