Very optimized BFS for Addition-chain-exponentiation. Uses the graph special structure to keep only the last layer.

gistfile1.txt

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

#define forn(i,n) for(int i=0;i<int(n);i++)
#define all(c) begin(c), end(c)

const int LARGEST = 12; // Cota basada en repeated squaring, 11 operaciones + el 1 inicial
                        // Igualmente, termina cortando solo antes

const int MAX = 100;
                        
typedef unsigned long long Mask;

struct Set
{
    Mask m[2];
    
    bool empty() const
    {
        return m[0] == 0 && m[1] == 0;
    }
    
    int next() const
    {
        int index = m[0] == 0;
        return 64 * index + __builtin_ctzll(m[index]);
    }
    
    bool add(int elem)
    {
        int index = elem >= 64;
        Mask bit = 1ULL << (elem & 0x3F);
        bool ret = (m[index] & bit) == 0;
        m[index] |= bit;
        return ret;
    }
    
    void del(int elem)
    {
        int index = elem >= 64;
        m[index] -= 1ULL << (elem & 0x3F);
    }
    
    bool operator ==(const Set &o) const
    {
        return m[0] == o.m[0] && m[1] == o.m[1];
    }
    
    bool operator <(const Set &o) const
    {
        if (m[0] != o.m[0])
            return m[0] < o.m[0];
        return m[1] < o.m[1];
    }
};

//int bound(int x)
//{
//    assert(x >= 1);
//    if (x == 1) return 0;
//    return bound(x/2) + 1 + (x%2);
//}

int best[MAX+1];

int main()
{
    // Helper bound (repeated squaring) calculation, not used in the end
    //int maxi = 0;
    //forn(i,100)
    //    maxi = max(maxi, bound(i+1));
    //cout << maxi << endl;
    assert(MAX < 128); // uso de bits
    forn(i,MAX+1)
        best[i] = 1000;
    vector<Set> pending;
    vector<Set> next;
    const Set start = {{2,0}};
    best[1] = 0;
    pending.push_back(start);
    int currentDist = 0;
    while (!pending.empty())
    {
        currentDist++;
        int remaining = 0;
        forn(i,MAX)
            remaining += currentDist < best[i+1];
        if (remaining == 0)
            break;
        cout << "Exploring dist " << currentDist << " with " << remaining << " remaining." << endl;
        next.clear();
        for (Set s : pending)
        {
            int decoded[LARGEST+1];
            Set cop = s;
            int total = 0;
            while (!cop.empty())
                cop.del(decoded[total++] = cop.next());
            forn(i,total)
            forn(j,i+1)
            {
                int x = decoded[i]+decoded[j];
                if (x <= MAX && s.add(x))
                {
                    best[x] = min(best[x], currentDist);
                    if (total < LARGEST)
                        next.push_back(s);
                    s.del(x);
                }    
            }
        }
        cout << "NEXT MEM SIZE:" << next.size() << endl;
        sort(all(next));
        next.resize(unique(all(next)) - next.begin());
        next.swap(pending);
    }
    cout << "SOLUTION:" << endl;
    forn(i,MAX)
        cout << i+1 << " " << best[i+1] << endl;
    return 0;
}