Page **1** of **1**

### 10240 - The n-Dimensional Cities

Posted: **Mon May 27, 2002 8:01 pm**

by **Anderson**

I find the following regularity:

Dimension : 1 2 3 4 5 6 7 8 9 .......

Segment No : 1 2 4 5 9 10 16 17 25 .......

So I guess a formula, which make out the segment number,when the dimension is given.

But , I got W.A.

Is there any mistakes in my guess?

or there are some pitfalls that I didn't pay any attention.

could you help me? thank u very much!

### About My program :

Posted: **Tue May 28, 2002 3:06 pm**

by **Anderson**

my program is as follows , can u tell me where my bug is?

thanx again!

[cpp]

// @begin_of_source_code

#include <iostream.h>

#include <math.h>

#include <iomanip.h>

#include <fstream.h>

ifstream fin("10240.in");

int dis[10005];

int dim,dist,d;

double length;

void main()

{

dis[1] = 0;

dis[2] = 1;

dis[3] = 2;

int i,step;

i = 3;

step = 2;

for ( ; ; ) {

i++;

if ( i>10002 ) break;

dis* = dis[i-1] + step;*

i++;

if ( i>10002 ) break;

dis* = dis[i-1] + 1;*

step+=2;

}

double d1,d2,a,c,ang,b;

int q,z;

double lenq,lenz,len;

fin>>dim>>dist>>d;

while ( !fin.fail() ) {

dim++;

d1 = dist;

a = d1 / 2.0;

ang = asin(a/d);

ang = ang * 2.0;

d2 = ang * double(d);

if ( dis[dim]%2==0 ) {

q = z = dis[dim]/2;

} else {

q = (dis[dim]-1) / 2;

z = (dis[dim]+1) / 2;

}

for( ; ; ) {

lenz = d1 * double(z);

lenq = d2 * double(q);

len = lenq + lenz;

if ( lenq/len>0.5 ) {

q--;

z++;

} else {

break;

}

}

cout<<dis[dim]<<' '

<<setiosflags(ios::fixed)

<<setprecision(0)<<len<<endl;

fin>>dim>>dist>>d;

}

}

// @end_of_source_code

[/cpp]

Posted: **Thu Jul 25, 2002 7:27 am**

by **Adrian Kuegel**

your segment numbers for even dimensions >=4 are wrong, for example consider dim = 4. The 5 cities can be connected in this way:

1 - 2

2 - 3

3 - 4

4 - 5

1 - 4

2 - 5

use backtracking to determine the segment numbers for small dimensions, you will also find a easy formula for the even dimensions.

Posted: **Thu Jul 25, 2002 3:32 pm**

by **Shih-Chia Cheng**

What's wrong with my codes???

Is my formula wrong???

Or another precision error???

Posted: **Thu Jul 25, 2002 3:55 pm**

by **Shih-Chia Cheng**

I fixed my codes, but still wrong answer......

Posted: **Thu Jul 25, 2002 6:13 pm**

by **Adrian Kuegel**

Your segment numbers are correct, so the error must lie in the calculation of the road length.

I don't understand this line:

x = min(e/2,e*dist/(cl+dist))

What do you want to do with e*dist/(cl+dist) ?

Posted: **Fri Jul 26, 2002 2:24 am**

by **Shih-Chia Cheng**

The problem says "there can be at most 50% circular roads and the

number of them will be no more than straight ones."

So let the number of circular roads be x and the length of a circular road

be cl, I have the following formula:

x*cl/(x*cl+(e-x)*dist) <= 0.5

after some algebra, we can get x <= (e*dist)/(cl+dist)

then it is combined with the constraint x<=e/2

the final result is x = min (e/2, (e*dist)/(cl+dist));

did I make any mistake in understanding the problem description?

Posted: **Fri Jul 26, 2002 2:30 am**

by **Adrian Kuegel**

Yes, I think you misunderstood the description. The 50% is 50% of the number of roads, not of the length.

Try this input:

29 10 10

Output:

225 2303

Posted: **Fri Jul 26, 2002 3:05 am**

by **Shih-Chia Cheng**

Finally I got AC!

Thanks for your great help!

Adrian Kuegel wrote:Yes, I think you misunderstood the description. The 50% is 50% of the number of roads, not of the length.

Try this input:

29 10 10

Output:

225 2303

Posted: **Thu Dec 18, 2003 11:02 pm**

by **Bladerunner**

I keep getting WA. Can you help me?

What's the result, for example, for this:

30 10 10

120 50 26

125 40 30

thanx

### Re:

Posted: **Thu Jan 31, 2013 7:08 am**

by **brianfry713**

Bladerunner wrote:I keep getting WA. Can you help me?

What's the result, for example, for this:

30 10 10

120 50 26

125 40 30

thanx

AC output: