| Problems | Submit | Runs Status | Rank List | Statistics | Clarifications |
| Problems | Submit | Runs Status | Rank List | Statistics | Clarifications |
A favorite pastime for big families in Acmestan is going to
the movies. It is quite common to see a number of these
multi-generation families going together to watch a movie.
Movie theaters in Acmestan have two types of tickets: A
single ticket is for exactly one person while a family ticket
allows a parent and their children to enter the theater.
Needless to say, a family ticket is always priced higher than
a single ticket, sometimes as high as five times the price of
a single ticket.
It is quite challenging for families to decide which ticket arrangement is most economical to buy.
For example, the family depicted in the figure on the right has four ticket arrangements to choose
from: Seven single tickets; Two family tickets; One family ticket (for adam, bob, cindy) plus four
single tickets for the rest; Or, one family ticket (for bob and his four children) plus single tickets
for the remaining two.
Write a program to determine which ticket arrangement has the least price. If there are more
than one such arrangement, print the arrangement that has the least number of tickets.N1 N2 N3 ... Nk
where N1 is the name of a parent, with N2 ... Nk being his/her children. Names are all lower-case letters, and no longer than 1000 characters. No parent will be taking more than 1000 of their children to the movies :-). Names are unique, the name of a particular person will appear at most twice: Once as a parent, and once as a child. There will be at least one person and at most 100,000 people in any test case. The end of a test case is identified by the beginning of the following test case (a line made of two integers.) The end of the last test case is identified by two zeros.1 3 adam bob cindy bob dima edie fairuz gary 1 2 john paul george ringo 1 3 a b c 0 0
1. 2 1 5 2. 4 0 4 3. 0 1 3