IPv444
TCO11 Round 1 · 2011-05-07 · by ir5
Problem Statement
After the shortage of IPv444 (Internet Protocol version 444) addresses had occurred, Fox Ciel decided to sell her IPv444 addresses to the traders.
An IP address in IPv444 is the concatenation of four integers between 0 and 999, inclusive, in decimal notation with no extra leading zeroes, separated by periods ('.'). For example, the following two strings are valid IPv444 addresses.
66.37.210.86 123.456.789.0
In addition, in IPv444, there is a way to represent some IP addresses by using a wildcard character '*'. Each '*' character replaces one of the four integers in the address, and represents all integers between 0 and 999, inclusive. For example, "23.4.*.8" represents 1000 IP addresses: "23.4.0.8", "23.4.1.8", ..., "23.4.999.8", and "*.4.*.8" represents 1000000 IP addresses.
Ciel received requests from some traders to sell her addresses. i-th trader requests IP addresses represented by request[i], and the trader promised to pay price[i] dollars for each requested address.
Each IP address can be sold to at most one trader, and each trader does not require all the IP addresses he requested. Assume that she owns all the IP addresses that have been requested by the traders.
Return the maximum amount of money Ciel can gain.
Constraints
- request will contain between 1 and 50 elements, inclusive.
- request and price will contain the same number of elements.
- Each element of request will be formatted as described in the statement.
- price will be between 1 and 1,000,000, inclusive.
{"66.37.210.86"}
{47}
Returns: 47
An optimal way is to sell IP address "66.37.210.86" to the 0-th trader. Then Ciel would gain 47 dollars.
{"0.0.0.*", "0.0.0.3", "0.0.0.5"}
{1, 3, 9}
Returns: 1010
Ciel is going to sell 1,000 addresses "0.0.0.0", ..., "0.0.0.999" to the traders. An optimal way is to sell "0.0.0.3" to trader 1, "0.0.0.5" to trader 2, and the other 998 addresses to trader 0. Ciel would gain 3*1+9*1+1*998=1010 dollars.
{"*.*.*.*", "123.456.789.0", "434.434.434.434", "999.*.999.*"}
{1, 5, 3, 6}
Returns: 1000005000006
It is possible for Ciel to gain a tremendous amount of money.
{"*.*.999.999", "888.888.999.*", "888.888.*.999", "777.777.777.777", "777.*.*.777"}
{19, 33, 42, 777, 7}
Returns: 26075718
{"127.0.0.1", "*.0.0.*", "*.*.255.255", "192.68.*.*"}
{999999, 629851, 294016, 438090}
Returns: 1361957076132
{
"1.1.1.*",
"1.1.*.1",
"1.*.1.1",
"*.1.1.1",
"*.*.*.999",
"*.*.*.888",
"*.*.*.1",
"*.*.*.2",
"*.*.*.3",
"*.*.*.4",
"*.*.*.5",
"*.*.*.6",
"*.*.*.7",
"*.*.*.8",
"*.*.*.9",
"*.*.*.0",
"*.*.1.*",
"*.*.2.*",
"*.*.3.*",
"*.*.1.*",
"*.*.1.*",
"*.*.1.*",
"*.*.4.*",
"*.*.5.*",
"*.*.6.*",
"*.*.7.*",
"*.*.8.*",
"*.*.9.*",
"*.*.0.*",
"*.1.*.*",
"*.2.*.*",
"*.3.*.*",
"*.4.*.*",
"*.5.*.*",
"*.6.*.*",
"*.7.*.*",
"*.8.*.*",
"*.9.*.*",
"*.0.*.*",
"1.*.*.*",
"2.*.*.*",
"3.*.*.*",
"4.*.*.*",
"5.*.*.*",
"6.*.*.*",
"7.*.*.*",
"8.*.*.*",
"9.*.*.*",
"0.*.*.*",
"*.*.*.*"}
{
989898,
989895,
989892,
989886,
30358,28885,42185,24816,49337,32121,35471,34601,29570,20974,46574,24669,32971,40031,32995,48323,47222,23726,39832,35120,46282,21196,41228,34404,44789,42737,34757,34831,45446,24781,41396,22960,32984,21837,21733,32810,37388,27596,36817,44411,42882,23310,29443,22611,27722,9706}
Returns: 10717792389547149
large test
Submissions are judged against all 117 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class IPv444 with a public method long long getMaximumMoney(vector<string> request, vector<int> price) · 117 test cases · 2 s / 256 MB per case