vatayush's blog

By vatayush, 10 years ago, In English

How can i solve this question? i wrote the following code but it fails for larger test cases:

#include<bits/stdc++.h>
using namespace std;
int main()
{
  while(1)
  {
    long long sum;
    cin>>sum;
    long long int n=sqrt(sum);
    int h=0,len=999999999;
    for(int i=n;i<=2*n;i++)
    {
      //printf("%d\n",i);
      int fh=(i*(i+1))/2;
      if(fh>sum)
	break;
      if(fh==sum)
      {
	if(len>n)
	{
	  cout<<len<<endl;
	  h=i;
	  len=i;
	}
      }
      long long int rem=sum-fh;
      long long int a=2*(i-1)+1;
      if(a*a-8*rem>=0)
      {
	long long int r=(a+sqrt((a*a)-(8*rem)))/2;
	if(2*rem==r*(2*(i-1)+(r-1)*-1))
	{
	  if(len>i+r)
	  {
	    len=i+r;
	    cout<<len<<' '<<i<<endl;
	  }
	}
	if(a>sqrt(a*a-8*rem))
	{
	  long long int r=(a-sqrt((a*a)-(8*rem)))/2;
	  if(2*rem==r*(2*(i-1)+(r-1)*-1))
	  {
	    if(len>i+r)
	    {
	    len=i+r;
	    cout<<len<<' '<<i<<endl;
	    }
	  }
	}
      }
    }
    printf("%d\n",len);
  }
  return 0;
}

	

please help? Edit: sorry, the question was not visible earlier.Now it's visible.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess "int fh=(i*(i+1))/2;" is one of bug.

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    please explain a bit more...in my code 'fh' variable stores sum of first h numbers in sequence f(h,r).and then i am checking if it is possible to get a sum of 'sum -fh' by considering first term as 'i-1' in the arithemetic progression with common difference -1.converting it into long long is also not helping...

  • »
    »
    10 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks dreamoon_love_AA,that was indeed the bug.corrected it :) I was wondering if there is a better way to solve this problem?