2007-01-11 Error501

Przerobilismy

  • Koszt zamortyzowany -> Listy. ( samoorganizujące się struktury danych na przykładnie list z przerzucaniem na początek)
  • Zadania OPSS
  • Dijkstra
  • Skiplisty
  • łączenie kopców

// Grzegorz Wierzowiecki 2007-05
// UAM - Dyktator Mody
 
#include <cstdio>
#include <map>
#include <utility>
 
typedef long long LL ;
typedef std::pair<long,long> pairll;
long n,m,tn;
using std::pair;
using std::map;
 
void init(){
        scanf("%ld %ld", &n, &m);
        scanf("%ld", &tn);
};
 
LL ilosc(long , long);
 
void doit(){
        long t;
        scanf("%ld", &t);
        printf("%lld\n", ilosc(n,t) );
};
 
map<pairll,LL> dyn; //tablica do dynamika
LL ilosc(long n, long t){
        if(t > (n*(m-1)) ) return 0;
        if(n==1) return 1;
        if(dyn.count(pairll(n,t))==1) return dyn[pairll(n,t)];
        LL wyn=0; long i;
        for(i=0; i<m; i++) if(t>=i) wyn += ilosc(n-1,t-i);
        dyn[pairll(n,t)] = wyn;
        return wyn;
};
 
int main(){
        init();
        for(long i=0; i<tn; i++) doit();
        return 0;
};
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License