Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
I hate SPAM, but some people love it
Time Limit: 1000MSMemory Limit: 10000K
Total Submissions: 304Accepted: 135


Nowadays, unfortunately, SPAM messages are becoming more and more common. Some of them may have a multiplicative effect since they ask you to forward them to all your friends. Some SPAM messages wish good luck, others promise you will become rich, and others just remind you how important it is to tell your friends that you care for their friendship. Here is an example of a SPAM:

From: Alice
To: Bob, Mary, Julia, Paul
Hi, this is a good luck email. I wish you become a millionaire, but
that is up to you. If you
* send this email to 10 or more people you will be a millionaire
* send this email to 5 or more people you will be rich
* send this email to less than 5 people you will be poor
As I said, it is up to you. Write your email and be rich! :-)


People usually react in two different ways when they receive a SPAM:
1.They discard the message immediately without even reading it (they hate SPAM);
2.They forward the message to everyone they know (they love SPAM).
For this problem, we will assume everyone loves SPAM, but one never forwards the same message twice. Each SPAM message has a different effect based on the number of friends you forward the message to. For example: a SPAM message could tell that you will be poor if you send the message to 5 friends, but you will be the rich if you send to 10, and you will be the richest man in the world if you send it to 20 friends, and so on.
We will consider only SPAM messages similar to the example above. More specifically, a SPAM message will define two threshold values T1 and T2 and three attributes A1, A2 and A3. A person acquires one of the three attributes depending on the number of messages forwarded for that specific SPAM. If a person forwards T messages and T < T1 then her/his attribute is A1, if T1 <= T < T2 then her/his attribute is A2, otherwise her/his attribute is A3.
You will be given the names of a group of people, and for each person in the group, the set of friends she/he knows the email address. You will also be given a set of distinct SPAM messages, and for each SPAM message its threshold values and attributes, and the information about which person started it.
You have to write a program that determines, for each person in the given group, which attributes she/he acquired, based on all the SPAM they forward.

You may assume that the SPAM originator will have at least one friend (in other words, she/he will send at least one message), and a person will not send messages to herself.


Your program should process several test cases. The first line of a test case contains an integer N indicating the number of persons in the group (2 <= N <= 20). In the input, a person is identified by an integer from 1 to N. The following N lines contain each a list of friends of each person (the i-th line contains the list of friends of person number i). The list of friends of person i describes the friends person i knows the email address, and consists of a list of integers Fi (1 <= Fi <= N, Fi != i) terminated by the value 0 (zero). Following the list of friends comes the description of the SPAM messages (there will be at most 100 messages). Each description appears in a different line. The description consists of an integer P identifying the person who is the SPAM originator (2 <= P <= N); two integers T1 and T2 representing the threshold values; and the three attributes A1, A2 and A3 (each attribute is a word of no more than 20 letters). The SPAM list ends with a line containing only the value 0 (zero). The following N lines contain each a name, which is single word with no more than 20 letters. The name in the ith line is the name of person number i. The end of input is indicated by N = 0.


For each test case your program should output a list of names followed by the attributes they acquired.Your program should write the persons names in the order they appear in the input, followed by ':' and by a space, followed by their attributes according to the SPAM they sent. Attributes should be written in the order they appear in the input; each attribute should be followed by a space.

Sample Input

2 3 0
1 3 5 4 0
5 0
4 1 0
1 2 4 poor rich millionaire
5 3 10 sad normal happy
2 0
1 3 0
1 2 4 0
1 2 3 5 0
1 2 3 4 0
1 3 4 0
1 2 4 red green blue
1 2 4 dumb normal smart
6 3 5 ugly bad good
0 0

Sample Output

Bob: rich sad
Paul: millionaire normal
Mary: poor sad
Alice: poor sad
Julia: rich sad
Peter: red dumb ugly
Paul: green normal ugly
Victoria: green normal bad
John: blue smart bad
Julia: blue smart bad
Anne: red dumb bad


[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator