11254 - Consecutive Integers

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

11254 - Consecutive Integers

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

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind »

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

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

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

Post Reply

Return to “Volume 112 (11200-11299)”