11254 - Consecutive Integers

chetan · Post by **chetan** » Sat Aug 04, 2007 1:23 pm

hi all.
why TLE ????

# 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 · Post by **emotional blind** » Sat Aug 04, 2007 1:31 pm

---CUT---

hamedv · Post by **hamedv** » Sat Aug 04, 2007 1:36 pm

can you give me some hint

emotional blind · Post by **emotional blind** » Sat Aug 04, 2007 1:38 pm

oh sorry.. my solution is not O(1)
it is O(sqrt(2*n))

pvncad · Post by **pvncad** » Sat Aug 04, 2007 1:40 pm

I have solved this using O(sqrt(n)). emotional blind, any clue on o(1) solution ?

pvncad · Post by **pvncad** » Sat Aug 04, 2007 1:42 pm

Actually, mine is also O(sqrt(2 *n))

emotional blind · Post by **emotional blind** » Sat Aug 04, 2007 1:46 pm

but chetan's solution is O(n)
that might be the reason behind getting TLE.

emotional blind · Post by **emotional blind** » Sat Aug 04, 2007 5:08 pm

sqrt(2*n) is the upper limit of the length of sequence.

rushel · Post by **rushel** » Sat Aug 04, 2007 5:08 pm

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

Spykaj · Post by **Spykaj** » Sat Aug 04, 2007 5:18 pm

OK, i have ACC...

DP · Post by DP » Sat Aug 04, 2007 5:24 pm

Can someone please check my Output.

Input:

Code: Select all

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 · Post by **chetan** » Sat Aug 04, 2007 5:26 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

emotional blind · Post by **emotional blind** » Sat Aug 04, 2007 5:30 pm

DP wrote:Can someone please check my Output.

Input:

Code: Select all

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 · Post by **chetan** » Fri Aug 10, 2007 1:59 pm

is my approach right ????

David Kjaer · Post by **David Kjaer** » Sat Aug 11, 2007 6:53 am

It's closer to being correct. There are a few things.
Don't use double since it's unnecessary. Think Gauss-sums..