I submitted your code but i get TLE.
I attached my code.
Wladimir Araujo Tavares
*Federal University of Ceará <http://lia.ufc.br/%7Ewladimir/>
Homepage <http://lia.ufc.br/%7Ewladimir/> |
Maratona<https://sites.google.com/site/quixadamaratona/>|
*
On Fri, Sep 28, 2012 at 12:59 AM, Rahul Singh <[email protected]> wrote:
> the following code is working I get it submitted.you can refer it
>
> #include<iostream>
> #include<stdio.h>
> #include<math.h>
>
> using namespace std;
> long double *ar = new long double[2718275];;
> int ans;
> void bin_search(long double *ar,int st,int end,int a)
> {
> if(st>=end)
> {
> if(ar[st]< log10(a) * st)
> {
> ans = st+1;return;
> }
> else
> {
> ans=st;return;
> }
> }
> int half = (st+end)/2;
> long double gn = log10(a) * half;
> if(ar[half]< gn)
> {
> bin_search(ar,half+1,end,a);
> }
> else if(ar[half]>gn)
> {
> bin_search(ar,st,half-1,a);
> }
> else if(ar[half]==gn)
> {
> ans = half+1;
> return;
> }
> }
> int main()
> {
> long double sum=0;
> ar[0]=0;
> //prerocessing
> for(int i=1;i<=2718274;i++)
> {
> sum +=log10(i);
> ar[i]=sum;
> }
> int t;
> scanf("%d",&t);
> int a;
> while(t--)
> {
> scanf("%d",&a);
> bin_search(ar,0,2718274,a);
> printf("%d\n",ans);
> }
> }
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#define MAX 10001
using namespace std;
int i,t;
long double table[MAX];
//n! = sqrt(2*M_PI*n)(n/e)^n
long double f(int n){
if(n<MAX)
return table[n];
else
return 0.5*log(2*M_PI*n) + n*log(n/M_E);
}
long double g(int a,int n){
if(n==0) return 1;
else{
return n*log(a);
}
}
int menor(int a){
int inicio,meio,fim;
inicio = 2*a;
fim = (int)(M_E*a);
//printf("%lld\n",fim);
while(inicio < fim){
meio = (inicio+fim)/2;
//printf("%lld %lld\n",inicio,fim);
//printf("%lld\n",meio);
//printf("%llf %llf\n", f(meio),g(a,meio));
//system("PAUSE");
if( f(meio) > g(a,meio) ){
fim = meio;
}else{
inicio = meio+1;
}
}
return inicio;
}
int main(){
int a;
table[0] = log(1);
for(i=1;i<MAX;i++)
table[i] = table[i-1] + log(i);
scanf("%d",&t);
for(i=0;i<t;i++){
scanf("%d",&a);
printf("%d\n",menor(a));
}
//system("PAUSE");
}
