10240  The nDimensional Cities
Moderator: Board moderators
10240  The nDimensional Cities
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!
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 :
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[i1] + step;
i++;
if ( i>10002 ) break;
dis = dis[i1] + 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]
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[i1] + step;
i++;
if ( i>10002 ) break;
dis = dis[i1] + 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]

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 New poster
 Posts: 17
 Joined: Fri May 24, 2002 4:24 am
 Location: Taiwan
 Contact:
What's wrong with my codes???
Is my formula wrong???
Or another precision error???
Is my formula wrong???
Or another precision error???
Last edited by ShihChia Cheng on Fri Jul 26, 2002 3:10 am, edited 1 time in total.

 New poster
 Posts: 17
 Joined: Fri May 24, 2002 4:24 am
 Location: Taiwan
 Contact:
I fixed my codes, but still wrong answer......
Last edited by ShihChia Cheng on Fri Jul 26, 2002 3:11 am, edited 1 time in total.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 New poster
 Posts: 17
 Joined: Fri May 24, 2002 4:24 am
 Location: Taiwan
 Contact:
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+(ex)*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?
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+(ex)*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?

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 New poster
 Posts: 17
 Joined: Fri May 24, 2002 4:24 am
 Location: Taiwan
 Contact:

 New poster
 Posts: 1
 Joined: Thu Dec 11, 2003 6:52 am

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re:
AC output: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
Code: Select all
240 2457
3660 214499
3969 166267
Check input and AC output for thousands of problems on uDebug!