Page 1 of 1

903 - Spiral of Numbers

Posted: Fri Sep 29, 2006 8:02 pm
1. What is a semicolumn?
2. 14 appears twice in the 11x11 table.
3. is there some hidden input/output assumption?

Posted: Fri Sep 29, 2006 11:21 pm
1. What is a semicolumn?
I think it should be 'semicolon'. Spelling mistake.
2. 14 appears twice in the 11x11 table.
Another mistake. It should be 24.
3. is there some hidden input/output assumption?
I dont know. I believe there is something wrong. Still checking...

Posted: Sat Sep 30, 2006 4:17 am
I believe that something was wonrg with judge input and output. after 77 submission no one got AC??
I've made 2 program,one with formula,and the second one I simulate that spiral. The result of two my program are exactly the same.
I wonder why WE got Wrong Answer???

Posted: Sat Dec 16, 2006 10:19 am
Who can show me some good idea or algorithm to speed up the problem.
First,I find the the coordinate of the number.
Second,I use the coordinate to find other number.
I use this method then got TLE.

Posted: Sat Dec 16, 2006 12:01 pm
I used the same algorithm and got AC with 0.355.

function : number -> coordinate
and
function : coordinate -> number
isn't efficient enough.

Posted: Sat Dec 16, 2006 5:06 pm
rio wrote:I used the same algorithm and got AC with 0.355.

function : number -> coordinate
and
function : coordinate -> number
isn't efficient enough.

My step1 & step2 isn't efficient enough.
I can't think how to speed it.
My method is find the number on which loop then step by step to find the
coordinate.
It is too slow.

Posted: Sun Dec 17, 2006 12:09 pm
IRA wrote:
rio wrote:I used the same algorithm and got AC with 0.355.

function : number -> coordinate
and
function : coordinate -> number
isn't efficient enough.

My step1 & step2 isn't efficient enough.
I can't think how to speed it.
My method is find the number on which loop then step by step to find the
coordinate.
It is too slow.
I used the same method and used binary search for finding the loop.
I think the process of finding the loops takes almost of the time.
So If you are using linear searh for finding the loop, try binary search.

Posted: Sun Dec 17, 2006 2:55 pm
I just did a linear search and got AC with 0.414 sec

function: number -> coordinate
You can get the bounds and only need to search n/4

function: coordinate -> number
You can find a formular and get it directly

Posted: Mon Dec 18, 2006 1:05 pm
Thanks to rio and helloneo!
I know how to solve it.

Re: 903 - Spiral of Numbers

Posted: Wed Jun 25, 2008 4:57 am
I m getting WR plz help me

Code: Select all

``````
.....Removed

``````
Thanks
Sapnil

Re: 903 - Spiral of Numbers

Posted: Wed Jun 25, 2008 9:55 pm
Try the case below:

Input:

Code: Select all

``301413357``
Output:

Code: Select all

``````301343915;301413356;301482805;
301343916;301413357;301482806;
301343917;301413358;301482807;``````

Re: 903 - Spiral of Numbers

Posted: Thu Oct 09, 2008 2:11 am
Why WA ??

Code: Select all

``````#include<iostream>
#include<string>
using namespace std;
int main(){
unsigned int i,n,j,k,l,d,m;
char c[11][27]={
"2",
"7;8;9;\n6;1;2;\n5;4;3;",
"8;9;10;\n1;2;11;\n4;3;12;",
"1;2;11;\n4;3;12;\n15;14;13;",
"6;1;2;\n5;4;3;\n16;15;14;",
"19;6;1;\n18;5;4;\n17;16;15;",
"20;7;8;\n19;6;1;\n18;5;4;",
"21;22;23;\n20;7;8;\n19;6;1",
"22;23;24;\n7;8;9;\n6;1;2;",
"23;24;25\n8;9;10;\n1;2;11;"};

while(cin>>n){
if(n<10){
puts(c[n]);
continue;
}
i=1;
while(i*i<n)	i+=2;
j=i*i;
k=(i+2)*(i+2);
l=(i-2)*(i-2);
if(j==n)
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-2,k-1,k,j-1,j,j+1,l,l+1,j+2);
else if(j-i+2<n){
d=j-n;
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-d-2,k-d-1,k-d,n-1,n,n+1,l-d,l-d+1,l-d+2);
}
else if(j-i+2==n)
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-i,k-i+1,k-i+2,n-1,n,n+1,n-2,l-i+3,l-i+4);
else if(j-i+1==n)
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-i-1,k-i,k-i+1,k-i-2,n,n+1,k-i-3,n-1,l-i+3);
else if(j-i==n)
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-i-2,n+1,n+2,k-i-3,n,l-i+3,k-i-4,n-1,l-i+2);
else if(j-2*i+3<n){
d=j-n;
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-d-2,n+1,l-d+4,k-d-3,n,l-d+3,k-d-4,n-1,l-d+2);
}
else if(j-2*i+3==n){
d=j-n;
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-d-2,n+1,l-d+4,k-d-3,n,l-d+3,k-d-4,n-1,n-2);
}
else if(j-2*i+2==n){
d=j-n;
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",k-d-2,n+1,l-d+4,k-d-3,n,n-1,k-d-4,k-d-5,k-d-6);
}
else if(j-2*i+1==n){
d=j-n;
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",n+2,l-d+5,l-d+4,n+1,n,n-1,k-d-4,k-d-5,k-d-6);
}
else if(l+(i-2)+2<n){
d=n-l;
m=(i-4)*(i-4);
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",m+d-2,m+d-3,m+d-4,n+1,n,n-1,j+d+4,j+d+3,j+d+2);
}
else if(l+(i-2)+2==n){
d=n-l;
m=(i-4)*(i-4);
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",m+d-2,m+d-3,n-2,n+1,n,n-1,j+d+4,j+d+3,j+d+2);
}
else if(l+(i-2)+1==n){
d=n-l;
m=(i-4)*(i-4);
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",m+d-2,n-1,j+d,n+1,n,j+d+1,j+d+4,j+d+3,j+d+2);
}
else if(l+(i-2)==n){
d=n-l;
m=(i-4)*(i-4);
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",m+d-2,n-1,j+d,m+d-1,n,j+d+1,n+2,n+1,j+d+2);
}
else if(l+2<n){
d=n-l;
m=(i-4)*(i-4);
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",m+d-2,n-1,j+d,m+d-1,n,j+d+1,m+d,n+1,j+d+2);
}
else if(l+2==n){
d=n-l;
m=(i-4)*(i-4);
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",n-2,n-1,j+d,m+d-1,n,j+d+1,m+d,n+1,j+d+2);
}
else{
m=(i-4)*(i-4);
printf("%u;%u;%u;\n%u;%u;%u;\n%u;%u;%u;\n",j-1,j,j+1,l,n,j+2,m+1,n+1,j+3);
}
}
return 0;
}

``````
``````Accepted