2000 Canadian Computing Competition, Stage 1

Problem J5/S3: Surfin'

Every Web Page is identified by a string of characters known as a URL (Uniform Resource Locator). Web Pages are formatted using HTML (Hypertext Markup Language). HTML has many codes, collectively known as markup, that allow the author to specify the format of the pages as well as to specify links to other pages. For this problem, we are concerned only with the markup that identifies links to other pages within a given page.

A link within the page is denoted <A HREF="URL"> where URL is the URL of some other page. A user viewing a page containing a link may click on the link to view the other page.

You are to write a program that reads a number of web pages and their associated URLs. For each link in each page, you must print the URL of the page containing the link, and the URL of the page referred to by the link.

Following the last page, you are then given several pairs of URLs. For each pair you are to assume that you are viewing the page identified by the first URL, and determine whether it is possible to click a sequence of links so as to view the page identified by the second URL. If so, you should print "Can surf from here to there." where here and there are the two URLs. If not you should print "Can't surf from here to there.

The first line of input contains an integer n ≤ 100, the number of Web Pages. For each Web Page, there will be a line containing its URL, followed by several lines containing the page. The URL will consist of up to 80 non-blank printable characters and will not contain any quotation marks. The first line of the page will be <HTML> and the last line will be </HTML>. Each page will contain up to 100 links in the format described above. Each link will be contained within a single line of input. URLs in the link will be those of pages given in the input. The markup keywords A, HREF, and HTML will appear only in upper case.

Following the n pages will be several pairs of lines giving URLs required by the problem as specified above. The last line of input will be "The End". For each pair, print the appropriate message given above.

Sample Input

3 
http://ccc.uwaterloo.ca 
<HTML> <TITLE>This is the CCC page</TITLE> 
Hello there boys 
and girls. <B>Let's</B> try <A HREF="http://abc.def/ghi"> a little problem </A> 
</HTML> 
http://abc.def/ghi 
<HTML> Now is the <TITLE>time</TITLE> for all good people to program. 
<A HREF="http://www.www.www.com">hello</A><A HREF="http://xxx">bye</A> 
</HTML> 
http://www.www.www.com 
<HTML> 
<TITLE>Weird and Wonderful World</TITLE> 
</HTML> 
http://ccc.uwaterloo.ca 
http://www.www.www.com 
http://www.www.www.com 
http://ccc.uwaterloo.ca 
The End

Sample Output

Link from http://ccc.uwaterloo.ca to http://abc.def/ghi 
Link from http://abc.def/ghi to http://www.www.www.com 
Link from http://abc.def/ghi to http://xxx

Can surf from http://ccc.uwaterloo.ca to http://www.www.www.com
Can't surf from http://www.www.www.com to http://ccc.uwaterloo.ca

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Oct 01, 2008

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

"URLs in the link will be those of pages given in the input."

This is contradicted in the example; there is a link for xxx, but that is not one of the pages in the input.

Which is correct?

Read the input more carefully.

I can see that the link is there; but there is no page with that URL in the input.
The definition of the problem also says "The first line of the page will be <HTML>", but in the example, the first lines of some of the pages contain other text.

Hmm, I think you are right about the statement being wrong. Just pretend that sentence doesn't exist I guess.
Also, I guess you'll also have to assume that the first line of each page merely starts with <HTML>.

Why do I get a nullptr exception? I verified with official CCC data and nothing came up

Edit: Thanks fixed!

I think you're reading lines when no more exists in the input file. On your computer, this is only obvious when you're testing with files rather than inputting by console.

There is no dot in "Can surf from http://ccc.uwaterloo.ca to http://www.www.www.com."
should be "Can surf from http://ccc.uwaterloo.ca to http://www.www.www.com"

Thanks, fixed.

And yeah, this annoying type of problem is perfectly characteristic of ACM.

i spent like an hour finding the error in that. apparently if i have a string s and i call s.length()-8, and the length of the string is less than 8, then it returns some randomly huge number rather than something like -8, or -4. Why does it do that? Is it because it returns an unsigned int?

As defined by the C++ STL, the length() method in the string class will return the type "size_type" which is basically an unsigned integer.

Therefore, if a type is not specified for "8", it will be implicitly typecasted to the value that precedes it (size_type), so you've got s.length()-(size_type)8, which gives you a negative overflow.

To fix this, you would typecast s.length() to an integer: (int)s.length()-8.