1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <cstdint>
#include <limits>

struct RodzajZelka {
    // int kolor;
    int64_t koszt;
    int16_t waga;
};

static std::string nl{"\n"};
static int64_t INF = std::numeric_limits<int64_t>::max();

typedef std::vector<RodzajZelka> RodzajeZelkow;
typedef std::vector<RodzajeZelkow> KoloroweZelki;
typedef std::unordered_map<int32_t,int64_t> WagaWKoszt;

void dodaj_do_zestawu(WagaWKoszt &zestawy, RodzajeZelkow &rodzaje, int16_t m) {
    WagaWKoszt wynik;
    for (auto &mniejszy: zestawy) {
        for (RodzajZelka &zelek: rodzaje) {
            int32_t waga_wiekszego = (mniejszy.first + zelek.waga) % m;
            int64_t koszt_wiekszego = mniejszy.second + zelek.koszt;
            auto znany_koszt = wynik.find(waga_wiekszego);
            if (znany_koszt == wynik.end() || koszt_wiekszego < znany_koszt->second) {
                wynik[waga_wiekszego] = koszt_wiekszego;
            }
        }
    }
    zestawy.swap(wynik);
}

int64_t mieszaj_zestawy(std::vector<WagaWKoszt> &mapa_zestawow, std::vector<int64_t> &wyniki) {
    std::vector<std::vector<RodzajZelka>> zestawy(mapa_zestawow.size());
    std::vector<int> pozycje(mapa_zestawow.size());
    for (size_t i=1; i<mapa_zestawow.size(); ++i) {
        zestawy[i].reserve(mapa_zestawow[i].size());
        for (auto &zestaw: mapa_zestawow[i]) {
            zestawy[i].push_back({zestaw.second, zestaw.first});
            // std::cerr << "<> " << i << " " << zestaw.second << "←" << zestaw.first << nl;
        }
    }

    int64_t najmniejszy_koszt = INF;

    while (true) {
        int32_t waga = 0;
        int64_t koszt = 0;
        for (size_t i=1; i<zestawy.size(); ++i) {
            RodzajZelka &zelek = zestawy[i][pozycje[i]];
            koszt += zelek.koszt;
            waga += zelek.waga;
        }
        najmniejszy_koszt = std::min(najmniejszy_koszt, koszt);
        waga = waga  % wyniki.size();
        wyniki[waga] = std::min(wyniki[waga], koszt);
        for (size_t i=1; i<=pozycje.size(); ++i) {
            if (i == pozycje.size()) {
                return najmniejszy_koszt;
            }
            ++pozycje[i];
            if (pozycje[i] == (int)zestawy[i].size()) {
                pozycje[i] = 0;
            } else {
                break;
            }
        }
    }
    return najmniejszy_koszt;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int rodzajow;
    int kolorow;
    int m;

    std::cin >> rodzajow >> kolorow >> m;

    KoloroweZelki rodzaje(kolorow+1);
    std::vector<WagaWKoszt> zestawy(kolorow+1);
    std::vector<int64_t> wyniki(m, INF);
    wyniki[0] = 0;

    int16_t kolor;
    int16_t waga;
    int64_t koszt;
    for (int i=0; i<rodzajow; ++i) {
        std::cin >> kolor >> waga >> koszt;
        rodzaje[kolor].emplace_back(koszt, waga);
    }

    for (int i=1; i<=kolorow; ++i) {
        zestawy[i].emplace(0, 0);
        if (rodzaje[i].size() == 0) {
            goto wypisz_wynik;
        }
    }

    for (int i=1; i<=m; ++i) {
        for (int j=1; j<=kolorow; ++j) {
            dodaj_do_zestawu(zestawy[j], rodzaje[j], m);
            // std::cerr << "kolor " << j << " wielkość zestawu " << i << nl;
            // for (auto &zestaw: zestawy[j]) {
                // std::cerr << zestaw.first << "->" << zestaw.second << " ";
            // }
            // std::cerr << nl;
        }
        int64_t najmn = mieszaj_zestawy(zestawy, wyniki);
        if (*std::max_element(wyniki.begin(), wyniki.end()) <= najmn) {
            goto wypisz_wynik;
        }
    }
    // std::cerr << "---" << nl;
wypisz_wynik:;
    for (int i=0; i<m; ++i) {
        if (wyniki[i] == INF) {
            wyniki[i] = -1;
        }
        std::cout << wyniki[i] << nl;
    }
}