Problem K
Breadboarding
Recently Theta took up breadboarding. Breadboarding is the prototyping of electronic circuits on solderless prototype boards, called breadboards for their looks. Electronic components such as integrated circuits, resistors, transistors, diodes, capacitors, and others are pushed into the holes to secure them to the board. Inside the board the holes are connected in groups.
On a typical breadboard, there are $2 \times 30 = 60$ groups of $5$ connected pin holes, along with larger connected rails on the sides for power and ground, which are typically connected to the positive and negative ends of a power source.
In this problem, you are given a description of an electronic circuit and are asked to compute
-
the number of holes needed in the power and ground rail
-
the number of groups needed (this determines the size of the breadboard needed)
-
a sorted parts list with all components
The electronic circuit consists of components with one or more pins. We denote pins by combining the abbreviation of the part to which they belong with a unique identifier such as a number or letter combination.
For instance, in Figure 1, Resistor R7 (shown near the center of the diagram) has two pins, R7-W and R7-E (the W and E identifiers are not shown in the circuit diagram, we use W for West and E for East based on the layout in the circuit diagram to distinguish the two pins). The R7-E pin is connected to integrated circuit U1B pin 6 (denoted U1-6 in the sample input) and also connected to the R10-W and C9-W pins of R10 and C9, respectively. The other pin of R7, which is R7-W, is connected to C7-E which is a pin belonging to capacitor C7. Thus, pins R10-W, C9-W, R7-E, and U1-6 form a group of connected pins. Membership in a group of connected pins is transitive: if $a$ is connected to $b$, and $b$ is connected to $c$, then $a$, $b$, and $c$ are part of the same connected group.
Each group of connected pins, with the exception of Power and Ground, must be placed into a group of connected holes on the board. For instance, if each hole group has 5 holes, 5 connected pins can be placed into it (we ignore geometric layout constraints for this problem and assume that each part has pins that are long enough to reach any available hole). To connect $6$ pins, however, $2$ groups are needed. In addition, these groups must be connected with a jumper wire, which takes up one hole in each group. Thus, with a board where holes are in groups of $5$, up to $4 + 4 = 8$ pins can be placed in $2$ groups, $4 + 3 + 4 = 11$ pins in $3$ groups, $4 + 3 + 3 + 4 = 14$ pins in $4$ groups, and so on.
![\includegraphics[width=0.8\textwidth ]{cdm324circuit.png}](/problems/vths21.breadboarding/file/statement/en/img-0002.png)
Input
The input consists of a single test case. The first line contains two integers $n$ and $g$ ($2 \le n \le 10\, 000$, $3 \le g \le 10$). $n$ is the number of listed connections that follows, $g$ is the number of holes in each group. (A standard breadboard would have $g=5$, but for this problem $g$ is an input variable.)
The following $n$ lines contain pairs of pins that must be connected. Each line contains two pin specifications separated by a space. A pin specification consists of either the words Power, Ground, or a Part-and-Pin identifier. The order of the two pin specifications on a line may be arbitrary. Part-and-Pin identifiers consist of a part component and a pin component, separated by a hyphen. The part component starts with one or more uppercase English letters, followed by one or more digits (e.g., R10). The pin component appears after the hyphen and may consist of any sequence of uppercase letters or digits. Part-and-Pin identifiers consists of at most $10$ characters in total. You may assume at least one pin is connected to the Power and Ground rails, respectively.
Output
First, output $3$ lines:
Need <P> holes on power rail Need <G> holes on ground rail Need <H> additional <g>-hole groups
where <P> is the number of holes needed for components that have one of their pins connected to the power rail, <G> is the number of holes needed for components that have one pin connected to the ground rail, and <H> is the total number of hole groups needed to hold all pins that aren’t connected to power or ground, accounting for any jumper wires that may be needed to connect hole groups when more than $g$ pins need to be connected. The value <g> must be equal to the number $g$ in the input.
Next, your program should output the part list in the format
Part <P> has <p> pins
where <P> is the name of the part, and <p> is the number of pins this part has. Sort the list by the letter portion of the part names, with ties broken by the number component of the part name using numerical comparison, (e.g. R2 should be listed before R10).
| Sample Input 1 | Sample Output 1 |
|---|---|
60 4 J1-3 Power J1-2 R1-N J1-2 C1-W C1-2 R2-S C1-2 R3-N C1-2 C3-S C3-S Q1-2 R2-N C3-N C3-N Q1-1 Q1-1 RV1-1 RV1-3 C2-N R4-S RV1-3 R4-N Power C4-N Power RV1-2 U1-3 U1-2 C5-N C5-N C6-W C5-S R5-N C6-W R6-W R6-E C6-E C6-E U1-1 C6-E C7-W C7-E R7-W R7-E U1-6 R7-E R10-W R10-W C9-W C9-E R10-E U1-7 R10-E R10-E R11-W U1-5 R8-S R8-S R9-N R9-N C8-N R8-N Power R11-E U1-12 U1-12 R14-W U1-13 R13-N R13-S Ground R13-N R12-S R12-N Power R14-E U1-14 R14-E R15-W R15-W U1-10 U1-11 Ground U1-4 Power U1-9 U1-8 U1-8 R16-W R16-E D1-N D1-S Ground R15-E J2-2 J2-1 Ground J2-3 Power C2-S Ground C4-S Ground J1-1 Ground R1-S Ground R3-S Ground Q1-3 Ground R5-S Ground C8-S Ground R9-S Ground |
Need 7 holes on power rail Need 13 holes on ground rail Need 19 additional 4-hole groups Part C1 has 2 pins Part C2 has 2 pins Part C3 has 2 pins Part C4 has 2 pins Part C5 has 2 pins Part C6 has 2 pins Part C7 has 2 pins Part C8 has 2 pins Part C9 has 2 pins Part D1 has 2 pins Part J1 has 3 pins Part J2 has 3 pins Part Q1 has 3 pins Part R1 has 2 pins Part R2 has 2 pins Part R3 has 2 pins Part R4 has 2 pins Part R5 has 2 pins Part R6 has 2 pins Part R7 has 2 pins Part R8 has 2 pins Part R9 has 2 pins Part R10 has 2 pins Part R11 has 2 pins Part R12 has 2 pins Part R13 has 2 pins Part R14 has 2 pins Part R15 has 2 pins Part R16 has 2 pins Part RV1 has 3 pins Part U1 has 14 pins |
