|
|
Show all threads Hide all threads Show all messages Hide all messages | DP solution is very easy | Adhambek | 1531. Zones on a Plane | 19 Dec 2014 14:34 | 1 | deleted: Edited by author 24.12.2014 23:56 | Some Tests. | Oleg Strekalovsky [Vologda SPU] | 1531. Zones on a Plane | 8 Apr 2010 01:25 | 1 | Some Tests. Oleg Strekalovsky [Vologda SPU] 8 Apr 2010 01:25 input 5 output 20 input 6 output 28 input 7 output 44 input 100 output 4503599627370492 input 1000 output 13093562431584567480052758787310396608866568184172259157933165472384535185618698219533080369303616628603546736510240284036869026183541572213314110357500 input 2000 output 42860344287450692837937001962400072422456192468221344297750015534814042044997444899727935152627834325103786916702125873007485811427692561743938310298794299215738271099296923941684298420249484567511816728612185899934327765069595070236662175784308251658284785910746168670641719326610497547348822672277500 | WA12. | #11(Pskov) | 1531. Zones on a Plane | 15 Sep 2009 01:40 | 1 | WA12. #11(Pskov) 15 Sep 2009 01:40 #include<stdio.h> int a[2001][330]; int main() { int n; for(int i=0; i<2001; i++) { for(int j=0; j<330; j++) { a[i][j]=0; } } scanf("%d", &n);
a[1][329]=1; a[2][329]=4; a[3][329]=8; for(int i=4; i<2001; i++) { for(int j=329; j>0; j--) { if((i%2)==0) { a[i][j]=a[i][j]+(2*a[i-1][j])%10-a[i-2][j]; if(a[i][j]<0) { a[i][j]=a[i][j]+10; a[i][j-1]=a[i][j-1]-1; } if(a[i][j]>10) { a[i][j]=a[i][j]%10; a[i][j-1]=a[i][j-1]+a[i][j]/10; } if(2*a[i-1][j]>9) { a[i][j-1]=a[i][j-1]+(2*a[i-1][j])/10; } } else { a[i][j]=a[i][j]+(3*a[i-1][j])%10-(2*a[i-2][j])%10; if(a[i][j]<0) { a[i][j]=a[i][j]+10; a[i][j-1]=a[i][j-1]-1; } if(a[i][j]>10) { a[i][j]=a[i][j]%10; a[i][j-1]=aa[i][j-1]+[i][j]/10; } if(3*a[i-1][j]>9) { a[i][j-1]=a[i][j-1]+(3*a[i-1][j])/10; } if(2*a[i-2][j]>9) { a[i][j-1]=a[i][j-1]-(2*a[i-2][j])/10; } } } } for(int i=0; i<330; i++) { if(a[n][i]!=0) { for(int j=i; j<330; j++) { printf("%d", a[n][j]); } printf("\n"); goto A; } } A: return 0; } All tests are right, but I can't understand why WA12? | Is there some formula? | Mace(Lviv Polytechniс NU) | 1531. Zones on a Plane | 1 Aug 2008 19:44 | 6 | I used DP for solving this problem, and have AC in 0.015 sec. as many other Timus members. But, there are some members who take AC in 0.001 sec. So, my question is: is there some formula for this problem or this people take so incredible result with very hard optimization? If you know DP formula it's easy convert to simple math formula. It's very instresting problem =) If you submit your solution several times, it may get 0.001 sec in one of submissions Start with sequence of anges 0, 90, 180, 270 (the inner square) and perform -45, +45 steps at every edge from previous stage. Then cut away 180 degree turns. After that number of remaining edges /2 will be the result for current stage. Of course, yhat won't work for big N, but it gives an idea on how to calculate number of 180-degree cut-outs at stage N. Case N=1 is special. Odd and even N should be treated separately. The rest is up to you :) | What's answers for n=10 and n=11 ? | KIRILL(ArcSTU) | 1531. Zones on a Plane | 19 Feb 2007 00:46 | 5 | Thank you, but I have WA9 My prog returns 12 - 252 13 - 380 14 - 508 .. 50 - 93489396564 Thank you very much! Very stupid bug:) |
|
|
|