SPOJ.com - Problem ANARC07G

ANARC07G - Let go to the movies

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 ﬁve 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 ﬁgure 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.

Input

Your program will be tested on one or more test cases. The ﬁrst line of each test case includes two positive integers (S and F) where S is the price of a single ticket and F is the price of a family ticket. The remaining lines of the test case are either the name of a person going by him/herself, or of the form:

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 identiﬁed by the beginning of the following test case (a line made of two integers.) The end of the last test case is identiﬁed by two zeros.

Output

For each test case, write the result using the following format:

k. NS NF T

Where k is the test case number (starting at 1) NS is the number of single tickets, NF is the number of family tickets, and T is the total cost of tickets.

Sample

Input
1 3
adam bob cindy
bob dima edie fairuz gary
1 2
john
paul
george
ringo
1 3
a b c
0 0

Output
1. 2 1 5
2. 4 0 4
3. 0 1 3

Submit solution!

Added by:	psetter
Date:	2009-07-05
Time limit:	1s-1.5s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:	ANARC 2007

hide comments

2023-08-26 13:21:33
if you get TLE in c++, jonathanasdf in vjudge.net has implemented the best solution for taking the input.
Also ignore this question, because problems like SPOJ VOCV,PT07X ( both are tree vertex cover problems with VOCV asking number such minimal vertex cover additionally ) have same concept of implementation.

2021-03-30 09:07:56
Will there be single big family or there can be multiple broken families? ....I mean is there a name who is super-parent of all names?

2020-10-20 11:02:12
Arggh.. reading input is pure kill joy.
Hope this helps someone -
100 20
j
p
k
r
0 0
1. 0 4 80

Last edit: 2020-10-20 11:11:09

2020-07-23 16:23:05
The problem statement should specify if a person could buy 1 single ticket and his parent buy another family ticket. Also, taking the input is such a burden.

2016-10-17 01:07:40
Can one person buy 2 tickets?

2016-06-22 23:06:29
dp solution would be O(2^(N+1) log N) + input time.

2016-01-26 08:18:59 birdie
tle for top down? or tle due to java? :/

2015-08-07 18:17:10 Ajey Golsangi
Reading the input is very time consuming :( .

2015-08-01 23:03:31 Mauro Persano
input:
1 2
a b c d e f g
b h i j k l m
0 0

output:
1. 0 2 4

Last edit: 2015-08-01 23:20:49

2010-08-20 14:21:14 Luka Hrabar
I didn't have problems with empty lines or double spaces, but the lines finish with '\r\n'.