Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/*
[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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment