Problem Statement |
| | You wish to earn money selling cute socks from the TC store. You live in Glastonbury, but its citizens are all long-time TopCoders, so you can't sell any socks there. Thus you are going to visit several other cities, find new TopCoders there, and sell them some socks. Unfortunately, several other TC members are also sock salesmen. If one or more sock salesmen visits a city before you, or at the same time as you, your profit in that city will be halved once for each of the other salesmen (because some people will buy his socks). Hence, if two people visit the city before you, you will only get one fourth of the potential profit. Also, travelling between cities is not free, so you may lose money if you visit too many cities. However, you have your competitors' plans, so you know which cities they will visit, and in what order they will visit them. Now you are planning your route, and want to maximize your profit.
You will be given a int[], money, which gives maximal possible earnings for each city. You will also be given a String[], costs, which contains the costs of getting from one city to another. A String[], times, gives you the number of days it takes to get from one city to another (you may assume that it takes no time to sell socks once you get to a city).
Both costs and times will be formatted in the same way. If they both have K elements, then each element of costs and times will contain K integers, each separated by a single space. The jth integer in the ith element of times will represent the number of days it takes to get from city i to city j. Similarly, the jth integer in the ith element of costs will represent the cost of travelling from city i to city j.
Also, a String[], competitors, gives you the routes of your competitors. Each element of competitors will be formatted as "N1 N2 ... Nk", where N1 N2 ... Nk are the numbers of the cities a competitor will visit (so first he will go to the city N1, then to the city N2 and so on).
Your method must plan the route that maximizes your profit. You will start in Glastonbury (city 0) and then visit any number of the cities (not visiting a particular city more than once), before finally returning to Glastonbury. All your competitors start their routes in Glastonbury at the same time as you, and they sell socks along the routes specified in competitors. It takes them the same amount of time to travel between cities as it takes you. Your method should return your maximum possible profit. |
| |
Definition |
| | | Class: | TCSocks | | Method: | earnMoney | | Parameters: | int[], String[], String[], String[] | | Returns: | int | | Method signature: | int earnMoney(int[] money, String[] cost, String[] time, String[] competitors) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | You must finish your route in city 0. |
| - | You may not visit a city more than once. |
| |
Constraints |
| - | money will contain between 1 and 10 elements, inclusive. |
| - | times, money and costs will each have the same number of elements. |
| - | Each element of money will be between 0 and 1000, inclusive. |
| - | The first element of money will be 0. |
| - | Each element of times and costs will contain K single-space delimited integers, where K is the number of elements in times and costs. |
| - | Each integer in costs will be between 0 and 1000, inclusive, and will contain no extra leading zeros. |
| - | Each integer in times will be between 1 and 10, inclusive, and will contain no extra leading zeros. |
| - | The ith integers of the ith elements of times and costs will be 0. |
| - | competitors will contain between 0 and 10 elements, inclusive. |
| - | Each element of competitors will be formatted as a single-space delimited list of 1 or more integers. |
| - | Each integer in each element of competitors will be between 1 and the number of elements in money-1, inclusive. |
| - | None of your competitors will visit any city more than once. |
| |
Examples |
| 0) | |
| | {0, 100, 100, 100} | {"0 50 50 200", "0 0 50 200", "0 10 0 200", "0 0 0 0"} | {"0 1 1 1", "1 0 1 1", "1 1 0 1", "1 1 1 0"} | {} |
| Returns: 140 | | You have no competitors. Your best path is 0 -> 2 -> 1 -> 0.
You spend 50 + 10 + 0 units, and earn 200 units. So the total income is 140. |
|
|
| 1) | |
| | {0, 100, 100, 100} | {"0 50 50 200", "0 0 50 200", "0 10 0 200", "0 0 0 0"} | {"0 1 1 1", "1 0 1 1", "1 1 0 1", "1 1 1 0"} | {"3", "2 3 1", "2 1"} |
| Returns: 50 | | The same data, but now you have three competitors. These competitors decrease your earnings in city 2, so you just visit city 1, and return back to Glastonbury. |
|
|
| 2) | |
| | {0, 100, 200} | {"0 20 10", "10 0 20", "20 10 0"} | {"0 1 5", "1 0 1", "1 1 0"} | {"2", "2"} |
| Returns: 240 | | Both your competitors want to visit city 2 first. Nevertheless, you can leave them behind, visiting city 1, then city 2, and returing back home. |
|
|
| 3) | |
| | {0, 40, 40, 40, 40, 40} | {"0 25 25 25 25 25", "25 0 25 25 25 25", "25 25 0 25 25 25",
"25 25 25 0 25 25", "25 25 25 25 0 25", "25 25 25 25 25 0"} | {"0 1 1 1 1 1", "1 0 1 1 1 1", "1 1 0 1 1 1", "1 1 1 0 1 1", "1 1 1 1 0 1", "1 1 1 1 1 0"} | {"1", "2", "3", "4", "5"} |
| Returns: 0 | | Here, staying at home is your best choice, because any trip is unprofitable. |
|
|
| 4) | |
| | {0, 70, 70, 70, 70, 70} | {"0 25 25 25 25 25", "25 0 25 25 25 25", "25 25 0 25 25 25",
"25 25 25 0 25 25", "25 25 25 25 0 25", "25 25 25 25 25 0"} | {"0 1 1 1 1 1", "1 0 1 1 1 1", "1 1 0 1 1 1", "1 1 1 0 1 1", "1 1 1 1 0 1", "1 1 1 1 1 0"} | {"1", "2", "3", "4", "5"} |
| Returns: 25 | | The same case, except cities give you bigger income. Visiting just one city is still unprofitable, and visiting any two cities still isn't good idea, but you will profit 25 units for visiting all of them in any order. |
|
|
| 5) | |
| | {0,457,434,382,818,403,265,449,214} | {"0 204 600 800 885 542 439 823 913",
"32 0 813 687 242 129 34 447 862",
"56 462 0 727 71 309 461 867 200",
"656 96 334 0 178 650 108 477 547",
"89 856 922 495 0 821 374 100 651",
"634 810 319 947 322 0 283 227 286",
"446 416 272 551 243 880 0 47 878",
"390 315 221 765 938 732 747 0 435",
"902 616 166 830 223 406 736 712 0"} | {"0 1 10 6 5 5 4 7 6",
"5 0 2 7 3 2 1 4 2",
"1 9 0 8 6 1 3 9 9",
"2 8 8 0 1 9 10 4 5",
"8 8 2 7 0 5 3 9 1",
"6 8 9 9 3 0 7 4 7",
"10 8 9 10 7 1 0 9 4",
"8 6 5 1 6 6 5 0 4",
"3 8 4 4 6 10 10 3 0"} | {"1 8 2 5 4 7 6","6 2 4","8 7"} |
| Returns: 785 | |
|