Show all threads Hide all threads Show all messages Hide all messages | For WA#8 | ACSpeed | 1064. Binary Search | 1 Dec 2011 19:36 | 1 | 0 13 answer should be 1 8191 10000 not 8191 10001 | If you have WA7 | Olzhas2dy | 1064. Binary Search | 27 Jan 2011 05:51 | 5 | TEST: 9999 14 ANSWER: 1 10000 10000 | Very Very Bad Task Description | Laise | 1064. Binary Search | 20 May 2010 03:52 | 6 | words "... and array A was filled with a nondescending integer sequence." means another that author want to say. E.g. nondescending array consists of only values 666, so which N can give us result (i=666,L=1)? of course all possible 1..MAXN =) but my AC prog output 1333-1334 =\... very very strange, don't you mind? True. The problem statement is wrong!! Solution requires array A to be { 1, 2, 3, ... } which is not "... and array A was filled with a nondescending integer sequence.". That could mean ANY NON-DESCENDING sequence, i.e. A could be { 1, 1, 1, 10, 12, 13 ...} which is completely different problem! You are wrong. You are given only i and L in this problem, x is unknown. So array shouldn't be { 1, 2, 3, ... }, any nondescending array is OK. Ok, I might be wrong. But what do you think is the answer for input like: 666 1? Aren't ALL integers in [1, 10000] are possible answers?? array might be { 666, 666, 666, 666 ... } which does not contradict problem statement, yet any size of N in [1, 10000] will give "Found item i = 666 in L = 1 comparisons" right? meaning answer should be "1 1 10000" and not "1 1333 1334"... If N = 10000 and array is { 666, 666, 666, 666 ... } then output of the program will be "Found item i = 5000 in L = 1 comparisons". Read the program code carefully. I apologize. My bad. Misunderstood the problem statement... "item i" kinda misleads... | i think sample test case in given problem is wrong | Anupam Ghosh,Bengal Engg and Science University,Shibpur,India | 1064. Binary Search | 25 Mar 2009 21:39 | 3 | take N=29 p=0 q=28 i=14 L=1 p=15 q=28 i=21 L=2 p=21 q=28 i=24 L=3 this is cancelled since i value is not 10 NOW the other way p=0 q=28 i=14 L=1 p=0 q=13 i=6 L=2 p=0 q=5 i=2 L=3 this is cancelled since i value is not 10 can any body explain me this?? take N=29 p=0 q=28 i=14 L=1 p=15 q=28 i=21 L=2 p=22 q=28 i=25 L=3 this is cancelled since i value is not 10 NOW the other way p=0 q=28 i=14 L=1 p=0 q=13 i=6 L=2 p=0 q=5 i=2 L=3 this is cancelled since i value is not 10 can any body explain me this?? Answer - is a POSSIBLE value of N. It means, that from this value you CAN get I for L steps. P = 0 Q = 28 I = 14 L = 1 P = 0 Q = 13 I = 6 L = 2 P = 7 Q = 13 I = 10 L = 3 | TEST #11 | jagatsastry | 1064. Binary Search | 27 Apr 2008 00:22 | 3 | I'm getting WA#11 Is there anyone who had such problem and got AC after rectifying it. Is there any such tricky test case. Problem solved. Try this test case 0 13 answer should be 1 8191 10000 | WA 3 please help!! | baku | 1064. Binary Search | 6 Feb 2008 00:57 | 1 | | WHY WA ON TEST#4 | 6yxa/\bl | 1064. Binary Search | 31 Mar 2007 08:23 | 1 | Help me please!!! Give me test #4 please!!!! This is my code #include <stdio.h> int n,m,a[10000]; bool BS(int x) { int p,q,i,L; p=0; q=x-1; L=0; while (p<=q) { i=(p+q)/2; ++L; if (i==n) return (L==m); if (n<i) q=i-1; else p=i+1; } return (L==m)&&(i==n); } int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int i,j,k,l,r,e=0,u=0; scanf("%d%d",&n,&m); for(i=1;i<=10000;i++) { if (BS(i)) { if (i-e>1) { a[++u]=e; a[++u]=i; } e=i; } } a[++u]=e; printf("%d\n",u/2); for(i=1;i<=u/2;i++) { printf("%d %d\n",a[2*i],a[2*i+1]); } return 0; } Edited by author 31.03.2007 08:25 | Give me test | AiD | 1064. Binary Search | 21 Feb 2007 22:47 | 3 | Please, give me same test. I hava WA on test 7. I fogotten the problem and didn't remember structure of difficult tests.Tne next is random. 20 7 14 87 90 103 106 119 122 127 134 143 150 159 166 183 190 215 222 247 254 303 318 383 414 543 574 895 958 2687 2814 thank you, but I have allready found my mistake. :-) | WA TEST#10 Help please!!! | Julius Canute | 1064. Binary Search | 29 Sep 2006 19:27 | 5 | #include<iostream> using namespace std; int BinarySearch(int N,int i,int l) { int mid,p,q; p = 0; q = N-1; for(int x=0;x<l;x++) { mid = (p+q)/2; if(mid<i) p = mid +1; else q = mid -1;
}
if(mid==i) return 1; else return 0;
} int main() { int j,k=0,f,com,flag=0,first,second; cin>>f>>com; for(j=f+1;j<=10000;j=j+1) { flag = BinarySearch(j,f,com); if(flag==1) { first =j; j = j + 1; while(BinarySearch(j,f,com)==1) {j=j+1;} second = j-1; k++; flag=0; } } cout<<k<<"\n"; for(j=f+1;j<=10000;j=j+1) { flag = BinarySearch(j,f,com); if(flag==1) { first =j; j = j + 1; while(BinarySearch(j,f,com)==1) {j=j+1;} second = j-1; cout<<first<<" "<<second<<"\n"; flag=0; } } return 0; } Are These Output correct for given inputs? 100 5 104 104 111 112 119 120 129 129 141 141 154 154 171 172 190 190 215 216 249 250 295 298 359 362 463 466 647 654 1079 1086 3231 3262 56 3 4 65 65 91 92 151 154 455 462 if they are correct,then why my soution is not accepted? Try this 0 5 The right answer is 1 31 62 And your answer is 1 1 62 Good Luck! ) I modified the code but still failing at Test#16 #include<iostream> using namespace std; int BinarySearch(int N,int i,int l) { int mid,p,q,x; p = 0; q = N-1; if(N==0) x=1; else x=0; for(;(x<l);x++) { mid = (p+q)/2;
if(mid==0)break; if(mid<i) p = mid +1; else q = mid -1;
}
if((x+1)>=l) { if(mid==i) return 1; else return 0; } else return 0; } int main() { int j,k=0,f,com,flag=0,first,second; cin>>f>>com; for(j=f+1;j<=10000;j=j+1) { flag = BinarySearch(j,f,com); if(flag==1) { first =j; j = j + 1; while(BinarySearch(j,f,com)==1&&(j<=10000)) {j=j+1;} second = j-1; k++; flag=0; } } cout<<k<<"\n"; for(j=f+1;j<=10000;j=j+1) { flag = BinarySearch(j,f,com); if(flag==1) { first =j; j = j + 1; while(BinarySearch(j,f,com)==1&&(j<=10000)) {j=j+1;} second = j-1; cout<<first<<" "<<second<<"\n"; flag=0; } } return 0; } Edited by author 29.09.2006 19:31 | Who can tell me how to solve this problem...Thx | akademi | 1064. Binary Search | 21 Apr 2005 09:31 | 2 | |
|
|