So the task is to determine whether the sum C[n][1]+C[n][2]+...+C[n][k] is greater than X and do it FAST.
I can't do it fast.


#include <stdio.h>
typedef unsigned long long huge;
huge calc(int n, int k){
     huge Up=k, Dn=0;
     while(Up-Dn>1){
           huge Md=(Up+Dn)/2;
           huge cnt=0;
           long double aux=1;
           for(int i=1; cnt<k && i<=n; ++i){
                  aux*=(long double)Md+1-i;
                  aux/=i;
                  cnt+=aux;
           }
           if(cnt<k)
                Dn=Md;
           else
                Up=Md;
     }
     return Dn+1;
}
int main(){
    huge n,k, ans[1000];
    int tot=0;
    scanf("%llu %llu",&n,&k);
    while(n>0 && k>0){
         ans[tot++]=calc(n,k);
         scanf("%llu %llu",&n,&k);
    }
    for(int i=0; i<tot; ++i)
          printf("%llu\n",ans[i]);
    return 0;
}

With that code you can solve version 1 in 0.031 sec and even in 0.001 sec if precomputed table of binomials is used.
But in V2 it runs in 0.51 sec on testcase 2!

Try
Update from:
huge calc(int n, int k){

To:
huge calc(huge n, huge k){

And one more trick:
ans[tot++]=calc(n,k);
replace by ans[tot++]=calc(min(60,n),k);

Thanks
See you AC
I am applied your suggestions to my program
But something went wrong again
Then I replaced magic constant 60 with 30000 and got 0.4999 sec running time but WA#2

My current WA#4 C code.
http://ideone.com/KwNNiu

AC Python2.

Finally AC with C++.  Thanks!