## CCC '05 S4 - Pyramid Message Scheme

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 256M

Problem type
##### Canadian Computing Competition: 2005 Stage 1, Senior #4

Spamway Inc. maintains a network of zombie computers to solicit and collect orders for its various fine products. Each zombie computer is responsible for zero or more subordinate zombies that it coordinates in these activities.

Spamway uses a simple communication strategy among its zombies for transmitting solicitations and receiving orders. Each solicitation originates at Spamway's head zombie, which then communicates it to each of its subordinates in turn, waiting to collect orders from one subordinate before proceeding to the next. Each subordinate employs the same strategy - it sends to and receives from each of its subordinates in turn.

For example, suppose that Home has two subordinate zombies named Alfred and Betty; Alfred's subordinates are named Cindy and Dennis; Betty has no subordinates. This organization is pictured below.

            Cindy
/
Alfred
/      \
Home        Dennis
\
Betty

Home first sends to Alfred; Alfred then sends to Cindy; Cindy responds to Alfred; Alfred sends to Dennis; Dennis responds to Alfred; Alfred responds to Home; Home sends to Betty; Betty responds to Home.

Each message takes seconds to be delivered. So the example given above would be completed in seconds. You have been retained by Spamway, who will pay you handsomely (in Spam Bucks which may be redeemed for any of their valuable products) to help them reduce the time necessary to solicit and collect orders. In particular, Spamway is considering a new strategy in which each zombie sends out messages to each of its subordinates and waits for their responses only after all messages have been sent.

Spamway's network administrator has captured a chronological list of the name of the recipient of each message involved in a particular solicitation. For the example above, using the slow strategy, this list would be: Alfred, Cindy, Alfred, Dennis, Alfred, Home, Betty, Home. (Note that messages at seconds per message is seconds.)

Using the new and improved strategy, Home sends to Alfred and Betty simultaneously, Alfred sends to Cindy and Dennis at the same time as Betty is responding, Cindy and Dennis respond simultaneously to Alfred and finally Alfred responds to Home. Using the new strategy, Spamway needs only seconds to accomplish the communication that takes seconds using the old strategy. Thus, Spamway can send twice as many solicitations and make twice as much money.

#### Input Specification

As input, you are given lists of names describing the order that messages are received using the old Spamway strategy. The input contains the integer , followed by message lists. Each list begins with an integer, , identifying the number of message recipients in the list, followed by lines, each containing the name of a message recipient.

#### Output Specification

For each list you are to print out a single integer indicating the amount of time in seconds that Spamway saves.

#### Sample Input

1
8
Alfred
Cindy
Alfred
Dennis
Alfred
Home
Betty
Home

#### Sample Output

40

• commented on May 28, 2022, 5:25 a.m.

Wow I really didn't read the input specification carefully...

• commented on Nov. 29, 2021, 10:14 p.m.

Always read the output specification.... Had a working solution but didn't do subtraction lol

• commented on March 28, 2020, 12:19 a.m. edited

Nevermind, the question requires output for multiple lists, eliminating the need for more testcases.

• commented on Nov. 2, 2017, 2:14 a.m. edited

What are the limits on ?

• commented on Nov. 2, 2017, 5:01 p.m.

, and .

• commented on Oct. 10, 2016, 11:11 p.m.

It might be helpful to clarify that the root node will not always be named "Home", even though this is never confirmed nor denied in the problem statement.

• commented on Feb. 13, 2018, 1:24 p.m.

For test 5/10, its "home" not "Home"... just do the last element. Debugging for EVER.

• commented on March 27, 2018, 6:41 p.m.

It's not even "home" nor "Home" for the last two cases. Don't waste time like me, who tried to change all uppercase letters to lowercase.

• commented on Jan. 17, 2018, 5:26 a.m.