Going to the movies is one of the favorite pastimes of many people. Most movie theaters try to attract large families by providing two kinds of tickets: single tickets that can be used by exactly one person and family tickets that allow entrance to one parent and all of his or her accompanying children. Needless to say that family tickets are always priced higher than single ticket, sometimes as high as ﬁve times the price of a single ticket.

Example of a family tree.

It is quite challenging for families to decide which ticket arrangement is most economical to buy. For example, the family depicted in the ﬁgure above has four ticket arrangements to choose from:

seven single tickets
two family tickets
one family ticket (for adam, bob and cindy) plus four single tickets for the rest
one family ticket (for bob and his four children) plus single tickets for the remaining two

Assignment

Write a function movieTickets that takes three arguments: i) an integer $$s \in \mathbb{N}_0$$ indicating the unit price of single tickets, ii) an integer $$f \in \mathbb{N}_0$$ indicating the price of family tickets and iii) the location of a text file that describes the composition of a family. Each line of the text file contains a list of one or more names, separated by spaces. The first name on a line is the name of a parent, and the other names are his or her accompanying children (a single name on a line represents a person going by him/herself). Names only contain lowercase letters and are unique: the name of a particular person appears at most twice, once as a parent and once as a child. The file contains at least one line. The function must return a tuple containing three positive integers that indicate the ticket arrangement that results in the minimal total cost: i) the number of single tickets, ii) the number of family tickets and iii) the total costs of all tickets. If there are multiple arrangements that result in the minimal total cost, the function must return the one having the least number of tickets.

Example

In the following interactive session, we assume the text files data01.txt¹, data02.txt² and data03.txt³ to be located in the current directory.

        >>> movieTickets(1, 3, 'data01.txt')
(2, 1, 5)
>>> movieTickets(1, 2, 'data02.txt')
(4, 0, 4)
>>> movieTickets(1, 3, 'data03.txt')
(0, 1, 3)