Untitled

[Description]   

You would like to develop a program to estimate the production output of a semiconductor manufacturing line.

The manufacturing line consists of N steps and has one warehouse.

 

[Fig. 1] below shows a semiconductor manufacturing line that is made of total 3 steps and a warehouse.

In the course of production (i.e. the 3 steps) and at the warehouse, semiconductors are carried, processed and transported in the unit called ¡®lot¡¯.

The manufacturing line illustrated in [Fig. 1] has 8 lots.

 




[Fig. 1]

 

Strictly by the production plan, raw materials are brought to Step#0 on an irregular basis and stand by there.

The production completes when the lot of semiconductors is processed in all the N steps of the manufacturing line, in order from Step#0, Step#1, ¡¦, to Step#N-1.

In other words, only after the lot of semiconductors is processed in the final Step#N-1, it can be transported to the warehouse.

 

Each step has at least one tool.

Each tool can be assigned to only one step.

In [Fig. 1], there are 2 tools in Step#2 (i.e. Tool#1, Tool#5).

 

Each tool can process only ONE lot of semiconductors.

In other words, while one lot of semiconductors is being processed by a tool, another lot of semiconductors CANNOT be processed by that tool.

In the manufacturing line illustrated in [Fig. 1], the both tools in Step#2 are processing one lot of semiconductors each (i.e. Lot#B, Lot#C).

Therefore until this process is done, Lot#E must stand by in Step#2. 

Also note that the lot of semiconductors being processed CANNOT be moved to the other place until the current process completes.

 

Each tool has different performance, so they can vary in the amount of time required to process a single lot of semiconductors (Process Time, PT).

The lot of semiconductors processed by a tool in one step is transported to the next.

And depending on the condition of the tool in the next step, one of the following scenarios takes place:

1)    Transported to the next step and immediately processed there if there is an available tool (i.e. the tool that is not processing anything).

If the tool in the next step has completed the processing of the previously assigned lot upon the arrival of a new lot, it is considered available.

2)    Transported to the step after next and stands by there if there is no available tool in the next step.

In this case, it should wait until any one of the tools completes the processing of the other lots.

When such time arises, it should be transported to and processed by that tool.

 

In order to most efficiently utilize the process capability of each tool, 
a lot should be transported to and processed by the tool with the shortest PT
if there are more than 1 available tool in the next step

 

The transportation time of lots is set 0 given that it is extremely short compared to the processing time.

e.g.

Transported to Tool#1 tool while standing by in Step#2;

Transported to Step#2 to stand by;

Transported from Tool#0 in Step#0 to Tool#2 in Step#1;

Transported from Tool#5 in the final step to the warehouse; etc

 

Given that the semiconductor manufacturing line is run under the above condition, write a program that estimates and returns
the total number of lots standing by AND being processed in each step of the manufacturing line,
and the number of lots stored in the warehouse.

 

The following are the API to be implemented.

¡Ø The function signature below is based on C/C++. As for Java, refer to the provided Solution.java and UserSolution.java.

void init(int N)

A function called once in the beginning of each test case for initialization and it tells the total number of steps.

 

Parameters

N: Number of steps (3 ¡Â N ¡Â 100)

void setupTool(int T, int stepNo[5000], int procTime[5000])

A function called once in the beginning of each test case after init call.

It tells the total number of tools, plus the step number (Step#) and the process time of each tool. The number of tools in each step in a test case varies.

 

Parameters

T: Total number of tools in every step (3 ¡Â T ¡Â 5,000)

stepNo: Array of ¡°Step#¡±s assigned to each tool; its length is T (0 ¡Â ¡°Step#¡± < N)

procTime: Array of PT of each tool; its length is T (5 ¡Â PT ¡Â 6,000)
  ¡Ø stepNo and procTime both use the parameters from 0 to T-1.

void addLot(int time, int number)

A function that adds ¡°number¡± of lots to Step#0 upon ¡°time¡± point.

 

Parameters

time: Timestamp of the point when the lot is added to Step#0 (0 ¡Â time ¡Â 100,000)

number: Number of lots added to Step#0

int simulate(int time, int wip[100])

A function that counts the number of lots standing by or being processed in each of N steps from Step#0 to Step#N-1 to store it in the wip array and then returns the number of lots stored in the warehouse.

 

Parameters

time: Timestamp of the point when the number of lots in the manufacturing line and in the warehouse is estimated (0 ¡Â time ¡Â 100,000).

wip: Stores and returns the number of lots in each step of the manufacturing line.

The number of lots in each step refers to the total number of lots standing by and being processed.

The number of lots in Step#0 is stored in wip[0].

The number of lots in Step#N-1 is stored in wip[N-1].

Since wip[N] and the results following it are not evaluated in the test, you do not need to store them.

 

Return

The number of lots stored in the warehouse

 

¡Ø     As for the lot processed completely at the point of time when this function is called, you should return the information about its condition, either standing by for the next step or being transported to the tool, as wip array and return value.

[Table 1]

 

[Example]

Let¡¯s take a look at the case where the functions are called as in [Table 2] below.

Order

Function

Return Value

Figure

1

init (N=3)

 

 

2

setupTool(T=6, stepNo={0, 2, 1, 1, 0, 2},
procTime={50, 60, 60, 40, 70, 60})

 

 

3

addLot(time=0, number=3)

 

[Fig. 2]

[Fig. 3]

4

simulate(time=70, wip[ ])

return=0, wip[ ]={1, 2, 0, ¡¦}

[Fig. 4]

5

addLot(time=90, number=3)

 

[Fig. 5]

6

simulate(time=100, wip[ ])

return=0, wip[ ]={3, 2, 1, ¡¦}

[Fig. 6]

7

simulate(time=140, wip[ ])

return=0, wip[ ]={3, 0, 3, ¡¦}

[Fig. 7]

8

simulate(time=150, wip[ ])

return=1, wip[ ]={2, 1, 2, ¡¦}

[Fig. 8]

[Table 2]

 

There are 3 steps and 6 tools.

Those 6 tools are installed in the steps from Step#0 to Step#2.

 

When 3 lots, Lot(A, B, C), are added to Step#0 at time0, the two lots start being processed by Tool#0 and Tool#4.

One lot stands by as there is no available tool. [Fig. 2] below illustrates this scenario

.




[Fig. 2]

 

 

As PT of Tool#0 is 50, Lot#A is transported to Step#1 at Time50.

Among the available tools, Tool#3 has the shortest PT, so Lot#A gets processed by Tool#3.

At the same time, Lot#C gets processed by Tool#0.

 




[Fig. 3]

 

 

At Time70, Lot#B completely processed by Tool#4 gets processed by Tool#2 in Step#1.

Therefore, the number of lots in each of Step#0, Step#1 and Step#2 of the manufacturing line,
plus in the warehouse at Time70 is 1, 2, 0, and 0, respectively (refer to [Fig. 4]). 

 




[Fig. 4]

 

 

At Time90, Lot#A processed completely by Tool#3 in Step#1 is transported to Step#2 and then starts being processed by available Tool#1.

At the same time, 3 lots of Lot(D, E, F) are added to Step#0.

Tool#4 that has not been processing any lot starts processing Lot#D.




[Fig. 5]

 

 

Lot#C processed completely by Tool#0 at Time100 is transported to Step#1 and gets processed by Tool#3.

Lot#E that has been standing by in Step#0 starts being processed by Tool#0 that is now available.

 




[Fig. 6]

 

 

Lot#B processed completely by Tool#2 at Time130 is transported to Step#2 and gets processed by Tool#5.

Lot#C processed completely by Tool#3 at Time140 is transported to Step#2 and stands by there.

Therefore, the number of lots in each of Step#0, Step#1 and Step#2 of the manufacturing line,
plus in the warehouse at Time140 is 3, 0, 3, and 0, respectively (refer to [Fig. 7]).

 




[Fig. 7]

 

 

At Time150, Lot#A is processed completely by Tool#1 and transported to the warehouse.

At the same time, Lot#C that has been standing by in Step#2 gets processed by Tool#1.

Lot#E completely processed by Tool#0 gets processed by Tool#3, which has the shortest PT in Step#1.

Lot#F that has been standing by in Step#0 gets processed by Tool#0.

Therefore, the number of lots in each of Step#0, Step#1 and Step#2 of the manufacturing line,
plus in the inventory warehouse at Time150 is 2, 1, 2, and 1, respectively (refer to [Fig. 8]). 

 




[Fig. 8]

 

 

[Constraints]

1. The number of steps in the manufacturing line, N, is greater than or equal to 3, but not over 100. (3 ¡Â N ¡Â 100)

2. In each test case, setupTool( ) is called only ONCE after init( ) is called.

3. Each step has at least 1 tool, but no more than 50.

4. The lot of semiconductors is processed in ascending order of step numbers (you may NOT change the process order).

5. The total number of lots does NOT exceed 100,000.

6. When there are 2 or more available tools, choose the tool with the shortest PT.

7. addLot( ) and simulate( ) are NEVER called with same ¡°time¡± point.
The time of addLot( ) and simulate( ) is an ascending number.

8. If the tool has completed the lot processing at the time when the simulate( ) is called,
you should return the result at the point after the lot is transported to the next step.

9. In each test case, only up to 1,000 calls can be made for all functions combined.

 

 

[Input and Output]

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

The correct output for the sample input will be shown as below.

#1 100

#2 100

#3 100

#4 100

#5 100



#define MAX_N    100
#define MAX_TOOL 50
  
#define MAX_NUM_TOOLS MAX_N*MAX_TOOL
#define MAX_TIME_RANGE 100001
#define NULL 0
  
typedef struct _PROCESS_TOOL{
    int pTime;
    int step_id;
    struct _PROCESS_TOOL *next;
}PROCESS_TOOL, *pProcessTool;
  
PROCESS_TOOL tools[MAX_NUM_TOOLS];
PROCESS_TOOL processLine[MAX_N];
  
pProcessTool timeRange[MAX_TIME_RANGE];
  
int cnt[MAX_N + 1][2];
  
int stepQueue[MAX_N];
  
int n;
int currentTime;
  
  
void init(int N) {
    n = N;
    for (register int i = 0; i < MAX_N; i++){
        processLine[i].next = NULL;
        cnt[i][0] = 0;
        cnt[i][1] = 0;
    }
  
    for (register int i = 0; i < MAX_TIME_RANGE; i++){
        timeRange[i] = NULL;
    }
    currentTime = 0;
  
}
  
void setupTool(int T, int stepNo[5000], int procTime[5000]){
  
    for (register int i = 0; i < T; i++) {
        tools[i].pTime = procTime[i];
        tools[i].step_id = stepNo[i];
        tools[i].next = NULL;
  
        pProcessTool curr = &processLine[stepNo[i]];
  
        while (curr->next != NULL && curr->next->pTime<procTime[i]) {
            curr = curr->next;
        }
        tools[i].next = curr->next;
        curr->next = &tools[i];
    }
}
  
void processLots(int time) {
  
    pProcessTool freeTool;
    pProcessTool curr;
    int stepCtr;
  
    while (currentTime <=time){
  
        if (timeRange[currentTime]){
            stepCtr = 0;
  
            while (timeRange[currentTime]){
  
                freeTool = timeRange[currentTime];
                timeRange[currentTime] = freeTool->next;
  
                cnt[freeTool->step_id][1]--;
                cnt[freeTool->step_id + 1][0]++;
  
                stepQueue[stepCtr++] = freeTool->step_id;
                stepQueue[stepCtr++] = freeTool->step_id + 1;
  
                curr = &processLine[freeTool->step_id];
  
                while (curr->next != NULL && curr->next->pTime < freeTool->pTime){
                    curr = curr->next;
                }
                freeTool->next = curr->next;
                curr->next = freeTool;
            }
  
  
            for (int i = 0; i < stepCtr; i++){
                int stpID = stepQueue[i];
  
                while (processLine[stpID].next != NULL && cnt[stpID][0]){
                    curr = processLine[stepQueue[i]].next;
                    processLine[stepQueue[i]].next = curr->next;
  
                    curr->next = timeRange[currentTime + curr->pTime];
                    timeRange[currentTime + curr->pTime] = curr;
  
                    cnt[stpID][0]--;
                    cnt[stpID][1]++;
                }
            }
        }
        currentTime++;
    }
}
  
void addLot(int time, int number) {
  
    int pendingCount = number;
    processLots(time);
    pProcessTool curr;
  
    while (processLine[0].next != NULL && n > 0) {
        curr = processLine[0].next;
        processLine[0].next = curr->next;
  
        curr->next = timeRange[time + curr->pTime];
        timeRange[time + curr->pTime] = curr;
  
        pendingCount--;
        cnt[0][1]++;
    }
  
    cnt[0][0] += pendingCount;
}
  
  
int simulate(int time, int wip[MAX_N]) {
  
    processLots(time);
  
    for (int i = 0; i < n; i++){
        wip[i] = cnt[i][0] + cnt[i][1];
    }
    return cnt[n][0];
}