UTS Programming Competition 2016 Problem 3

From ProgSoc Wiki

Jump to: navigation, search

This is a part of the UTS Programming Competition 2016 Problem Set.

Problem 3: WidgCo

Run time limit: 2 seconds

Problem Description

WidgCo is a company that produces various widgets.

Write a program that will assist the stock manager in determining what components need to be ordered from suppliers.

Data Specification


Input consists of two parts for a single test case.

First, the catalogue of widgets produced by the factory and their components. A number is given on its own line indicating how many different widgets are produced. For each widget in the catalogue, there will be a line starting with an integer indicating how many different components are required, and a widget name. Each component then appears on a line describing the number of that component required to make a single widget, and the name of that component. Note that widget and component names are each a single word with an initial capital letter followed by a number. They all have unique letters.

Second, the orders for widgets. A number is given indicating the number of order lines to follow. Each has a number for the number of widgets required, and a widget name.


Output consists of the components that should be purchased from WidgCo's suppliers to fill the orders for the given test case. Components to be ordered are to be given in alphabetical order. Each component to order must appear on its own line, with the number to be ordered followed by the name of the component. Note that if a component should not be ordered (0 are required), your program must not include that component in the output.

Sample Input

3 X20
2 A4
3 B3
4 C6
2 Y900
4 C6
5 D1
2 X20
3 X20
2 Y900
1 Y900

Sample Output

10 A4
15 B3
32 C6
15 D1


Put your solutions here!

Luke's Java solution

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;

class WidgCo {

   public static void main(String[] args) {
       (new WidgCo()).solve();

   private void solve() {
       Scanner in = new Scanner(System.in);

       // Read in the catalogue
       int widgetCount = in.nextInt();
       ArrayList<String> widgetNames = new ArrayList<String>();
       int[][] widgetComponentCounts = new int[widgetCount][];
       int[][] widgetComponentIndicies = new int[widgetCount][];
       ArrayList<String> componentNames = new ArrayList<String>();
       for (int widget = 0; widget < widgetCount; ++widget) {
           int componentCount = in.nextInt();
           widgetComponentCounts[widget] = new int[componentCount];
           widgetComponentIndicies[widget] = new int[componentCount];
           String widgetName = in.next();
           for (int component = 0; component < componentCount; ++component) {
               int componentForWidgetCount = in.nextInt();
               widgetComponentCounts[widget][component] = componentForWidgetCount;
               String componentForWidgetName = in.next();
               int componentForWidgetIndex = componentNames.indexOf(componentForWidgetName);
               if (componentForWidgetIndex == -1) {
                   componentForWidgetIndex = componentNames.indexOf(componentForWidgetName);
               widgetComponentIndicies[widget][component] = componentForWidgetIndex;

       // Read in the orders
       ArrayList<String> requiredComponentNames = new ArrayList<String>();
       for (String componentName : componentNames)
       int[] requiredComponentCounts = new int[componentNames.size()];
       int orderCount = in.nextInt();
       for (int order = 0; order < orderCount; ++order) {
           int widgetForOrderCount = in.nextInt();
           String widgetForOrderName = in.next();
           int widgetForOrderIndex = widgetNames.indexOf(widgetForOrderName);
           for (int component = 0; component < widgetComponentCounts[widgetForOrderIndex].length; ++component) {
               int requiredComponentIndex = requiredComponentNames.indexOf(
               requiredComponentCounts[requiredComponentIndex] +=
                   widgetForOrderCount * widgetComponentCounts[widgetForOrderIndex][component];

       // Print out the supplier order
       for (int i = 0; i < requiredComponentNames.size(); ++i)
           if (requiredComponentCounts[i] != 0)
               System.out.println(requiredComponentCounts[i] + " " + requiredComponentNames.get(i));
Personal tools