Pro.ID22399 TitleLet's Go to the Movies Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22399 AC0 Submit0 Ratio- 时间&空间限制描述
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. 输入Your program will be tested on one or more test cases. The first 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 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. 输出Description
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. Input Your program will be tested on one or more test cases. The first 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 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. 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,) ' ' is a single space, 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 Sample Output 1. 2 1 5 Source 样例输入1 3 样例输出1. 2 1 5 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-5 02:41 , Processed in 0.038812 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
