511 - Do You Know the Way to San Jose?

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
damnerd
New poster
Posts: 1
Joined: Mon Apr 20, 2009 1:57 pm

511 - Do You Know the Way to San Jose?

Post by damnerd » Mon Apr 20, 2009 2:04 pm

Anyone knows what's the largest number of maps and or cities? i.e. the limits on the size of each test case?

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

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

Post by stubbscroll » Fri Jun 15, 2012 11:12 pm

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.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

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

Post by brianfry713 » Tue Jun 19, 2012 1:29 am

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.
Check input and AC output for thousands of problems on uDebug!

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

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

Post by stubbscroll » Mon Jun 25, 2012 3:43 am

Thanks for the info, Brian! Seems like this problem could use a new dataset...

cksteven
New poster
Posts: 5
Joined: Wed Jul 23, 2014 9:38 am

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

Post by cksteven » Tue Aug 12, 2014 10:34 am

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;
	......
Last edited by cksteven on Tue Aug 12, 2014 10:18 pm, edited 1 time in total.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

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

Post by lighted » Tue Aug 12, 2014 11:50 am

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)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

cksteven
New poster
Posts: 5
Joined: Wed Jul 23, 2014 9:38 am

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

Post by cksteven » Tue Aug 12, 2014 10:14 pm

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.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

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

Post by lighted » Tue Aug 12, 2014 10:19 pm

printing ends will output null character '\0' not space. :)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

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

Post by metaphysis » Wed Apr 26, 2017 11:38 am

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!

Post Reply

Return to “Volume 5 (500-599)”