SlimeXSlimeRancher
SRM 506 · 2010-11-01 · by dolphinigle
Problem Statement
You are playing a game titled Slime Rancher. You will be training slimes in this game.
You have three slimes-in-training. Associated with each slime are N different attributes, each represented by a positive integer. The attributes of the slimes will be given in
You will train these slimes, and after the training is complete, each of the slimes' attributes will either increase by some integral value or stay the same. The weight of the training is defined as the sum of the differences between the final and initial values of all the attributes for all three slimes.
These slimes are going to be combined to make an even stronger slime. Three slimes produce the strongest result when combined if there exists a way such that when their final attributes are sorted in ascending order of values (identical valued attributes may be permuted to your liking), the attribute types match. That is, the i-th attribute in the sorted attributes for the first, second, and third slime must be the same attribute type (their values need not be the same, only their relative ordering).
You are a master slime breeder and you're able to obtain any possible final values for the slimes' attributes. What is the minimum possible weight of the training that gives the strongest result?
Constraints
- first_slime, second_slime, and third_slime will each contain between 1 and 50 elements, inclusive.
- Each element in first_slime, second_slime, and third_slime will contain between 1 and 50 characters, inclusive.
- first_slime, second_slime, and third_slime will each be formatted as described in the problem statement without leading or trailing spaces.
- Each of first_slime, second_slime, and third_slime will contain the same number of integers.
- All the integers in first_slime, second_slime, and third_slime will be between 1 and 1,000,000,000, inclusive, given without leading zeroes.
- The number of integers in first_slime will be between 1 and 150, inclusive.
{"1 6 2"}
{"1 3 5"}
{"5 4 3"}
Returns: 5
We will use the following legends: Initially, the slimes' attributes are as follows. Train the slimes as follows. The attributes can then be sorted as follows. The attributes match for all three slimes in the ordering above. Since the attributes can be sorted such that the attributes match for all the slimes, the slime produced by combining them is the strongest.
{"3 2 1"}
{"6 5 4"}
{"9 8 7"}
Returns: 0
{"1 2", "3 4"}
{"12 3 ", "4"}
{"1 2 ", "34"}
Returns: 36
{"1 1 1 1000000000 1000000000 1000000000"}
{"1000000000 1000000000 1000000000 1 1 1"}
{"1 1 1 2 2 2"}
Returns: 2999999997
Watch out for integer overflow.
{"1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16"}
{"1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16"}
{"1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16"}
Returns: 0
Submissions are judged against all 185 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SlimeXSlimeRancher with a public method long long train(vector<string> first_slime, vector<string> second_slime, vector<string> third_slime) · 185 test cases · 2 s / 256 MB per case