Thursday, July 31, 2014

Problem 94 - C++

I had a solution to problem 94 written up in EEL pretty quickly before running into 32-bit integer limitations. Therefore, it was not too hard to then port my solution to C++, especially seeing as I am extremely familiar with the language. Problem 94 was a very different type of problem from the last many. Problems 89-93 seemed to all pretty much be problems of knowing how to enumerate a space. Problem 94 was almost entirely a "do some math to dramatically simplify the problem, then brute force it" approach. The below code probably makes absolutely no sense at first glance, but accompanied by the small page of math that motivated it, this was a nice little problem. Looking at the shortness and simplicity of the below code makes me think I may be resolving this to free up C++ once again in the near future.

Code runs in about 3s on my machine.
#include<stdio.h>
#include<cmath>

long contribution(long x) {
    long c = 0;
    // x as smaller side:
    long temp = 3 * x * x - (2 * x) - 1;
    long root = (long)sqrt((double)temp);
    if (root * root == temp) {
        c += 3 * x + 1;
    }
    // x as larger side:
    temp = 3 * x * x + (2 * x) - 1;
    root = (long)sqrt((double)temp);
    if (root * root == temp) {
        c += 3 * x - 1;
    }
    return c;
}
int main(int argc, char ** argv) {
    long ans = 0;
    //repeated side must be odd
    for (long i = 3; i * 3 < 1000000000; i+=2) {
        ans += contribution(i);
    }
    printf("%ld\n", ans);
    return 0;
}

No comments:

Post a Comment