What's the test for WA#9? Try 3 0 0 10 10 10 0 20 10 20 0 30 10 Answer 36 try a rectangle in the negative area If you have WA #3 try this simple test 1 0 0 10 12 Answer of course is 18 Something is wrong with test 11. When I wrote while (scanf("%d", &n) >= 1) { ... } I got WA11. But when I wrote while (scanf("%d", &n) >= 1) { ... break; } I got AC. This problem seems easy , but I have WA on test 8, does anybody know what kind of test is this? May be greedy wrong? My solution based on greedy. Starting from p1=(1,1) we go to nearest(in x+y metric) admissible p2 and so on. I have wa 9. Yes!. Greedy is right. Proof: Let p3 be another admissible point. We have: Dist(p1,p2)<=Dist(p1,p3)-Dist(p2,p3); Dist(p2,n)<=Dist(p3,n)+Dist(p2,p3); => Dist(p1,p2)+Dist(p2,n)<=Dist(p1,p3)+Dist(p3,n) Edited by author 22.11.2011 14:35 What is the answer for 2 0 0 3 3 3 2 5 7 Answer is -1? - What?! Why? ^ | __ | | | | | | | | | |___| | Such input gives that picture, so why there is no path?! | | | | |__| |___| ----------- > #include <cstdio> int main() { freopen("output.txt", "w", stdout); printf("99999\n"); printf("0 0 10 100\n"); for(int i =0 ; i < 99998; ++i) { printf("%d %d %d %d\n", (i+1)*10,0,(i+2)*10 , 100); } return 0; } My early solution get AC, but must get TL. Edited by author 19.01.2011 16:05 Hi! Here is my source - I compiled it on Visual C++ and it is OK - but here got "compilation Error". Could anyone explain me why??? #include <stdio.h> long x1,x2,y1,y2,ymin,ymax,n,i,posy,disttt; void main() { bool boo; boo=false; scanf("%ld",&n); scanf("%ld%ld%ld%ld",&x1,&y1,&x2,&y2); disttt=0; posy=1; ymin=y1; ymax=y2; for(i=1;i<n;i++) { scanf("%ld%ld%ld%ld",&x1,&y1,&x2,&y2); if(y1>=ymax-1||y2<=ymin+1) { printf("-1\n"); boo=true;; } if (posy<=y1) { disttt+=(y1+1-posy); posy=y1+1; } else if (posy>=y2) { disttt+=posy-y2+1; posy=y2-1; } ymin=y1; ymax=y2; } disttt+=x2-2; if (posy>y2-1) disttt+=posy+1-y2; else if(posy<y2-1) disttt+=y2-1-posy; if (boo==false) printf("%ld\n",disttt); } Thanks! Try replacing y1 with y1_ and y2 with y2_. You will get accepted. The same thing happened to me. Do not use bool,the compiler may not support this I think my code is right,but it was getting wa wa all the time. So I started to change it. I saw the code above,so I changed mine more and more like that. But a surprising thing ,my code is even equal to the code above, but it got accepted,but my still wa. I wonder.............. my code #include<iostream> #include<string> #include<memory> using namespace std; int main(void) { long n; cin>>n; long nowy=1,i,maxy,miny,x1,y1,x2,y2; long dist=0; cin>>x1>>miny>>x2>>maxy; bool ok=true; for(i=1;i<n;++i){ cin>>x1>>y1>>x2>>y2; if(y1>=maxy-1||y2<=miny+1){ ok=false; break; } if(y1>=nowy){ dist+=y1+1-nowy; nowy=y1+1; } else if(y2<=nowy){ dist+=nowy-y2+1; nowy=y2-1; } miny=y1; maxy=y2; } if(ok){ dist+=x2-2; //dist+=abs(y2-1-nowy); if(nowy>y2-1)dist+=nowy+1-y2; else if(nowy<y2-1)dist+=y2-1-nowy; cout<<dist<<endl; } else cout<<"-1"<<endl; return 0; } show me how big of this test can x,y be a negative integer? my code fail on test #10 for many times i can't see why? #include<stdio.h> int abs(int n) { if(n>=0) return n; else return -n; } int min(int a,int b) { if(a<=b) return a; else return b; } int main() { int n,i; int best_u_last,best_d_last ,y_u_last,y_d_last ,x1,y1,x2,y2 ,dx;
scanf("%d",&n);
scanf("%d %d %d %d",&x1,&y1,&x2,&y2); y_d_last=y1; y_u_last=y2; best_u_last=x2-x1+y2-y1-4; best_d_last=x2-x1-2;
for(i=1;i<n;i++) { scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
if( (y1>=y_u_last-1) || (y2<=y_d_last+1) ) { //suck!! best_u_last=-1; break; } else { //pass //dx dx=abs(x2-x1); //u best_u_last=min( best_u_last + abs(y_u_last - y2) , best_d_last + abs(y_d_last - y2 + 2) ) + dx; //d best_d_last=min( best_u_last + abs(y_u_last - y1 - 2) , best_d_last + abs(y_d_last - y1) ) + dx; } y_u_last=y2; y_d_last=y1; }
printf("%d", best_u_last ); } Can he touch the borders? For the following input: 0 0 10 10 10 9 20 20 is there solution? (can he walk like 10,9 ->10,10->11,10, touching the borders but not walking over them) ? #include <stdio.h> #include <math.h> #define min(a, b) (a < b ? a : b) #define max(a, b) (a > b ? a : b) int N; int read_and_solve() { int i, L = 0; int lx1, ly1, lx2, ly2, x1, y1, x2, y2, lo, hi; int X = 1, Y = 1; scanf("%d %d %d %d %d", &N, &lx1, &ly1, &lx2, &ly2); for (i = 1; i < N; i++) { scanf("%d %d %d %d", &x1, &y1, &x2, &y2); lo = max(y1, ly1); hi = min(y2, ly2); if (hi-lo < 2) return -1; if (Y <= lo) L += (lo+1)-Y, Y = lo+1; if (Y >= hi) L += Y-(hi-1), Y = hi-1; L += x1-X, X = x1; lx1 = x1, ly1 = y1, lx2 = x2, ly2 = y2; } L += x2-1-X+abs(y2-1-Y); return L; } void main() { printf("%d\n", read_and_solve()); } 1 0 0 2 2 for 1 0 0 2 2 should the answer be 0 i think that code also answer 0 What is the meaning of "100 >= xi ?xi >= 2"? In "100>=xi ? xi >=2","i" is unless than 2.
Note:"X1=0 Y1=0" and "Xi=Xi+1" !!! |
|