Component and Parts

[littlehug]

Write a function to find the price of components and parts.

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	CPU	memory	power	device	network
price	1500	383	463	833	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 component are stored in a array and have indice from 0 to N-1. Note that the components and part 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.

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:

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

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

#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:

#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 <= 128,T <= 64.
• Name length 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