Sunday, October 13, 2013

Problem 53 - C++, now considered separate from C

When I started this challenge, I considered C and C++ to be the same language as one is a subset of the other. This was reasonable at the time, especially as I began this challenge as a timed challenge with a fixed goal, and didn't want to make it too easy for myself by allowing me to use almost all languages I knew. However, now that I am around problem 53, and have experienced extreme similarities between various languages, I think that it is fair to call C and C++ distinct languages: clearly they are distinct, as C++ has so many features not in C, even though most short C++ programs look almost identical to C programs. So, here is my solution to problem 53: the problem was easy enough that I probably didn't need to use C++, but I thought I wanted to get this distinction out of the way before I needed it. The solution runs in 2ms.

Also, for this problem, I finally made a nice script to automate a large part of my work process: before I manually copied files from a working directory to the git repository and then committed, then opened up a GUI text editor to copy and paste. Now, that whole process is automated into a single script (I won't bother posting a link to the script as its mostly just a bunch of cp, cd, and git commands that are very dependent on my personal directory setup). However, I think it is worth noting my discovery of xclip, a nice program that allows copy text to the clipboard from the command line. For example, in order to paste the code for this problem below, I added in my script: cat $1 | xclip -sel clip, and now whenever I add one of my files to the git repository, I also get a copy of the file on my clipboard. Fun stuff.
#include<stdio.h>

int fac(int n) {
    return n < 2 ? 1 : n * fac(n - 1);
}

bool isncrbig(int n, int r) {
    //we calculate very carefully to avoid
    //overflow, and will return true as soon
    //as we see a number > 1000000
    int denom = fac(r);
    long rest = n;
    for (int i = n - 1; i > (n - r); --i) {
        rest *= i;
        if (rest / denom > 1000000) {
            return true;
        }
    }
    return false;
}

int main() {
    int min_r = 10;
    int ans = 0;
    for (int n = 23; n <= 100; ++n) {
        while (isncrbig(n, min_r - 1)) {
            --min_r;
        }
        ans += n - (2*min_r) + 1;
    }
    printf("%d\n", ans);
    return 0;
}

No comments:

Post a Comment