11254 - Consecutive Integers

[Piklu_sust]

Anyone who don't get ACC or idea to solve this problem:

Just read the following article:
Partitions into Consecutive Integers

http://www.mathpages.com/home/kmath107.htm

I think it will be helpful for solving the problem.

[anderson101866]

Could anyone please give me more test cases?

I have tested all the input above and I got correct answer.
Besides, I also checked my code and it did not make extra newline.
but I still got WA...

[Jan]

A lot of cases are posted here already. You should post your code if it passes all the cases provided.

[Jehad Uddin]

hello everyone,i m getting TLE for this prob,i m a beginner, pls help me how to decrease time limit....

Code: Select all

 long int a,m,k,n,p,q;
while(cin>>n&&n!=-1)
 {
       a=0;
	 for(m=1;m<n/2;m++)
	 {for(k=1;k<=(int)sqrt(2*n);k++)
	  {
	   if((2*m+k)*(k+1)==2*n)
       {
	    p=m;q=m+k;
		a=1;
		break;

	   }
	   else if((2*m+k)*(k+1)>2*n) break;
	 }
	   if(a==1) break;
	  }
  
 if(!a) cout<<n<<" = "<<n<<" + ... + "<<n<<endl;
 else cout<<n<<" = "<<p<<" + ... + "<<q<<endl;
 }
  

[Obaida]

Try to use S = n/2(2a+(n-1)d) formula.
here d=1. So you don't need to consider about d. Then the formula is simplified as S = n/2(2a+n-1)
Now we also can write a = (2s+n-n^2)/2n
As s is given for all combination of n decide the value of a and output the value..
Very simple. I got 10-12 line code and it runs .024sec

[Jehad Uddin]

Thanks,got acc

[sazzadcsedu]

Can someone tell me why my code gives WA.It passed all the I/O given in the board.Still WA.
Here my code:

Code: Select all

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


 
int Div[5000000];

 
int main()
{
	 unsigned  long long i,x, count,j,k,N, temp,max,pos,lastpos;
	 unsigned long long  u,v,m,n,A,B,p;

	while(scanf("%llu",&N)==1)
	{


		if(N==-1)
			break;

		x=2*N;

		j=0;
		max=0;
		pos=N;

		for(i=1;i<=sqrt(x);)
		{

			if(i%2==0 && (x/i)%2==0)
			{
				i=i+1;
				continue;
			}
			if(x%i==0)
			{
				Div[j++]=i;
				Div[j++]=x/i;
			}

			i=i+1;
		}


		for(i=0;i<j;)
		{
			//printf("%d %d\n",Div[i],Div[i+1]);

			A=2*Div[i];
			B=2*Div[i+1];

			if(A>B)
			{
				temp=B;
				B=A;
				A=temp;
			}

			v=(A+B)/2;

			u=(v-A);

			n=(-1+ (int)sqrt(8*N + pow(u,2)))/2;

			p=n*(n+1)-2*N;

			m=(int)ceil((-1+ sqrt(-1 + 4*p))/2);

			count=0;

			for(k=m+1;k<=n;k++)
			{
				 
				count+=1;
			}

			if(count>=max)
                        {
				max=count;
				pos=m+1;
				lastpos=n;
			}

			i=i+2;
		}
		 
	       printf("%llu =",N);

               printf(" %llu + ...",pos);

               printf(" + %llu",pos+(max-1));

               printf("\n");
	
        }

	return 0;
}

[mintae71]

Actually, I got AC with O(sqrt(n)). But Super dizzy.
I precaculated all the test case.

Code: Select all

if (x%2 == 1){
	if (!a){
		if (y >= (x-1)/2){
			if (y - (x-1)/2 == 0){
				if (mxcnt < x-1){
					sta = 1;
					end = y + (x-1)/2;
					mxcnt = x-1;
				}
			}
			else {
				if (mxcnt < x){
					mxcnt = x;
					sta = y - (x-1)/2;
					end = y + (x-1)/2;
				}
			}
		}
	}
}
if (x%2 == 1){
	if (y%2 == 0) a = true;
	if (!a){
		if ((y-1)/2 - (x-1) >= 0) {
			if ((y-1)/2 - (x-1) == 0){
				if (mxcnt < x*2-1){
					sta = 1;
					end = (y-1)/2+x;
					mxcnt = x*2-1;
				}
			}
			else {
				if (mxcnt < x*2) {
					sta = (y-1)/2-x+1;
					end = (y-1)/2+x;
					mxcnt = x*2;
				}
			}
		}
	}
}
else {
	if (y/2 - (x-1) >= 0) {
		if (y/2 - (x-1) == 0){
			if (mxcnt < x*2-1){
				sta = 1;
				end = y/2+x;
				mxcnt = x*2-1;
			}
		}
		else {
			if (mxcnt < x*2) {
				sta = y/2-x+1;
				end = y/2+x;
				mxcnt = x*2;
			}
		}
	}
}

[mintae71]

Input

Code: Select all

65220
684
772
5
124
888
9431
55575
88888
91124

Output

Code: Select all

65220 = 484 + ... + 603
684 = 17 + ... + 40
772 = 93 + ... + 100
5 = 2 + ... + 3
124 = 12 + ... + 19
888 = 6 + ... + 42
9431 = 4715 + ... + 4716
55575 = 9 + ... + 333
88888 = 193 + ... + 463
91124 = 332 + ... + 540

Hope it helps

[Shafaet_du]

Use long long,i got wa for that.