시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 0 | 0 | 0 | 0.000% |
You may have heard the expression "the enemy of my enemy is my friend". By extension, then, "the enemy of my enemy of my enemy is my enemy", and so on. Given a set of relationships, you wish to determine how much of a friend or enemy people are, represented by a "total relationship score".
Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set will consist of a series of lines.
F
" representing a friend, an "E
" representing an enemy, and "N
" representing a neutral relationship. For example, if a line contained "Bob F E N
", this would indicate that Bob is friends with the person on the first line of the relationship matrix, enemies with the person on the second line of the relationship matrix, and has a neutral relationship with the person on the third line of the relationship matrix. Note that a person will always have a neutral relationship with themselves and that relationships are bi-directional (e.g., if Bob is a friend with George, then George is a friend with Bob).For each data set, print a single line containing the total relationship scores between the name given in the final line of the data set and every other person in the data set, with each score separated by a single space and in the same order that the names appear in the input. The total relationship score between two people is the sum total of all the relationship scores of direct and indirect relationships between them. Direct relationships are determined by the input described above. Indirect relationships are those in which a cycle-free path of two or more relationships can be traced between two people, with none of those relationships being of the neutral variety (e.g., an "enemy of an enemy" or an "enemy of a friend of an enemy"). The formula for determining a direct or indirect relationship score is as follows:
Score = (128 × (-1)x) / 2(y-1)
where x is the number of enemy relationships in the path and y is the total number of relationships in the path. Some examples follow:
3 5 Bob N F E N N Friend F N N N N Enemy E N N F E FriendOfEnemy N N F N N EnemyOfEnemy N N E N N Bob 4 Bob N F F F Tom F N E E Tim F E N F Joe F E F N Bob 4 Spy1 N E F N Spy2 E N E N Spy3 F E N N Spy4 N N N N Spy3
0 128 -128 -64 64 0 0 256 256 192 -192 0 0