Cod sursa(job #2171947)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 15 martie 2018 14:18:44
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
#include <cstring>

typedef long long LL;
const int N = 55, L = 10, B = 1e8;
int n, k, i, j, w, lim;

class nrmare {
    int v[L+2];
    public:
    int& operator[] (const int &x) {
        return v[x];
    }

    void operator+= (nrmare b) {
        int i, t = 0;
        for (i = 1; i <= v[0] || i <= b[0] || t; i++, t /= B) {
            t += v[i]+b[i];
            v[i] = t%B;
        }
        v[0] = i-1;
    }

    void operator= (int n) {
        v[0] = 0;
        while (n)
            v[ ++v[0] ] = n%B, n /= B;
    }
};

nrmare ant[N*N], acum[N*N];

int main() {
    freopen("perm6.in","r",stdin);
    freopen("perm6.out","w",stdout);

    ant[0] = 1;
    scanf("%d %d\n", &n, &k);

    for (i = 2; i <= n; i++) {
        lim = (i-1)*(i-2)/2;
        for (j = 0; j <= lim; j++)
            for (w = 0; w < i; w++)
                acum[j+w] += ant[j];

        memcpy(ant, acum, sizeof(ant));
        memset(acum, 0, sizeof(acum));
    }

    printf("%d", ant[k][ ant[k][0] ]);
    for (i = ant[k][0]-1; i >= 1; i--)
        printf("%08d", ant[k][i]);

    return 0;
}