10240 - The n-Dimensional Cities

[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!

[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]

[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.

[Shih-Chia Cheng]

What's wrong with my codes???
Is my formula wrong???
Or another precision error???

[Shih-Chia Cheng]

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

[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) ?

[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?

[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

[Shih-Chia Cheng]

Finally I got AC!
Thanks for your great help!

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

[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

[brianfry713]

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:

Code: Select all

240 2457
3660 214499
3969 166267