1431 - PageRank
Time Limit : 10 Second
Memory Limit : 256 MB
Submission: 243
Solved: 14
- Description
Google is famous over the world, much of the reason for their success lies with the effective search result for their user. In the final, support this effective is the technique called PageRank which largely used the huge url link network. A simple example is a hyperlink in Page A linked to Page B is viewed as A give a vote of support to B.
For us, PageRank is a complex technique, to simplify the problem, let’s analysis a simple model first. For every hyperlink, we just give 2 kind of attribute, the tag on the hyperlink, and the target url hyperlink point. So a hyperlink is viewed as a tag vote to an url.
As a user of search engine, each time we search, we will offer an keywork. Now the problem is for each given keywork, check all given hyperlink, if the tag on hyperlink contain this keywork, we count it’s a effective vote, then list the top 10 most voted url. (if 2 urls get the same votes, we sort it with lexicographic order)
- Input
First line is N, indicate N hyperlinks. (1<=N<=20000)
Next N lines:
Each line contain two string, the first is the tag of hyperlink and the second is the url.
We guarantee that tags just contain lowcase and the length is less than 7, and urls just not contain blank characters(blank spaces, tabs and line break characters), the length of urls is less than 30.
Next line is Q, indicate Q times search. (1<=Q<=50000)
Next Q lines:
Each line just contain a string, indicate the keyword offered by user.
- Output
For each search, list the top10 most voted urls, and a blankspace and the vote number.(if less then 10 urls be voted, just list all). If no url get votes, just output “Sorry, no result satisfied." In a single line.
For the answer of difference search, output a blank line between them.(Never leave a redundant blank line before the end of file)
Important hint, huge output, printf is recommended.
- sample input
-
10 hustacm http://acm.hust.edu.cn acmicpc http://acm.hust.edu.cn acm http://acm.hust.edu.cn hoj http://acm.hust.edu.cn/thx vjudge http://acm.hust.edu.cn/vt forum http://acm.hust.edu.cn/forum hhoj http://acm.hust.edu.cn/vt isun http://acm.hust.edu.cn/vt sempr http://acm.hust.edu.cn/thx gaewah http://acm.hust.edu.cn/forum 6 acm m hoj zy j h
- sample output
-
http://acm.hust.edu.cn 3 http://acm.hust.edu.cn 3 http://acm.hust.edu.cn/forum 1 http://acm.hust.edu.cn/thx 1 http://acm.hust.edu.cn/thx 1 http://acm.hust.edu.cn/vt 1 Sorry, no result satisfied. http://acm.hust.edu.cn/vt 2 http://acm.hust.edu.cn/thx 1 http://acm.hust.edu.cn 1 http://acm.hust.edu.cn/forum 1 http://acm.hust.edu.cn/thx 1 http://acm.hust.edu.cn/vt 1
- hint
- source
- HONG Zehua / HUST Monthly 2011.04.09