You're in charge of distributing T-Shirts to everyone. Simple enough, right? But remember, there are different sizes of T-Shirts, and you have to keep that in mind...
Challenge Specifications
There are N
T-Shirt sizes. There are K
people. Each person may wear any T-Shirt that is larger than them, but they can only wear a T-Shirt that is D
sizes down. You want to figure out what the optimal configuration is, based on the cost of the system. It is guaranteed that everyone will be able to get a T-Shirt, so you must give everyone a T-Shirt.
The cost is calculated as such:
Start from 0
and add up.
For every person who receives a T-Shirt, add |S1 - S2|
, where the person is size S1
and they are receiving a T-Shirt of size S2
.
Input Specifications
The input starts with the integers N
, K
, and D
. You can choose to not input N
or K
if you want. These can be given in an array, one on each line, space separated, or pretty much anything you want, but they must be given in this order. You must specify how you want input.
Then, the next part of the input is N
integers representing how many T-Shirts of each size there are. For example, with N := 3
, [1, 4, 2]
means that there is 1 size 1 T-Shirt, 4 size 2 T-Shirts, and 2 size 3 T-Shirt. It is guaranteed that the sum of these numbers equals K
. This can be taken as an array, an array contained at the end of the first part of input, an array joined to the end of the first part of the input, one on each line, space separated, or some other one that does not put you at a clear advantage. Again, please specify how you want input.
Then, the next part of the input is K
integers representing the individual size of each person. This order matters. This can be taken as an array, an array contained at the end of the first part of the input, etc.
You can also choose to start with size-0.
Output Specifications
Output must consist of K + 1
integers. The first K
of these represents the size of T-Shirt given to each person, and the last integer is the overall cost. This can be outputted as an array, space-separated integers, one on each line, etc.
Test Cases
Input:
3 10 1
3 5 2
1 1 1 2 2 2 2 2 3 3
Output:
1 1 1 2 2 2 2 2 3 3 0
Explanation:
This one's an easy case; each person gets the size of T-Shirt matching them, so the overall cost is 0
.
Input:
2 10 0
5 5
1 1 1 1 1 1 2 2 2 2
Output:
1 1 1 1 1 2 2 2 2 2 1 # Or 2 1 1 1 1 1 2 2 2 2, or similar outputs
Explanation:
There are 5 size-1 shirts, which are given to 5 of 6 size-1 people. There are 5 size-2 shirts, 4 of which are given to the 4 size-2 people. There is one more size-1 person and one more size-2 shirt, so this assignment is made at a cost of 1
.
Input:
7 20 2
5 0 5 0 5 0 5
3 5 7 9 3 5 7 9 3 5 7 9 3 5 7 9 3 5 7 9
Output:
1 3 5 7 1 3 5 7 1 3 5 7 1 3 5 7 1 3 5 7 40
Explanation:
At first glance, it may make sense to assign everyone the size of T-Shirt they need. However, then we get 5 size-9 people and 5 size-1 T-Shirts, and people can only wear shirts down 2 sizes, so we assign everyone a T-Shirt 2 sizes down, at a cost of 40
.
This test case is also in place to address the possible confusion that you can output the shirt sizes sorted. This is not always the case, as shown in this test case.
This is a code-golf challenge, so the shortest valid submission by March 14th (Pi Day) wins!
N
andK
parameters, even though they're just the lengths of the lines/arrays that follow? It may be necessary in a language like C in order to know how many elements to read from each array, but in languages where the sizes of arrays are known it's kinda awkward and redundant. \$\endgroup\$