HOPE YOU UNDERSTAND.......
By associating with wise people you will become wise yourself
It's fine to celebrate success but it is more important to heed the lessons of failure
We've got to put a lot of money into changing behavior
PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
IDE- Microsoft Visual Studio 2008 Express Edition
Are you sure that's the exact version you're using. Without the %lld it will show a 0 for the max, yes, but this version works just fine (on gcc at least). The results will fit in an unsigned int, so you can also convert it back to an unsigned int and display with "%d". But the solution is too slow to work properly. It's been running here for several minutes and the last line it displayed was "40391 57121"
But doing some more maths I managed to make it run in about 5 seconds.
Edit: 2.2 seconds, but I reckon it can be done even better with more math.
Last edited by EVOEx; 09-04-2009 at 09:21 AM.
Yes, I copied it right from my Dev C++ opened file. Can you give me some hints of your mathematical work so I can do some research later on?
You mean something like this!Ok, I got it now. The problem is that your division is including two ints that's why the rsult will be an int. So change all the variables to long double and in the division part change 2 to 2.0 everywhere. This will result in correct outputs.
It outputs some very long negative doubles.Code:#include <stdlib.h> #include <stdio.h> int main(int argc, char* argv[]){ long double sum1, sum2; int count = 0; long double max = 8; long double temp = 0; long double house; while(count < 10){ temp = (max * (max + 1) / 2.0); for (house = 1.0 ; house <=max ; house++){ sum1 = house * (house - 1) / 2.0; sum2 =temp - house - sum1; if (sum1 == sum2){ printf("%lf\t%lf\n",house,max); count++; } } max++; } printf("\t\t\tEnd of Program\n\t\t\t"); system("PAUSE"); return 0; }
I ran the code and I dont know about the other lines but it's giving the correct output till the 6th line which was wrong with the int version of the code. It's taking too much of time to print after the 6th line which means if you make it more time efficient then using floating point calculations will give you the correct outputs.
Last edited by BEN10; 09-04-2009 at 09:31 AM.
HOPE YOU UNDERSTAND.......
By associating with wise people you will become wise yourself
It's fine to celebrate success but it is more important to heed the lessons of failure
We've got to put a lot of money into changing behavior
PC specifications- 512MB RAM, Windows XP sp3, 2.79 GHz pentium D.
IDE- Microsoft Visual Studio 2008 Express Edition
Don't use doubles. It's wrong here. You get zeroes because apparently your compiler doesn't understand %lld. In gcc it works just fine. Find out how it works on your compiler, or convert to normal integers before outputting with %d, as I said before.
About my math, it started with your equation. Then I changed it to be easier to handle:
That should reduce the number of loops from two to one...Code:(n-1)*n / 2 = (m+1)*m/2 - (n-1)*n/2 - n (n-1)*n + n = (m+1)*m/2 n*n = (m*m+m)/2
BEN10: there's no reason here to use floating point numbers. Because all the numbers actually are integers. Floating point numbers will only cause a possible lack in precision.
Last edited by EVOEx; 09-04-2009 at 09:36 AM.
I guess what I meant was that it's obviously already compiling, so why the desire to go backwards in terms of standards?
Using doubles means you go from 64 significant bits to only 53. The math should all still work unless it overflows 53 bits. It really only makes it slower and less likely to give correct output as the numbers increase.
Nice work EVOEx. I was going for the get it right bit before the optimisation. Hopefully he can follow what you've done there.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
Anyone?
Okay, now let's say you square-root both sides of the equation. Then you have a way to calculate n given m. The other way around (calculating m given n) is faster, but a little bit harder to do. I'll leave that bit up to you.
So now you can CALCULATE n given m in stead of looping through all n's given m. That's a big difference.
(as a side note, n is the Number of the house and m is the Maximum number)
Ok, after doing some math, I made it efficient a little bit in terms of time. But still, the program fails to give me right answers after the 6th line. I think the unsigned long long is not enough.
Don't mind the parsing warnings. I'm aware of them.Code:#include <stdlib.h> #include <stdio.h> #include <math.h> #include <stdint.h> int isPerfectSquare(unsigned long long ); int main(int argc, char* argv[]){ int count = 0; unsigned int max = 8; unsigned long long temp; while(count < 30){ temp = (max * (max + 1))/2; if (isPerfectSquare(temp)){ printf("%.0f\t%d\n",sqrt(temp),max); count++; } max++; } printf("\t\t\tEnd of Program\n\t\t\t"); system("PAUSE"); return 0; } int isPerfectSquare(unsigned long long i){ int temp = sqrt(i); return (temp*temp == i)?1:0; }
And once again you're doing maths with regular integers and only afterwards converting them to longs...
Yes, my mistake.
still blocks after the 6th lines. I had no idea how you did it in 2 seconds.Code:#include <stdlib.h> #include <stdio.h> #include <math.h> #include <stdint.h> int isPerfectSquare(unsigned long long ); int main(int argc, char* argv[]){ int count = 0; unsigned long long max = 8; unsigned long long temp; while(count < 30){ temp = (max * (max + 1))/2; if (isPerfectSquare(temp)){ printf("%.0f\t%d\n",sqrt(temp),max); count++; } max++; } printf("\t\t\tEnd of Program\n\t\t\t"); system("PAUSE"); return 0; } int isPerfectSquare(unsigned long long i){ int temp = sqrt(i); return (temp*temp == i)?1:0; }
I gave you, before, the advice to not use int's in such programs (like programming contests) unless you have a very good reason for that. The reason is that it might be quite difficult to determine whether an integer must be long long or not. In normal programs you have to learn; in contests (if you are going to join a contest), don't bother, don't waste that time.
But my answer remains the same as it was. And I'm not going to repeat another answer in this topic. This is the last time I repeat myself (as I have done many times already):
"And once again you're doing maths with regular integers and only afterwards converting them to longs... "
Ok, I appreciate your help. I don't think repeating the same exact answer is that encouraging but I'll keep working on it. Maybe others will join.
I used unsigned long long everywhere. I don't see myself using integers to do the math.