Page 1 of 1

511 - Do You Know the Way to San Jose?

Posted: Mon Apr 20, 2009 2:04 pm
by damnerd
Anyone knows what's the largest number of maps and or cities? i.e. the limits on the size of each test case?

Re: 511 - Do You Know the Way to San Jose?

Posted: Fri Jun 15, 2012 11:12 pm
by stubbscroll
I'm stuck on this problem, and I can't even get the example right. Could someone tell me where I'm wrong here (or verify that the example is wrong)?

In the second query (San Francisco, level 2), there are three eliglble maps:

Level 1: NCalif, area 572, distance to center sqrt(121.16)
Level 2: SanMateo, area 35, distance to center sqrt(5.41)
Level 3: BayArea, area 35, distance to center sqrt(2.26)

BayArea has a shorter distance to center, so this would make it more preferrable than SanMateo since they both have equal area. However, the correct answer according to the sample output is BayArea.

Have I missed some crucial details, or is this yet another broken problem? This problem wasn't submittable before the migration.
Anyone knows what's the largest number of maps and or cities? i.e. the limits on the size of each test case?
My program using static arrays doesn't crash when assuming 5000 maps, 5000 locations and a maximal name length of 139.

Re: 511 - Do You Know the Way to San Jose?

Posted: Tue Jun 19, 2012 1:29 am
by brianfry713
I agree with your logic that the sample output seems wrong. I got AC on this problem by simply doing a qsort on the area of each map containing that city and ignoring the rest. So my code doesn't consider whether multiple maps have the same area, the distance to center, aspect ratio, distance to the lower right corner, or the smallest x-coordinate. My code matches the sample I/O.

I can confirm that 5000 maps, 5000 locations and a maximal name length of 139 are large enough assumptions.

Re: 511 - Do You Know the Way to San Jose?

Posted: Mon Jun 25, 2012 3:43 am
by stubbscroll
Thanks for the info, Brian! Seems like this problem could use a new dataset...

511 WA- Do You Know the Way to San Jose?

Posted: Tue Aug 12, 2014 10:34 am
by cksteven
i tried and fixed some problems i found but i still got WA.
my code can pass the sample i/o data.

can anyone offer me some I/O data,plz?

or this is my code,if you are helpful and free,would you help me fix it?

Code: Select all

	......
	cout<<name<<" at detail level "<<level<<ends;
	......

Re: 511 WA- Do You Know the Way to San Jose?

Posted: Tue Aug 12, 2014 11:50 am
by lighted
Your output doesn't match sample. Change line

Code: Select all

cout<<name<<" at detail level "<<level<<ends;
It must be

Code: Select all

cout<<name<<" at detail level "<<level<<" ";
Don't forget to remove your code after getting accepted. 8)

Re: 511 WA- Do You Know the Way to San Jose?

Posted: Tue Aug 12, 2014 10:14 pm
by cksteven
Thank you very much, @lighted! :D
Now i knew the difference between

Code: Select all

cout<<ends;
and

Code: Select all

cout<<" ";
.
p.s. My C++ Primer (Chinese Edition) says ends will output a space.

Re: 511 WA- Do You Know the Way to San Jose?

Posted: Tue Aug 12, 2014 10:19 pm
by lighted
printing ends will output null character '\0' not space. :)

Re: 511 - Do You Know the Way to San Jose?

Posted: Wed Apr 26, 2017 11:38 am
by metaphysis
The test data is not strong. For a given location, the area of every map which contains the location is distinct, so for a given level, it exists a only map or not. You even can ignore the preferred rule!