11526 - H(n)

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

Re: 11526 - H(n)

Post by alamgir kabir » Sat May 23, 2009 3:24 pm

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
New poster
Posts: 7
Joined: Thu Jul 02, 2009 6:37 pm

Re: 11526 - H(n)

Post by liauys » Wed Jul 29, 2009 3:55 pm

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

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 11526 - H(n)

Post by arifcsecu » Wed Sep 30, 2009 2:14 am

Code remove after AC
Last edited by arifcsecu on Wed Sep 30, 2009 11:51 pm, edited 1 time in total.
Try to catch fish rather than asking for some fishes.

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 11526 - H(n)

Post by arifcsecu » Wed Sep 30, 2009 11:59 am

oh i got accepted now
i forget for negative numbers

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

bye
Try to catch fish rather than asking for some fishes.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 11526 - H(n)

Post by saiful_sust » Wed Sep 30, 2009 6:45 pm

Hi arifcsecu
if u got acc then plz remove ur code
:D

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 11526 - H(n)

Post by arifcsecu » Wed Sep 30, 2009 11:53 pm

i am new
thanks for ur ...........
Try to catch fish rather than asking for some fishes.

Aunik_04
New poster
Posts: 1
Joined: Thu Jan 12, 2012 10:39 pm

Re: 11526 - H(n)

Post by Aunik_04 » Thu Jan 12, 2012 10:45 pm

[/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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11526 - H(n)

Post by brianfry713 » Sat Jan 14, 2012 12:20 am

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.
Check input and AC output for thousands of problems on uDebug!

Rashik_kuet_dour
New poster
Posts: 1
Joined: Fri Aug 03, 2012 5:00 pm

Re: 11526 - H(n)

Post by Rashik_kuet_dour » Fri Aug 03, 2012 7:52 pm

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
New poster
Posts: 1
Joined: Tue Jul 10, 2012 7:46 am

Re: 11526 - H(n)

Post by tanveerahmedivan » Thu Feb 07, 2013 1:20 am

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...... :( :cry:

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11526 - H(n)

Post by brianfry713 » Fri Feb 08, 2013 8:48 pm

Input:

Code: Select all

2
0
1
AC output:

Code: Select all

0
1
Check input and AC output for thousands of problems on uDebug!

sdipu
New poster
Posts: 23
Joined: Sun May 19, 2013 1:50 am

Re: 11526 - H(n)

Post by sdipu » Sun May 19, 2013 2:04 am

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
Last edited by sdipu on Sat May 25, 2013 6:48 am, edited 1 time in total.
Check out UVA Arena - a software build for UVA solvers @ http://dipu-bd.github.io/UVA-Arena/

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11526 - H(n)

Post by brianfry713 » Tue May 21, 2013 3:56 am

Try the input in the post before yours. You code is throwing a RE on n=0.
Check input and AC output for thousands of problems on uDebug!

sdipu
New poster
Posts: 23
Joined: Sun May 19, 2013 1:50 am

Re: 11526 - H(n)

Post by sdipu » Sat May 25, 2013 6:50 am

brianfry713 wrote: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
Check out UVA Arena - a software build for UVA solvers @ http://dipu-bd.github.io/UVA-Arena/

Ovro
New poster
Posts: 12
Joined: Mon Nov 11, 2013 8:30 am

Re: 11526 - H(n)

Post by Ovro » Sat Dec 07, 2013 6:56 pm

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;
}

Post Reply

Return to “Volume 115 (11500-11599)”