Thread: Help with implementing an algorithm!

Hello there!
The following is an implementation of the street numbers problem.
My output stops at the fifth line! probably because of bad memory management or the size of the integers. I tried bigger types like long long but the problem persists.

Code:

#include <stdlib.h>
#include <stdio.h>
int main(int args, char* argv[]){
             int sum1, sum2;
             int count = 0;
             int max = 8;
             int temp = 0;
             while(count < 10){
                         temp =  (max * (max + 1) / 2);
                         for (int house = 1 ; house <=max ; house++){
                             sum1 = house * (house - 1) / 2;
                             sum2 =temp - house - sum1; 
                             if (sum1 == sum2){
                                             printf("%d\t%d\n",house,max);
                                             count++;
                                             }
                             }
                         max++;
                         }
             printf("\t\t\tEnd of Program\n\t\t\t");
             system("PAUSE");
    }

Already tried. The problem still takes a long time to execute the 6th line of input. I've waited a little bit, and it gave me strange results:
6 8
35 49
204 288
1189 1681
6930 9800
256 131072
7742 131528
11707 132113
19813 134033
115619 134705
Normally it should display:
6 8
35 49
204 288
1189 1681
6930 9800
40391 57121
235416 332928
1372105 1940449
7997214 11309768
46611179 65918161
Any hints? I think it has to do with some kind of over-calculation!

Part of the calculation for temp: 57121 * (57121 + 1) overflows the maximum positive value that an integer can hold: 2147483641

i suppose i should have watched the variables a bit longer....!

Ok. I did as told. I changed temp type to long long but I still get the same output as above!

Code:

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char* argv[]){
             long long sum1, sum2;
             int count = 0;
             int max = 8;
             long long temp = 0;
             int house;
             while(count < 10){
                         temp =  (max * (max + 1) / 2);
                         for (house = 1 ; house <=max ; house++){
                             sum1 = house * (house - 1) / 2;
                             sum2 =temp - house - sum1; 
                             if (sum1 == sum2){
                                             printf("%d\t%d\n",house,max);
                                             count++;
                                             }
                             }
                         max++;
                         }
             printf("\t\t\tEnd of Program\n\t\t\t");
             system("PAUSE");
             return 0;
    }

You can't print a long long with %d. %lld, maybe.

I tried what you said tabstop. Still, no output after the 6th line. I undersand the problem with int, but long long didn't fix it.

Two posts about those contests at the same day... I miss being in university...

Now, there is one quite common way to solve problems with a small set of possible inputs, or like this case no input at all: precompute it.
Ah, I remember the good old days on a contest. We had a way too slow solution. But there could only be 100 possible inputs or so. What did we do? Have the program run for 5 minutes and output all solutions followed by a comma. Copy-paste into a new file, into an array with 100 elements, and for whatever input you receive simply output the value the array contains.
Of course, that's only possible with less than about 1000 possible inputs, which is not too common.

In this case you don't have any input at all. What my answer would look like?

Code:

#include <iostream>
using namespace std;

int main()
{
cout<<"6 8"<<endl;
cout<<"35 49"<<endl;
cout<<"204 288"<<endl;
cout<<"1189 1681"<<endl;
cout<<"6930 9800"<<endl;
cout<<"40391 57121"<<endl;
cout<<"235416 332928"<<endl;
cout<<"1372105 1940449"<<endl;
cout<<"7997214 11309768"<<endl;
cout<<"46611179 65918161"<<endl;
}

Actually the output format is wrong, but I'm too lazy to fix that. During the contest you might even pass with a presentation error.

Remember, if you are going to join the contest: you don't have any time. 5 hours sounds like a lot, but it's not nearly enough to solve most problems (especially not with team mates like I had). So a good team is important as well .

Yes, thank you.
Such a solution is lovely, but I'm just trying to solve the problem for my self. So it's really important for me to know what went wrong in my code. Later on, I'll think on doing some math work to make it more efficient. Right now, help me see where this lost it!

Originally Posted by Leojeen

Yes, thank you.
Such a solution is lovely, but I'm just trying to solve the problem for my self. So it's really important for me to know what went wrong in my code. Later on, I'll think on doing some math work to make it more efficient. Right now, help me see where this lost it!

Well, I did some math and it can be a LOT more efficient. In the meantime, your problem:

Code:

sum1 = house * (house - 1) / 2;

As "house" is an int, it will still overflow. Only after the overflow is it converted to a long long. Another advice for programming contests: unless you have to, don't think too much about the types. If you need a long long somewhere, stop using normal integers at all (unless you have huge arrays where it doesn't matter but the extra memory usage would matter).

Ok. This is giving me a headache. I used long long everywhere when I deemed necessary.
Now I get 0s for the max value. Very strange.

Code:

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char* argv[]){
             long long sum1, sum2;
             int count = 0;
             long long max = 8;
             long long temp = 0;
             long long house;
             while(count < 10){
                         temp =  (max * (max + 1) / 2);
                         for (house = 1 ; house <=max ; house++){
                             sum1 = house * (house - 1) / 2;
                             sum2 =temp - house - sum1; 
                             if (sum1 == sum2){
                                             printf("%lld\t%lld\n",house,max);
                                             count++;
                                             }
                             }
                         max++;
                         }
             printf("\t\t\tEnd of Program\n\t\t\t");
             system("PAUSE");
             return 0;
    }

With the program still overflowing irght after the 6th line.