Page 1 of 2

11254 - Consecutive Integers

Posted: Sat Aug 04, 2007 1:23 pm
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;
}

Posted: Sat Aug 04, 2007 1:31 pm
by emotional blind
---CUT---

Posted: Sat Aug 04, 2007 1:36 pm
by hamedv
can you give me some hint :)

Posted: Sat Aug 04, 2007 1:38 pm
by emotional blind
oh sorry.. my solution is not O(1)
it is O(sqrt(2*n))

Posted: Sat Aug 04, 2007 1:40 pm
by pvncad
I have solved this using O(sqrt(n)). emotional blind, any clue on o(1) solution ?

Posted: Sat Aug 04, 2007 1:42 pm
by pvncad
Actually, mine is also O(sqrt(2 *n))

Posted: Sat Aug 04, 2007 1:46 pm
by emotional blind
but chetan's solution is O(n)
that might be the reason behind getting TLE.

Posted: Sat Aug 04, 2007 5:08 pm
by emotional blind
sqrt(2*n) is the upper limit of the length of sequence.

Posted: Sat Aug 04, 2007 5:08 pm
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

Posted: Sat Aug 04, 2007 5:18 pm
by Spykaj
OK, i have ACC...

Posted: Sat Aug 04, 2007 5:24 pm
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

Posted: Sat Aug 04, 2007 5:26 pm
by chetan
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 :(

Posted: Sat Aug 04, 2007 5:30 pm
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

Posted: Fri Aug 10, 2007 1:59 pm
by chetan
is my approach right ????

Posted: Sat Aug 11, 2007 6:53 am
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..