## 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)

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)

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)

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)

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)

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)

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)

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)

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)

@@@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)

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)

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)

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)

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)

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)

Read the previous posts