O recunoscută companie internaţională a deschis în oraş două fabrici de ciocolată şi n centre de distribuţie. Fabricile produc un singur sortiment de ciocolată şi utilizează ca ambalaj un singur model de cutii. Fiind o companie eficientă dar preocupată de reducerea poluării în oraş, pentru livrarea săptămânală a comenzilor la centrele de distribuţie se foloseşte doar o maşină. Au fost estimate costurile de transport a unei cutii cu ciocolată de la fiecare dintre cele două fabrici la fiecare centru. În fiecare săptămână, producţia cumulată a celor două fabrici acoperă exact cererile celor n centre.

Cerința

Scrieţi un program care calculează costul minim de transport săptămânal pentru livrarea comenzilor la cele n centre de distribuţie, cunoscând cantităţile produse de cele două fabrici, cererea fiecărui centru de distribuţie şi costurile de transport ale unei cutii cu ciocolată de la fiecare fabrică la fiecare centru.

Date de intrare

Fișierul de intrare centre.in Fişierul de intrare centre.in conţine:

pe prima linie: n – numărul de centre, x1 – numărul de cutii cu ciocolată produse de prima fabrică şi x2 – numărul de cutii cu ciocolată produse de a doua fabrică, separate prin câte un spaţiu.
Pe a doua linie: n numere naturale nenule c[1] c[2] … c[n] reprezentând cererile celor n centre de distribuţie, c[i] = numar de cutii de ciocolată solicitate de centrul de distribuție i.
Pe a treia linie: n numere naturale nenule reprezentând costurile de transport ale unei cutii de la prima fabrică la fiecare dintre cele n centre cost[1][1] cost[1][2] … cost[1][n].
Pe a patra linie: n numere naturale nenule reprezentând costurile de transport ale unei cutii de la a doua fabrică la fiecare dintre cele n centre cost[2][1] cost[2][2] … cost[2][n].

Date de ieșire

Fișierul de ieșire centre.out va conţine o singură linie pe care va fi scris un număr natural care reprezintă costul minim de transport săptămânal, pentru satisfacerea tuturor cererilor celor n centre de distribuţie.

Restricții și precizări

1 < n ≤ 200, 1 ≤ c[i] ≤ 20, 1 < x1, x2 < 4000, n ≤ x1 + x2
c[1] + c[2] + … + c[n] = x1 + x2
0 < cost[i][j] ≤ 1000, 1 ≤ i ≤ n, 1 ≤ j ≤ n

Exemplu

centre.in

centre.out

Explicație

O posibilă soluţie ar fi
cost[1][1]*0 + cost[1][2]*4 + cost[1][3]*1 + cost[2][1]*3 + cost[2][2]*0 + cost[2][3]*3 =
5 * 0 + 2 * 4 + 3 * 1 + 5 * 3 + 3 * 0 + 4 * 3 = 38.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema centre:

#include <bits/stdc++.h>
using namespace std;

ifstream fin("centre.in");
ofstream fout("centre.out");

int a[4001], b[4001], suma;
int c[201], cost[2][201], n, x1, x2, h,x[201];

void citire()
{
    int i;
    fin >> n >> x1 >> x2;
    for (i=1; i<=n; i++)
        fin >> c[i];
    for (i=1; i<=n; i++)
        fin >> cost[0][i];
    for (i=1; i<=n; i++)
        fin >> cost[1][i];
}

void sol()
{
    int min1, max1, min2, max2, h,k, i;
    int min=c[1]<x1?c[1]:x1;
    for (i=0; i<=min; i++)
        a[i]=cost[0][1]*i+cost[1][1]*(c[1]-i);
    suma=c[1];
    for (k=2; k<=n; k++)
    {
       min1=suma+c[k]<x1?suma+c[k]:x1;
       max2=suma+c[k]-x2>0?suma+c[k]-x2:0;
       for (i=max2; i<=min1; i++)
           {
             b[i]=1000000000;
             max1=i-suma>0?i-suma:0;
             min2=i<c[k]?i:c[k];
             for (h=max1; h<=min2; h++)
                 if (b[i]>(cost[0][k]*h+cost[1][k]*(c[k]-h)+a[i-h]))
                    {
                     b[i]=cost[0][k]*h+cost[1][k]*(c[k]-h)+a[i-h];
                     }
           }
       for (i=max2; i<=min1; i++) a[i]=b[i];
       suma += c[k];
    }
}

int main()
{
    citire();
    sol();
    fout<<a[x1] << "\n";
    fout.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2231 centre

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2231 centre de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2231 centre