## 11254 - Consecutive Integers

Moderator: Board moderators

Piklu_sust
New poster
Posts: 23
Joined: Fri Sep 01, 2006 10:17 am
Location: CSE, SUST
Anyone who don't get ACC or idea to solve this problem:

Partitions into Consecutive Integers

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

I think it will be helpful for solving the problem.

anderson101866
New poster
Posts: 5
Joined: Sat Jul 28, 2007 6:33 am
Location: Taiwan
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
A lot of cases are posted here already. You should post your code if it passes all the cases provided.
Ami ekhono shopno dekhi...
HomePage

Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 11254 - Consecutive Integers

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
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: 11254 - Consecutive Integers

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
try_try_try_try_&&&_try@try.com
This may be the address of success.

Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 11254 - Consecutive Integers

Thanks,got acc

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### 11254 - Consecutive Integers

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

``````
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

mintae71
New poster
Posts: 18
Joined: Tue Jan 19, 2010 10:50 am

### Re: 11254 - Consecutive Integers

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
New poster
Posts: 18
Joined: Tue Jan 19, 2010 10:50 am

### Re: 11254 - Consecutive Integers

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
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am