ural 1064 Binary Search

简单的模拟, 不过要注意这组数据......

Sample Input

 

9999 14

 

Sample Output

 

1

10000 10000

 

#include<iostream> #define MAXN 10000 using namespace std; int T[MAXN+2]; int N,ni,nL,tot; int want[MAXN/2][2]; void BinarySearch(int x) { int p,q,i,L; p=0; /* Left border of the search */ q=N-1; /* Right border of the search */ L=0; /* Comparison counter */ while(p<=q) { i=(p+q)/2; ++L; if(i==x) { if(L==nL) T[N]=1; return; } if(L>nL) return; if(x<i) q=i-1; else p=i+1; } return; } int main() { int i,temp; scanf("%d%d",&ni,&nL); for(N=ni;N<=10000;N++) BinarySearch(ni); for(i=0;i<=10001;i++) { if(T[i]) { temp=i; for(++i;i<=10001;i++) if(!T[i]) break; tot++; want[tot][0]=temp; want[tot][1]=i-1; } } printf("%d/n",tot); for(i=1;i<=tot;i++) printf("%d %d/n",want[i][0],want[i][1]); return 0; }