11526 - H(n)

[alamgir kabir]

I have tested more than 10000 test case not so big but the code given in the problem set gives the same result that this code give.
I also check the test case that MRH gave me and this also ok now
But I am getting WA again and again.
I will be mad.............
What's wrong with this code.
Can any one explain why i am getting WA again and again though all the test case passed.
I will be ever greatful to him.

Code: Select all

#include<stdio.h>
#include<queue>
#include<math.h>
using namespace std;

int main()
{
    /*freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);*/

    long long test, num, i, sq, a, b, sum;
    queue< long long > q1, q2;

    scanf("%lld", &test);

    while( test -- )
    {
        scanf("%lld", &num);
        if( num == 0 )
        {
            printf("0\n");
            continue;
        }

        sq = sqrt( num );

        q1.push( num );
        q2.push( 1 );

        for( i = 2; i <= sq; i ++ )
        {
            if( i != num / i )
            {
                q2.push( i );
            }
            q1.push( num / i );
        }

        sum = q1.front();
        a = q1.front();

        /*printf("%ld\n", q1.front());*/

        q1.pop();

        while( !q1.empty() )
        {
            /*printf("%ld\n", q1.front());*/

            sum += q1.front();
            /*printf("sum %ld\n", sum);*/
            b = q1.front();

            q1.pop();

            if( !q2.empty() )
            {
                /*printf("%ld\n", q2.front());*/
                sum += q2.front() * ( a - b );
                q2.pop();
            }
            a = b;
        }
        while( !q2.empty() )
        {
            sum += q2.front() * ( a - q2.front() );
            q2.pop();
        }
        printf("%lld\n", sum);
    }
    return 0;
}

I have read all the post here but not getting new.
please help me.
Thnx everybody.
alamgir

[liauys]

To kabir, don't forget there might be negative numbers given in the input set.

[arifcsecu]

Code remove after AC

[arifcsecu]

oh i got accepted now
i forget for negative numbers

when n<=0
printf("\n");

bye

[saiful_sust]

Hi arifcsecu
if u got acc then plz remove ur code

[arifcsecu]

i am new
thanks for ur ...........

[Aunik_04]

[/code]#include<stdio.h>
#include<math.h>
int main()
{
long int dem,n,i,kase,j;
scanf("%ld",&kase);
for(j=0;j<kase;j++)
{
scanf("%ld",&n);
dem=n/2;
long long int res=0;
for(i=1;i<=dem;i++)
res+=n/i;
res=res+(n-dem);
printf("%lld\n",res);
}
return 0;
}


i got time limit error.. whats the problem??

[brianfry713]

You get TLE because you have a loop of n/2 including a divide. For n=2147483647, how long does your code take to run? Read this thread for ideas on a faster algorithm.

[Rashik_kuet_dour]

my program is giving right output for all 9 digit numbers. but when i input 2147463638.my program gives 46475329054 as output where the actual output should be 46475375394.can't figure out what the problem is...






#include<iostream>
#include<math.h>
using namespace std;
int main ()
{
int test, j;
long long sum,i,n,b4, res;
double root_n;
cin>>test;
for(j=1; j<=test; j++)
{
cin>>n;
if (n<1)
{
cout <<0<<'\n';
continue;
}
if(n==2)
{
sum=3;
cout<<sum<<'\n';
continue;
}
if(n==3)
{
sum=5;
cout<<sum<<'\n';
continue;
}
sum=n;
b4=n;
root_n=sqrt(n);
for(i=2; i<=root_n; i++)
{
res=n/i;
sum=sum+res+(b4-res)*(i-1);
b4=res;
}
cout<<sum<<'\n';
}
return 0;
}

[tanveerahmedivan]

Code: Select all

#include<stdio.h>
#include<math.h>
int main()
{
	
	long long int t,k,n,i,j,l,m,a,b,c;
	while(scanf("%lld",&t)!=EOF)
	{
		for(k=1;k<=t;k++)
		{
			scanf("%lld",&n);
			if(n<=0)printf("\n");
			else
			{
				j=sqrt(n);
				l=n;
				b=n;
				for(i=2;i<=j;i++)
				{
					a=(n/i);
					c=b-a;
					l=l+(c*(i-1));
					l=l+(n/i);
					b=a;
				}
				
				for(i=b;i>j;i--)
					l=l+(n/i);
				
				printf("%lld\n",l);
			}
		}
	}
	return 0;
}

Wrong ans why......

[brianfry713]

Input:

Code: Select all

2
0
1

AC output:

Code: Select all

0
1

[sdipu]

I tried this problem at least 30 times. But every time I get WA for this code :

Code: Select all

removed after ac

I checked several input-outputs. but i couldn't find my mistake. Please help

[brianfry713]

Try the input in the post before yours. You code is throwing a RE on n=0.

[sdipu]

Try the input in the post before yours. You code is throwing a RE on n=0.

I rebuilded my code again and again. but at last it was this simple silly mistake
Thanks a lot brianfry. :p

[Ovro]

I am getting TLE.
If the input is 50, 1 will have to be added to the sum for 25 times(for i=26 to i=50).
Then 2 will have to be added for 18 times(for i=16 to i=25).
3 will have to be added for 4 times(for i = 12 to i=16)
I am doing this till sqrt of n.
Then i am doing the rest of the process in that ordinary way.(sum=sum+n/i);
Is my algorithm ok? Is it quick enough ? Plz someone answer. I am getting TLE.

Code: Select all

#include<stdio.h>
#include<math.h>
int main()
{
    long int i,k,num;
    int test,rt;
    long int sum;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%ld",&num);
        if(num<0)
            continue;
        rt=pow(num,.5);
        sum=0;
        for(k=1;k<=rt;k++)
            sum=sum+(num/k-num/(k+1))*k;
        for(i=1;num/i>rt;i++)
            sum=sum+num/i;
        printf("%lld\n",sum);
    }
    return 0;
}