Buckets and Balls, Again

[littlehug]

Place balls into buckets according to first fit, best fit, and worst fit.

Task Description

We are given N buckets with index from 0 to N-1 and M balls. Each bucket has a weight limit and each ball has a weight. Now we need to put the balls one by one into buckets, and we should make sure that the total weight of balls in a bucket does not exceed the weight limit. Once we put a ball into a bucket, we record the bucket index. If we could not find a bucket for a ball because it is too heavy, then we discard the ball and record -1. Write a function to record the how we place balls into buckets.

The balls can be put into the bucket according to either of the following three rules.

First fit. We place the ball to the first bucket that can hold it. If no bucket can hold the ball, we discard it. Best fit. We place the ball into the bucket that has the smallest remaining capacity after placing the ball. If no bucket can hold this ball, we discard the ball. Note that if more than one buckets have the same smallest remaining capacity, we put the ball into the one with the smallest index.
Worst fit. We place the ball into the bucket that has the largest remaining capacity after placing the ball. If no bucket can hold this ball, we discard the ball. Note that if more than one buckets have the same largest remaining capacity, we put the ball into the one with the largest index.

We use an example to illustrate the placement. Now we have three buckets (b0, b1, and b2), and four balls. The weight limits of the buckets are {13, 11, 12}, and and the weights of the four balls are {7, 8, 4, 9}.

When we use first fit, the following will happen.

• Iteration 1: we put the first ball of weight 7 into b0 because b0 has room for it, and the remaining capacity sequence is {6, 11, 12}.
• Iteration 2: we put the second ball of weight 8 into b1 because b1 has enough room and the index is the smallest. The remaining capacity sequence is {6, 3, 12}.
• Iteration 3: we put the third ball of weight 4 into b0 because b0 has enough room and the remaining capacity sequence is {2, 3, 12}.
• Iteration 4: we put the fourth ball of weight 9 into b2 because b2 is the only bucket with enough capacity. The buckets the balls go to are {0, 1, 0, 2}.

When we use best fit the following will happen.

• Iteration 1: we put the first ball of weight 7 into b1 because b1 has the smallest remaining capacity, and the remaining capacity sequence is {13, 4, 12}.
• Iteration 2: we put the second ball of weight 8 into b2 because b2 has the smallest remaining capacity, and the remaining capacity sequence is {13, 4, 4}.
• Iteration 3: we put the third ball of weight 4 into b1 because b1 has smallest remaining capacity and the index is the smallest. The remaining capacity sequence is {13, 0, 4}.
• Iteration 4: we put the fourth ball of weight 9 into b0 because b0 is the only bucket with enough capacity. The buckets the balls go to are {1, 2, 1, 0}.

When we use worst fit:

• Iteration 1: we put the first ball of weight 7 into b0 because b0 has the largest remaining capacity, and the remaining capacity sequence is {6, 11, 12}.
• Iteration 2: we put the second ball of weight 8 into b2 because b2 has the largest remaining capacity, and the remaining capacity sequence is {6, 11, 4}.
• Iteration 3: we put the third ball of weight 4 into b1 because b1 has the largest remaining capacity, and the remaining capacity sequence is {6, 7, 4}.
• Iteration 4: we discard the fourth ball of weight 9 because there is no bucket with enough capacity, and we record -1. The buckets the balls go to are {0, 2, 1, -1}.

You may use the following main function to test your function.

#include<stdio.h>
#include"placement.h"

int main(){
    int N,M,method;
    scanf("%d%d%d",&N,&M,&method);
    int buckets[N];
    for(int i=0;i<N;i++)
        scanf("%d",&buckets[i]);
    int balls[M];
    for(int i=0;i<M;i++)
        scanf("%d",&balls[i]);
    int result[M];
    place(buckets,N,balls,M,method,result);
    for(int i=0;i<M;i++)
        printf("%d%s",result[i],i==M-1?"":" ");
    return 0;
}

The prototype of place function is as follows.

void place(int bucket[1024],int N,int ball[16384],int M,int method,int result[16384]);

The placement.h is as follow:

void place(int bucket[1024],int N,int ball[16384],int M,int method,int result[16384]);

Subtask

• 20 points: Implement the first fit.
• 40 points: Implement the best fit.
• 40 points: Implement the worst fit.

  Input Format

  The input contains only one test case. The first line contains three integers N, M, and an integer for the placement method, where N is the bucket number, M is the ball number.

• When the method is 0, we use first fit.
• When the method is 1, we use best fit.
• When the method is 2, we use worst fit.

The second line contains N integers, and the i-th integer represents the weight limit of bucket bi. The third line contains M integers, and each integer represents the weight of a ball.

• N is no more than 1024.
• M is no more than 16384.

  Output Format

  Print the buckets the balls go to in a line. If we discard a ball, the placement of the ball is -1.

  Sample Input 1

  3 4 0
  13 11 12
  7 8 4 9

  Sample Output 1

  0 1 0 2

  Sample Input 2

  3 4 1
  13 11 12
  7 8 4 9

  Sample Output 2

  1 2 1 0

  Sample Input 3

  3 4 2
  13 11 12
  7 8 4 9

  Sample Output 3

  0 2 1 -1