## 11526 - H(n)

Moderator: Board moderators

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

### Re: 11526 - H(n)

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.
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.
Thnx everybody.
alamgir

liauys
New poster
Posts: 7
Joined: Thu Jul 02, 2009 6:37 pm

### Re: 11526 - H(n)

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)

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)

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)

Hi arifcsecu
if u got acc then plz remove ur code

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

### Re: 11526 - H(n)

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)

[/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)

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)

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)

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

### Re: 11526 - H(n)

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)

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

Code: Select all

``````removed after ac
``````
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)

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)

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)

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