ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1597. Chernobyl’ Eagle on a Roof. Version 2

Math solution but still not enough fast
Послано Mahilewets 17 апр 2017 17:34
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;
}
Re: Math solution but still not enough fast
Послано Mahilewets 17 апр 2017 17:44
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!
Re: Math solution but still not enough fast
Послано Tolstobrov Anatoliy[Ivanovo SPU] 10 май 2017 20:10
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);
Re: Math solution but still not enough fast
Послано Mahilewets 10 май 2017 22:01
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
Re: Math solution but still not enough fast
Послано Mahilewets 19 май 2017 14:32
My current WA#4 C code.
http://ideone.com/KwNNiu
Re: Math solution but still not enough fast
Послано Mahilewets 19 май 2017 14:50
AC Python2.
Re: Math solution but still not enough fast
Послано Mahilewets 19 май 2017 15:49
Finally AC with C++.  Thanks!