903 - Spiral of Numbers

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

Moderator: Board moderators

XLDEV
New poster
Posts: 3
Joined: Fri Sep 29, 2006 7:58 pm

903 - Spiral of Numbers

1. What is a semicolumn?
2. 14 appears twice in the 11x11 table.
3. is there some hidden input/output assumption?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:
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...
Ami ekhono shopno dekhi...
HomePage

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia
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???
"Life is more beautiful with algorithm"

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 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.
Thanks in advance!

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
I used the same algorithm and got AC with 0.355.

I think your implementation of
function : number -> coordinate
and
function : coordinate -> number
isn't efficient enough.

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am
rio wrote:I used the same algorithm and got AC with 0.355.

I think your implementation of
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.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
IRA wrote:
rio wrote:I used the same algorithm and got AC with 0.355.

I think your implementation of
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.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
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

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am
Thanks to rio and helloneo!
I know how to solve it.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Re: 903 - Spiral of Numbers

I m getting WR plz help me

Code: Select all

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

``````
Thanks
Sapnil
Last edited by sapnil on Thu Jul 03, 2008 7:02 pm, edited 1 time in total.
"Dream Is The Key To Success"

@@@ Jony @@@

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 903 - Spiral of Numbers

Try the case below:

Input:

Code: Select all

``301413357``
Output:

Code: Select all

``````301343915;301413356;301482805;
301343916;301413357;301482806;
301343917;301413358;301482807;``````
Ami ekhono shopno dekhi...
HomePage

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Re: 903 - Spiral of Numbers

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;
}

``````
thnx in advance for help...!!

moody
New poster
Posts: 9
Joined: Tue Sep 24, 2013 2:19 am

903 - Spiral of Numbers-WA-passed all test cases

Code: Select all

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