Cod sursa(job #2525405)

Utilizator andreibazavanAndrei Bazavan andreibazavan Data 17 ianuarie 2020 12:15:17
Problema Shop Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("shop.in");
ofstream fout("shop.out");
int n,c,x,cat;
bool ok;
long long l,t;
struct bani{
long long v,o,nr;
}a[31];

bool comparo(bani a,bani b)
{
    return a.o<b.o;
}

bool comparv(bani a,bani b)
{
    return a.v<b.v;
}

long long pow(int x,int y)
{
    long long p=1;
    for(int i=1;i<=y;i++)
        p*=x;
    return p;
}

int main()
{
    fin>>n>>c>>l;
    for (int i=1;i<=n;i++)
    {
        fin>>x>>a[i].nr;
        a[i].o=i;
        a[i].v=pow(c,x);
    }
    sort(a+1,a+n+1,comparv);
    for (int i=n;i>=1;i--)
    {
        cat=l/a[i].v;
        if (cat>a[i].nr)
        {
            l=l-a[i].nr*a[i].v;
            t+=a[i].nr;
        }
        else
        {
            a[i].nr=cat;
            l=l-cat*a[i].v;
            t+=cat;
        }
    }
    sort(a+1,a+n+1,comparo);
    fout<<t<<'\n';
    for(int i=1;i<=n;i++) fout<<a[i].nr<<" ";
    fout<<'\n';
    return 0;
}