Language War.cpp

/*

[DESAFIO / LANGUAGE WAR] Implemente um programa na sua linguagem favorita onde o usuário digita um número x, e o programa calcula o somatório dos x primeiros números pares da sequência fibonacci, e imprime a soma dos algarismos desse número. 

Por exemplo, quando x = 5, a resposta é 17, pois:
 1. A sequência fibonacci é 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,...
 2. Os 5 primeiros números pares são 0, 2, 8 e 34, 144.
 3. O somatório disso é 188.
 4. Somando os algarismos, 1+8+8 = 17

Rode o programa para o caso X = 100000 usando o comando `echo 100000 | time ./programa`. Confira se a resposta é 282042 e poste aqui o código fonte e o tempo de execução. Ganha a linguagem que tiver o código mais elegante e rápido.

*/

//g++ fib.cpp -ftemplate-depth=10000000 -m64

#include <iostream>
#include <string>

//#include "uint128.h"
typedef unsigned __int128 ull;

template <int T, ull A, ull B> struct fibonacci { enum { 
    value = (ull) fibonacci<T - 1, B, A + B>::value }; };

template <ull A, ull B> struct fibonacci<0, A, B> { enum { value = A }; };

template <int T, int I> struct sum_odd;

namespace conditional {

    template <int T, int I, bool COND> struct selector { enum { 
        value = (ull) fibonacci<I>::value + sum_odd<T - 1, I + 1>::value }; };

	template <int T, int I> struct selector<T, I, false> { enum { 
		value = (ull) sum_odd<T, I + 1>::value }; };

}

template <int T, int I> struct sum_odd { enum { 
	value = conditional::selector<T, I, 
		fibonacci<I>::value % 2 == 0>::value }; };

template <int I> struct sum_odd<0, I> { enum { value = (ull)0 }; };

template <ull N> struct sum_alg { enum {
	value = N % 10 + sum_alg<(N - N % 10) / 10>::value }; };

template <> struct sum_alg<1> { enum { value = (ull)1 }; };
template <> struct sum_alg<0> { enum { value = (ull)0 }; };

template <int N> struct result { enum {
	value = sum_alg<sum_odd<N, 0>::value>::value }; };

template <int K = 100000> struct table {
	enum { max = K };
	static int get(int ix) { 
		if (ix == K) 
			return result<K>::value; 
		else
			return table<K - 1>::get(ix);
	}
};

template <> struct table<0> { 
	enum { max = 0 };
	static int get(int) { return 0; }
};

int main(int argc, char* argv[])
{
	int y;
	std::cin >> y;
	int x = table<>::get(y);
	std::cout << x;
	return 0;
}