903 - Spiral of Numbers
Moderator: Board moderators
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?
2. 14 appears twice in the 11x11 table.
3. is there some hidden input/output assumption?
I think it should be 'semicolon'. Spelling mistake.1. What is a semicolumn?
Another mistake. It should be 24.2. 14 appears twice in the 11x11 table.
I dont know. I believe there is something wrong. Still checking...3. is there some hidden input/output assumption?
Ami ekhono shopno dekhi...
HomePage
HomePage
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???
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"
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.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 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.
Re: 903 - Spiral of Numbers
Last edited by sapnil on Thu Jul 03, 2008 7:02 pm, edited 1 time in total.
"Dream Is The Key To Success"
@@@ Jony @@@
@@@ Jony @@@
Re: 903 - Spiral of Numbers
Try the case below:
Input:
Output:
Input:
Code: Select all
301413357
Code: Select all
301343915;301413356;301482805;
301343916;301413357;301482806;
301343917;301413358;301482807;
Ami ekhono shopno dekhi...
HomePage
HomePage
Re: 903 - Spiral of Numbers
Why WA ??
thnx in advance for help...!!
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;
}
903 - Spiral of Numbers-WA-passed all test cases
Code: Select all
Accepted