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

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 11526 - H(n)

Post by helloneo » Sat Dec 20, 2008 1:05 am

abid_iut wrote:hey helloneo
I am not very clear about ur post
can U pls explain a bit more
what is the output for input 20 pls explain...
The output for 20 is of course..
20 + 10 + 6 + 5 + 4 + 3 + 2 + 2 + 2 + 2 + 1 + 1 + ... + 1

If you calculate until sqrt(n) steps, you may know the result of rest of them..

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11526 - H(n)

Post by Obaida » Sat Dec 20, 2008 9:56 am

Thank you helloneo
This helped me a lot. I was thinking something like that & now it's clear. :)
try_try_try_try_&&&_try@try.com
This may be the address of success.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11526 - H(n)

Post by zobayer » Sun Dec 21, 2008 2:00 pm

hmmm.. helloneo's idea is similar to mine.

lets say n = 20;
k = 1; sum = 0;
so, 20/1 = 20

k = 2
and 20/2 = 10
so, for all the integer divisions, all i = 11 to 20 will produce n/i = 1; (last denominator)
so, you don't need to calculate for 11 to 20, you have 10x1 + 20/1 = 30; (for k = 1)
sum = 30;

k = 3
again 20/3 = 6
so, for all the integer divisions, all i = 7 to 10 will produce n/i = 2; (last denominator)
so, you don't need to calculate for 7 to 10, you have 4x2 + 20/2 = 18; (for k = 2)
sum = sum + 18 = 48;

k = 4
now, 20/4 = 5
so, for all the integer divisions, all i = 6 to 6 will produce n/i = 3; (last denominator)
so, you don't need to calculate for 6, you have 1x3 + 20/3 = 9; (for k = 3)
sum = sum + 9 = 57

as 4 is largest int within sqrt(20),
so lastly you have 1x4 + 20/4 = 9; (for k = 4)
sum = sum + 9 = 66 (ans);
no need to carry any more,

I think you'll now get it. Straight forward idea, will get in time easily. Try in this way for some larger numbers, may be you will be able to find a pattern.

Thanks
You should not always say what you know, but you should always know what you say.

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 11526 - H(n)

Post by abid_iut » Sun Dec 21, 2008 8:52 pm

zobayer can u pls explain the same thing for input 10??
I don't understand why I am taking k=4 for input 20 but not k=3 for input 10.
hope U will help
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11526 - H(n)

Post by zobayer » Mon Dec 22, 2008 12:53 pm

for n = 10; go along the similar way:

lets say n = 10;
k = 1; sum = 0;
so, 10/1 = 10

k = 2
and 10/2 = 5
so, for all the integer divisions, all i = 6 to 10 will produce n/i = 1; (last denominator)
so, you don't need to calculate for 6 to 10, you have 5x1 + 10/1 = 15; (for k = 1)
sum = 15;

k = 3
again 10/3 = 3
so, for all the integer divisions, all i = 4 to 5 will produce n/i = 2; (last denominator)
so, you don't need to calculate for 4 to 5, you have 2x2 + 10/2 = 9; (for k = 2)
sum = sum + 9 = 24;

as k is the largest within sqrt(10);
so last we count for k = 3; for 3, one thing here to note that, 10/3 is also 3, so, in such cases, we have to consider once, cause otherwise it will be counted twice.
so, sum = sum + 3 = 27(ans)

for 10, we have the values (imagine RED is not yet counted, and GREEN is already counted, and BLUE is the current term)
k = 1; (10) + 5 + 3 + 2 + 2 + (1 + 1 + 1 + 1 + 1)
k = 2; 10 + (5) + 3 + (2 + 2) + 1 + 1 + 1 + 1 + 1
k = 3; 10 + 5 + (3) + 2 + 2 + 1 + 1 + 1 + 1 + 1;
so you see, 3 is to be counted once as it has no separate counterpart.
if k==n/k then you need to count once;

hope its now clear.
You should not always say what you know, but you should always know what you say.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11526 - H(n)

Post by Obaida » Tue Dec 23, 2008 9:52 am

I think if you look at this part of my code it will be clear,

Code: Select all

removed
Here n is the input & mid holds the sqrt value
Last edited by Obaida on Sat Dec 27, 2008 7:41 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 11526 - H(n)

Post by abid_iut » Tue Dec 23, 2008 11:59 am

Thankxxxxxxxxxxxxxxxxxxxxx aaaaaaaaaaaaaaaaaaaa looooooooooooooooooooooot
Opu
this problem was making me almost PAGOL
now AC thanks :)
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11526 - H(n)

Post by Obaida » Tue Dec 23, 2008 12:21 pm

This made me think for half an hour very coll to have the solution.
By the way good luck. :)
try_try_try_try_&&&_try@try.com
This may be the address of success.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11526 - H(n)

Post by zobayer » Fri Dec 26, 2008 12:40 pm

@@@Obaida, you have put your full code here, OMG, I fear it's a spoiler, pls remove it as soon as possible.
You should not always say what you know, but you should always know what you say.

Md. Mijanur Rahman
New poster
Posts: 9
Joined: Thu Nov 13, 2008 2:08 pm

Re: 11526 - H(n)

Post by Md. Mijanur Rahman » Tue Feb 24, 2009 8:50 pm

I have got TLE, please anyone honest help me as I am a beginner.
Here is my code

Code: Select all

#include<stdio.h>
int main()
{

	long long n,res,i;
    int j,num;

    scanf("%d",&num);
	for(j=1;j<=num;j++)
	{
	  scanf("%lld",&n);
      if(n<1)
             n=n*(-1);
      res=0;
      for(i=1;i<=n;i=i+1)
      {
            res = (res + n/i);
      }


	  printf("%lld\n",res);
    }
return 0;
}


Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11526 - H(n)

Post by Jan » Thu Feb 26, 2009 5:07 pm

Read the previous posts, please.
Ami ekhono shopno dekhi...
HomePage

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

Re: 11526 - H(n)

Post by alamgir kabir » Fri May 22, 2009 12:59 pm

Anyone help to find my fault. I am getting WA a lot of time.
my code is given below

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int main()
{
    long long res, n, deno, i, temp, sum, test, sq;

    scanf("%lld", &test);

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

        sq = sqrt( n );

        res = n;
        sum = n;
        deno = 1;

        for( i = 2; i <= n; i ++ )
        {
            temp = n / i;
            sum += ( res - temp ) * deno;
            sum += temp;
            deno = i;
            res = temp;
            if( n / ( i + 1 ) <= deno ) break;

        }
        if( n > 1 && n < 4 ) sum --;
        printf("%lld\n", sum);
    }
    return 0;
}

thnx
everyone

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

Re: 11526 - H(n)

Post by MRH » Sat May 23, 2009 7:08 am

hi "alamgir kabir"
i see your code .your procedure is not ok for this problem such as......
input :
2
100000
99999999
my Acc code output :
1166750
1857511487
your code faild for this case

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 7:53 am

Thanks MRH for ur reply. I have to check the problem again?
Am I not the right way? if not, Can u just hint me the way.

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

Re: 11526 - H(n)

Post by MRH » Sat May 23, 2009 8:33 am

Read the previous posts

Post Reply

Return to “Volume 115 (11500-11599)”