同余最短路

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define ll long long
using namespace std;
const int maxn=1e5+10;
ll a,b,c,k,ans[4],dis[maxn],vis[maxn],nxt[maxn];
priority_queue<pair<int,int> >q;
void Dijkstra(){
    memset(dis,0x7f,sizeof(dis));
    dis[0]=0;
    q.push(make_pair(0,0));
    ll u;
    while(!q.empty()){
        u=q.top().second;
        q.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        if(dis[(u+a)%a]>dis[u]+a){
            dis[(u+a)%a]=dis[u]+a;
            nxt[(u+a)%a]=a;
            q.push(make_pair(-dis[(u+a)%a],(u+a)%a));
        }
        if(dis[(u+b)%a]>dis[u]+b){
            dis[(u+b)%a]=dis[u]+b;
            nxt[(u+b)%a]=b;
            q.push(make_pair(-dis[(u+b)%a],(u+b)%a));
        }
        if(dis[(u+c)%a]>dis[u]+c){
            dis[(u+c)%a]=dis[u]+c;
            nxt[(u+c)%a]=c;
            q.push(make_pair(-dis[(u+c)%a],(u+c)%a));
        }
    }
}
int main(){
    cin>>a>>b>>c>>k;
    Dijkstra();
    ll d=dis[k%a];
    while(nxt[d%a]){
        if(nxt[d%a]==a)
            ans[1]++;
        else if(nxt[d%a]==b)
            ans[2]++;
        else
            ans[3]++;
        d-=nxt[d%a];
    }
    d=ans[1]*a+ans[2]*b+ans[3]*c;
    ans[1]+=(k-d)/a;
    cout<<ans[1]<<" "<<ans[2]<<" "<<ans[3];
    return 0;
}