Untitled

A computer hardware manufacturer has two warehouses for storing components.

This company offers a service that provides estimates that maximize computer performance within the consumer’s budget.

When manufacturing a computer, three types of components are chosen one by one each, and the performance of it is represented by the performance of the component with the lowest performance.

The amount of money the consumer has to pay is the sum of the component price and shipping charge. If multiple combinations max out computer performance, choose the combination with the lowest price.

If the chosen components are at a single warehouse, the components are shipped out right away.

If components of two warehouses are needed, components are gathered and the shipping charge is payed before the components are shipped out.

 



Let’s say a consumer with the budget of 400 placed an order, when the shipping charge is 50 and the list of inbound components of the warehouses equals to [Fig. 1].



If you choose components of Warehouse 0 only, at a cost of 100 + 220 + 77 = 397, as in [Fig. 2–(a)], you can manufacture a computer with the performance of 50 which is the minimum among component performance of 200, 120, and 50.

If you choose components of Warehouse 1 only, at a cost of 150 + 120 + 130 = 400, as in [Fig. 2–(b)], you can manufacture a computer with the performance of 70 which is the minimum among component performance of 150, 100, and 70.

 

 



If you choose components of both Warehouses 0 and 1, at a cost of 358 which is the sum of 100 + 120 + 88 = 308 and the shipping charge of 50, as in [Fig. 3], you can manufacture a computer with the performance of 100 which is the minimum among component performance of 200, 100, and 150.

This combination maximizes performance within the budget.

 

You are required to write a program that handles orders from consumers and manages components of each warehouse as above.

Implement each required function by referring to the following API description.

※ The function signature below is based on C/C++. As for other languages, refer to the provided Main and User Code.

 

The following is the description of API to be written in the User Code.

void init(int mCharge)

This function is called in the beginning of each test case, and shows the shipping charge between warehouses.

All previous lists of components are initialized.

 

Parameters

    mCharge : shipping charge between warehouses ( 1 ≤ mCharge ≤ 100,000 )

int stock(int mType, int mPrice, int mPerformance, int mPosition)

This function adds a new component to the list.

Inputs of the same type, price and function are not given two or more times within a test case.

 

Parameters

    mType       : component type             ( 0 ≤ mType ≤ 2 )

    mPrice       : component price            ( 1 ≤ mPrice ≤ 100,000 )

    mPerformance: component performance             ( 1 ≤ mPerformance ≤ 1,000,000 )

    mPosition    : the number assigned to the warehouse at which the component is stored ( 0 ≤ mPosition ≤ 1 )

 

Returns

    Return the number of kinds of components of the same type in the warehouse at which the component is brought in

Result order(int mBudget)

When the consumer’s budget is mBudget, this function chooses the combination that maximizes performance within the budget.

In the case of same performance, choose the combination with the lowest cost.

You never run out of stock as components are replenished immediately after being shipped out.

 

Parameters

    mBudget: consumer’s budget ( 1 ≤ mBudget ≤ 500,000 )

 

Returns

    If a computer can be manufactured within the given budget, return the price of the computer as mPrice, and the performance of the computer as mPerformance of the Result structure.

    If not, both mPerformance and mPrice returns 0.



[Example]

The below example describes test case 1.

Order

Function

return

Figure

1

init(50)

 

 

2

stock(0, 100, 200, 0)

1

 

3

stock(0, 200, 100, 0)

2

 

4

stock(1, 220, 120, 0)

1

 

5

stock(1, 330, 160, 0)

2

 

6

stock(2, 77, 50, 0)

1

 

7

stock(2, 88, 150, 0)

2

 

8

stock(0, 150, 150, 1)

1

 

9

stock(0, 250, 300, 1)

2

 

10

stock(1, 120, 100, 1)

1

 

11

stock(1, 450, 200, 1)

2

 

12

stock(2, 300, 200, 1)

1

 

13

stock(2, 130, 70, 1)

2

 

14

order(400)

mPrice = 358

mPerformance = 100

Fig. 3

 

(Order 14) Explanation for orders 1 to 14 is same as the above description.



15

order(450)

mPrice = 408

mPerformance = 120

Fig. 4

16

order(346)

mPrice = 0

mPerformance = 0

 

 



(Order 15) If components are chosen at Warehouse 0 only, as in [Fig. 4], at a cost of 408, you can manufacture a computer that has the performance of 120.

(Order 16) Manufacturing computers with the budget of 346 is impossible.

 

[Constraints]

1. init() is called in the beginning of each test case.

2. For each test case, stock() is called up to 4,000 times.

3. For each test case, order() is called up to 400 times.

 

[Input and Output]

As the input and output are processed in the provided code in the Main, they are not processed separately in the User Code.

The output result for the sample input is in the format of “#TC number result.” It is the correct answer if the result is 100; it is the wrong answer if it is 0.

 
* @brief: Sample Answer
 
 
* @copyright: All rights reserved (c) 2023 Samsung Electronics, Inc.
 
 
*/
 
 
#include <vector>
 
 
using namespace std;
 
 
#define MAX_POS  (2)
#define MAX_TYPE (3)
 
 
struct Result
{
    int mPrice;
    int mPerformance;
};
 
 
int CHARGE;
vector<pair<int, int>> parts[MAX_POS][MAX_TYPE];
 
 
void init(int mCharge)
{
    for (int i = 0; i < MAX_TYPE; i++)
    {
        parts[0][i].clear();
        parts[1][i].clear();
    }
    CHARGE = mCharge;
}
 
 
Result order(int mBudget)
{
    int h = 1000001;
    int l = 0; // the highest performance that knows what can be manufactured within the budget
    int Price = 0;
 
 
    while (h > l + 1)
    {
        int p[MAX_POS][MAX_TYPE];  // the lowest price of a component with the performance that exceeds the threshold in each warehouse
        int P[MAX_TYPE];           // the lowest price of a component with the performance that exceeds the threshold in all warehouses
        int m = (h + l) / 2;
        int Min;
 
 
        for (int pos = 0; pos < MAX_POS; pos++)
        {
            for (int type = 0; type < MAX_TYPE; type++)
            {
                Min = 1000000;
                for (auto& part : parts[pos][type])
                {
                    if (part.first >= m && part.second < Min)
                    {
                        Min = part.second;
                    }
                }
                p[pos][type] = Min;
            }
        }
 
 
        P[0] = min(p[0][0], p[1][0]);
        P[1] = min(p[0][1], p[1][1]);
        P[2] = min(p[0][2], p[1][2]);
 
 
        // Find the lowest price of a computer by comparing the combinations
        int price = min(min(p[0][0] + p[0][1] + p[0][2], p[1][0] + p[1][1] + p[1][2]), P[0] + P[1] + P[2] + CHARGE);
 
 
        // if a computer with the performance of ‘m’ or higher can be manufactured within the budget
        if (price <= mBudget)
        {
            l = m;
            Price = price;
        }
        else
        {
            h = m;
        }
    }
 
 
    return { Price, l };
}
 
 
int stock(int mType, int mPrice, int mPerformance, int mPosition)
{
    parts[mPosition][mType].emplace_back(mPerformance, mPrice);
    return parts[mPosition][mType].size();
}