50101. Component and Parts

I'm a slow walker, but I never walk backwards.

Task Description

You are given a set of $N$ components and parts. The difference between a component and a part is that a component consists of other components and parts, and a part is simply a part. Note that the definition of component is recursive, i.e., we use component to define component. However, eventually every component consists of only parts. Now we will be given the price of parts, and we want to compute the price of every component, which is simply the sum of prices of all its parts. Write a function to calculate the price of components, and print the unit price of all components and parts.

Here are examples of parts and components.

part price
CPU 1500
memory 383
power 463
device 833
network 200
component components price
PC 1 CPU, 1 memory, 1 power, 1 device 3179
ClusterSystem 4 PC, 1 network 12916

We define component/part as follow. All parts and components are stored in a array and have indices from $0$ to $N-1$. Note that the components and parts are mixed in this array. If a ComponentPart has numComponent set to $0$, then it is a part, otherwise it is a component, and the indices of its components and parts are stored in the componentPartList array.

1
2
3
4
5
6
typedef struct{
    char name[MAXLENGTH];
    int numComponent;
    int componentPartList[MAXCOMPONENT];
    int price;
}ComponentPart;

The prototype of the function you need to implement is as follows:

1
void findPrice(int N, ComponentPart list[]);

And you may use the following main function to test your function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<stdio.h>
#include"componentPart.h"
int main(){
    int N;
    scanf("%d",&N);
    ComponentPart list[N];
    for(int i=0;i<N;i++){
        scanf("%s%d",list[i].name,&list[i].numComponent);
        if(list[i].numComponent){
            for(int j=0;j<list[i].numComponent;j++)
                scanf("%d",&list[i].componentPartList[j]);
            list[i].price=0;
        }
        else
            scanf("%d",&list[i].price);
    }
    findPrice(N,list);
    return 0;
}

The componentPart.h is as follow:

1
2
3
4
5
6
7
8
9
10
11
12
#ifndef _COMPONENTPART_H
#define _COMPONENTPART_H
#define MAXLENGTH 16
#define MAXCOMPONENT 64
typedef struct{
    char name[MAXLENGTH];
    int numComponent;
    int componentPartList[MAXCOMPONENT];
    int price;
}ComponentPart;
void findPrice(int N,ComponentPart list[]);
#endif

Subtask

  • 10 points: There are no components -- everything is a part.
  • 30 points: Every component has only parts and no components.
  • 60 points: Nothing is guaranteed.

Input Format

The input contains only one test case. The first line contains an integer $N$, where $N$ is the number of components and parts. For each components and parts, there are two lines. The first line contains a string $U$ and an integer $T$, where $U$ is the unique name and $T$ is the number of its component parts. If $T$ is 0, the second line contains an integer $P$, which is the component price. Or the second line contains $T$ integers, and each integer is its component part index.

  • $N \leq 128$.
  • $T \leq 64$.
  • $P \gt 0$.
  • The length of name is less than $16$.

Output Format

Print the names and prices of components and parts in alphabetic (dictionary) order according to their names. For each component and part, print its name and price in one line.

Sample Input 1

4
CPU 0
1500
memory 0
383
power 0
463
device 0
833

Sample Output 1

CPU 1500
device 833
memory 383
power 463

Sample Input 2

5
CPU 0
1500
memory 0
383
power 0
463
device 0
833
PC 4
0 1 2 3

Sample Output 2

CPU 1500
PC 3179
device 833
memory 383
power 463

Sample Input 3

7
ClusterSystem 5
6 6 5 6 6
CPU 0
1500
memory 0
383
power 0
463
device 0
833
network 0
200
PC 4
1 2 3 4

Sample Output 3

CPU 1500
ClusterSystem 12916
PC 3179
device 833
memory 383
network 200
power 463

Discussion