Cod sursa(job #2675889)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 22 noiembrie 2020 19:14:48
Problema Lapte Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<iostream>
#include<fstream>
#include <algorithm>

using namespace std;

int n, l, dp[100][100][100], Mi=9999, cha[100][100][100], chb[100][100][100];

struct lapte{
    int a;
    int b;
};
lapte v[105];

void compute(int T) {
    dp[0][0][0] = true;
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= l; j++)
        {
            for(int k = 0; k <= l; k++)
            {
                dp[i][j][k] = false;
                int mi = min(T / v[i].a, j);
                for(int a = 0; a <= mi; a++)
                {
                    int b = min(k, (T - a * v[i].a) / v[i].b);
                    if(dp[i - 1][j - a][k - b] == true)
                    {
                        dp[i][j][k] = true;
                        cha[i][j][k] = a;
                        chb[i][j][k] = b;
                    }
                }
            }
        }
    }
}

int fixt(int st, int dr)
{
    if(st == dr)
    {
        return st;
    }
    int T = (st + dr) / 2;

    compute(T);

    if(dp[n][l][l] == true)
    {
        Mi = T;
        fixt(st, T - 1);
    }
    else fixt(T + 1, dr);
}

void intoarcere(int n, int l1, int l2)
{
    if(n == 0) {
        return;
    }
    int a = cha[n][l1][l2];
    int b = chb[n][l1][l2];
    intoarcere(n - 1, l1 - a, l2 - b);
    cout << a << " " << b <<'\n';
}

int main()
{
    freopen("lapte.in","r",stdin);
    freopen("lapte.out","w",stdout);
    cin>>n>>l;
    for(int i = 1; i <= n; i++)
    {
        cin>> v[i].a>> v[i].b;
    }
    fixt(1, 100);
    cout << Mi << '\n';
    compute(Mi);
    intoarcere(n, l, l);
}