编程介的小学生 2017-05-03 14:50 采纳率: 20.5%
浏览 757
已采纳

Kevin Bacon

Kevin Norwood Bacon (born July 8, 1958) is an American film and theater actor whose notable roles include Animal House, Diner, Footloose, Flatliners, Wild Things, A Few Good Men, Apollo 13, Mystic River, The Woodsman, Trapped, Friday the 13th, Hollow Man, Tremors, Death Sentence, Frost/Nixon, Crazy, Stupid, Love and X-Men: First Class.

Bacon has won Golden Globe and Screen Actors Guild Awards, was nominated for an Emmy Award, and was named by The Guardian as one of the best actors never to have received an Academy Award nomination.

In 2003, Bacon received a star on the Hollywood Walk of Fame.

He was good at playing various roles, and every actor or actress having the honor of being a partner to Bacon is well respected.

Not everybody got a chance to be a partner with Bacon, so many people were content if they managed to play a movie with somebody who had played a movie with Bacon. This gave rise to the so-called Bacon numbers. Nowadays, an advanced Bacon numbers have been invented, it also refer to the box office, when box office is larger, the number k is smaller. For example, An actor who has play in a movie with Bacon, with the number about this movie is k, had advanced Bacon number k. An actor who had not played with Bacon but with somebody(the movie they played together has a number k2) with Bacon number k1 obtained Bacon number k1+k2, and so on. Today, nearly every actor wants to know what the smallest advanced Bacon number he or she has. Your task is to write a program that computes advanced Bacon numbers for a given set of actor.

Input

The input file contains a sequence of actors, each scenario consisting of a movie database and a list of names. A scenario begins with the line "p n", where p and n are natural numbers with 1 <= p <= 32000;1 <= n <= 3000.1 <= k <= 100 000. Following this line are p lines containing descriptions of movies (this is the movie database). A movie is played by a line of the following form:

k LastName1, FirstName1, LastName2, Firstname2, . . . : TitleOfTheMovie

The names and the title may contain any ASCII characters between 32 and 126 except commas and colons. There will always be exactly one space character following each comma. The first name may be abbreviated, but the same name will always be written in the same way.

Example:

John, Belushi, Karen, Allen, Kevin, Bacon: Animal House

After the p movies follow n lines each containing exactly one name in the same format as in the movie database.

The line "0 0" terminates the input.

No name will consist of more than 40 characters. No line in the input file contains more than 250 characters. In each scenario there will be at most 1100 different actors.

Output

For every scenario first print the number of the scenario in the format shown in the sample output. Then print for every actor name in the list of names their advanced Bacon number based on the movies in the movie database of the scenario. The actors should be output in the order given in the input file. Actors that do not have any relation to Bacon via the movies have advanced Bacon number infinity. Adhere to the format shown in the sample output.
Print a blank line after each case.

Sample Input

3 3
3 John, Belushi, Karen, Allen, Kevin, Bacon: Animal House
2 Tom, Hulce, Karen, Allen: Starting Over
1 Hill, Ken, Bob, Stock: kick the ball
John, Belushi
Tom, Hulce
Bob, Stock
0 0
Sample Output

Database 1
John, Belushi: 3
Tom, Hulce: 5
Bob, Stock: infinity

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-05-18 03:07
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求chat4.0解答一道线性规划题,用lingo编程运行,第一问要求写出数学模型和lingo语言编程模型,第二问第三问解答就行,我的ddl要到了谁来求了
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果