All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
-
chetan
- New poster
- Posts: 43
- Joined: Sun Sep 24, 2006 2:39 pm
Post
by chetan »
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;
}
-
hamedv
- Learning poster
- Posts: 98
- Joined: Mon May 07, 2007 8:30 am
Post
by hamedv »
can you give me some hint

-
emotional blind
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
-
Contact:
Post
by emotional blind »
oh sorry.. my solution is not O(1)
it is O(sqrt(2*n))
-
pvncad
- New poster
- Posts: 27
- Joined: Sun Feb 18, 2007 2:14 pm
Post
by pvncad »
I have solved this using O(sqrt(n)). emotional blind, any clue on o(1) solution ?
-
pvncad
- New poster
- Posts: 27
- Joined: Sun Feb 18, 2007 2:14 pm
Post
by pvncad »
Actually, mine is also O(sqrt(2 *n))
-
emotional blind
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
-
Contact:
Post
by emotional blind »
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
- Location: Bangladesh
-
Contact:
Post
by emotional blind »
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
Post
by rushel »
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
Post
by Spykaj »
OK, i have ACC...
-
DP
- Learning poster
- Posts: 62
- Joined: Sun Aug 13, 2006 9:15 am
- Location: Bangladesh
-
Contact:
Post
by DP »
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
Post
by chetan »
i have changed the for loop to
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
- Location: Bangladesh
-
Contact:
Post
by emotional blind »
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
Post
by chetan »
is my approach right ????
-
David Kjaer
- New poster
- Posts: 9
- Joined: Sat Jul 07, 2007 5:47 pm
- Location: Denmark
Post
by David Kjaer »
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