## 11254 - Consecutive Integers

Moderator: Board moderators

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm

### 11254 - Consecutive Integers

hi all.
why TLE ????

Code: Select all

``````# include <iostream>
# include <cmath>

using namespace std;

int main()
{
long long x;

while(cin>>x)
{
if(x==-1)
return 0;

if(x == 0){
cout<<"0 = 0 + ... + 0\n";
continue;
}

unsigned long long c = x*2;
for(long long i=1;i<=x;i++)
{

long long b = 2*i-1;
double y = sqrt(b*b + 4*c);
if(!(y-(long long)y))
{

cout<<x<<" = "<<i<<" + ... + "<<i-1+((-b)+(long long)y)/(2)<<'\n';
break;
}
}
}
return 0;
}
``````

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
---CUT---
Last edited by emotional blind on Sat Aug 04, 2007 1:40 pm, edited 1 time in total.

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am
can you give me some hint

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
oh sorry.. my solution is not O(1)
it is O(sqrt(2*n))

New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm
I have solved this using O(sqrt(n)). emotional blind, any clue on o(1) solution ?

New poster
Posts: 27
Joined: Sun Feb 18, 2007 2:14 pm
Actually, mine is also O(sqrt(2 *n))

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
but chetan's solution is O(n)
that might be the reason behind getting TLE.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
sqrt(2*n) is the upper limit of the length of sequence.

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am
n can be expressed as summation of terms:

m + (m+1) + (m+2) + .... + (m+k) = n

which can be written as: A * B = 2*n
Last edited by rushel on Sat Aug 04, 2007 5:27 pm, edited 1 time in total.

Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm
OK, i have ACC...

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:
Can someone please check my Output.

Input:

Code: Select all

``````152
3265
159
6512
65120
4875
48750
4561
1654
987
988
999
1235
230
650
390
9871
98710
4590
4599
65480
6580
981120
98110
651123
11100
111000
2321
78451
784510
7845100
78451000
6451
7465
74650
740
790
990
3265
4590
-1
``````
My Output:

Code: Select all

``````152 = 2 + ... + 17
3265 = 3265 + ... + 3265
159 = 159 + ... + 159
6512 = 6512 + ... + 6512
65120 = 65120 + ... + 65120
4875 = 4875 + ... + 4875
48750 = 13 + ... + 312
4561 = 4561 + ... + 4561
1654 = 1654 + ... + 1654
987 = 3 + ... + 44
988 = 988 + ... + 988
999 = 9 + ... + 45
1235 = 1235 + ... + 1235
230 = 2 + ... + 21
650 = 650 + ... + 650
390 = 390 + ... + 390
9871 = 9871 + ... + 9871
98710 = 98710 + ... + 98710
4590 = 12 + ... + 96
4599 = 4599 + ... + 4599
65480 = 65480 + ... + 65480
6580 = 6580 + ... + 6580
981120 = 981120 + ... + 981120
98110 = 98110 + ... + 98110
651123 = 651123 + ... + 651123
11100 = 11100 + ... + 11100
111000 = 111000 + ... + 111000
2321 = 2321 + ... + 2321
78451 = 78451 + ... + 78451
784510 = 784510 + ... + 784510
7845100 = 7845100 + ... + 7845100
78451000 = 78451000 + ... + 78451000
6451 = 6451 + ... + 6451
7465 = 7465 + ... + 7465
74650 = 74650 + ... + 74650
740 = 2 + ... + 38
790 = 790 + ... + 790
990 = 1 + ... + 44
3265 = 3265 + ... + 3265
4590 = 12 + ... + 96
``````

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm
i have changed the for loop to

Code: Select all

``````
for(long long i=1;i*i<=2*x;i++)

``````
but now i get WA
Last edited by chetan on Sat Aug 04, 2007 5:31 pm, edited 1 time in total.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
DP wrote:Can someone please check my Output.

Input:

Code: Select all

``````152
3265
159
6512
65120
4875
48750
4561
1654
987
988
999
1235
230
650
390
9871
98710
4590
4599
65480
6580
981120
98110
651123
11100
111000
2321
78451
784510
7845100
78451000
6451
7465
74650
740
790
990
3265
4590
-1
``````
My Output:

Code: Select all

``````152 = 2 + ... + 17
3265 = 3265 + ... + 3265
159 = 159 + ... + 159
6512 = 6512 + ... + 6512
65120 = 65120 + ... + 65120
4875 = 4875 + ... + 4875
48750 = 13 + ... + 312
4561 = 4561 + ... + 4561
1654 = 1654 + ... + 1654
987 = 3 + ... + 44
988 = 988 + ... + 988
999 = 9 + ... + 45
1235 = 1235 + ... + 1235
230 = 2 + ... + 21
650 = 650 + ... + 650
390 = 390 + ... + 390
9871 = 9871 + ... + 9871
98710 = 98710 + ... + 98710
4590 = 12 + ... + 96
4599 = 4599 + ... + 4599
65480 = 65480 + ... + 65480
6580 = 6580 + ... + 6580
981120 = 981120 + ... + 981120
98110 = 98110 + ... + 98110
651123 = 651123 + ... + 651123
11100 = 11100 + ... + 11100
111000 = 111000 + ... + 111000
2321 = 2321 + ... + 2321
78451 = 78451 + ... + 78451
784510 = 784510 + ... + 784510
7845100 = 7845100 + ... + 7845100
78451000 = 78451000 + ... + 78451000
6451 = 6451 + ... + 6451
7465 = 7465 + ... + 7465
74650 = 74650 + ... + 74650
740 = 2 + ... + 38
790 = 790 + ... + 790
990 = 1 + ... + 44
3265 = 3265 + ... + 3265
4590 = 12 + ... + 96
``````
MY OUTPUT:

Code: Select all

``````152 = 2 + ... + 17
3265 = 322 + ... + 331
159 = 24 + ... + 29
6512 = 158 + ... + 194
65120 = 44 + ... + 363
4875 = 24 + ... + 101
48750 = 13 + ... + 312
4561 = 2280 + ... + 2281
1654 = 412 + ... + 415
987 = 3 + ... + 44
988 = 43 + ... + 61
999 = 9 + ... + 45
1235 = 14 + ... + 51
230 = 2 + ... + 21
650 = 14 + ... + 38
390 = 10 + ... + 29
9871 = 4935 + ... + 4936
98710 = 4926 + ... + 4945
4590 = 12 + ... + 96
4599 = 27 + ... + 99
65480 = 779 + ... + 858
6580 = 90 + ... + 145
981120 = 127 + ... + 1406
98110 = 4896 + ... + 4915
651123 = 3190 + ... + 3387
11100 = 33 + ... + 152
111000 = 78 + ... + 477
2321 = 95 + ... + 116
78451 = 2046 + ... + 2083
784510 = 1875 + ... + 2254
7845100 = 165 + ... + 3964
78451000 = 6523 + ... + 14122
6451 = 3225 + ... + 3226
7465 = 742 + ... + 751
74650 = 697 + ... + 796
740 = 2 + ... + 38
790 = 30 + ... + 49
990 = 1 + ... + 44
3265 = 322 + ... + 331
4590 = 12 + ... + 96
``````

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm
is my approach right ????

David Kjaer
New poster
Posts: 9
Joined: Sat Jul 07, 2007 5:47 pm
Location: Denmark
It's closer to being correct. There are a few things.
Don't use double since it's unnecessary. Think Gauss-sums..
Randers FC l