Dorel și-a achiziționat o fermă cu n plantații și o mașină de transport cu o capacitate c, pentru transportul de îngrășăminte la toate plantațiile. Îngrășămintele se află într-un depozit, în cantitate suficientă pentru scopul propus. Plantațiile și depozitul sunt dispuse sub forma unui cerc. Există drumuri doar între plantația i și plantația i+1 (1≤i≤n-1), precum și între depozit și plantația 1 și depozit și plantația n, ca în figură.
La o plantație i se poate ajunge de la depozit trecând prin plantațiile 1, 2,…, i-1 sau prin plantațiile n, n-1, …, i+1, alegerea făcându-se în funcție de traseul cel mai scurt. Se cunosc aceste distanțe, precum și cantitatea de îngrășăminte necesară pentru fiecare plantație. La fiecare încărcare, Dorel ia din depozit exact cantitatea c. Dorel vrea să-și organizeze bine munca la fermă și să consume cât mai puțină benzină prin alegerea celor mai scurte trasee de parcurs. Plantațiile trebuie să fie aprovizionate obligatoriu în ordinea următoare: mai întâi plantația 1, apoi plantația 2, plantația 3,…, plantația n. În plus, și-a propus să încarce o nouă cantitate de îngrășământ doar după ce a folosit toată cantitatea încărcată anterior. Transportarea îngrășămintelor pe plantații se face deci, începând cu plantația 1. După ce se transportă toată cantitatea necesară pentru această plantație, se trece la plantația 2, și tot așa în ordine la 3, 4 etc. până se deservește ultima plantație. Dacă după ce s-au transportat îngrășămintele necesare pentru plantația i în mașină au mai rămas încă îngrășăminte, acestea trebuie utilizate în continuare pentru alte plantații, alese în ordinea impusă (începând cu plantația i+1, apoi i+2 etc.), până se epuizează toată cantitatea transportată de mașină. Astfel, dacă de la plantația i trebuie să ajungă la plantația i+1, va alege cel mai scurt traseu dintre traseul direct de la plantația i la i+1 și traseul care trece prin plantațiile i-1, i-2, …, 1, depozit, n, n-1, …, i+1. La final, mașina trebuie să se întoarcă la depozit, goală sau cu cantitatea rămasă după aprovizionarea cu îngrășăminte a plantației n.
Cerința
Ajutați-l pe Dorel să calculeze distanța parcursă pentru a transporta îngrășăminte la toate cele n plantații, conform cerințelor.
Date de intrare
Fișierul de intrare fermier.in conține pe prima linie numerele naturale n și c, separate printr-un spațiu. A doua linie conține numerele naturale d[0], d[1], d[2], …, d[n-1], d[n] separate două câte două prin câte un spaţiu, unde d[0] este distanța dintre prima plantație și depozit, d[i] (1≤i≤n-1) este distanța între plantația i și plantația i+1, iar d[n] este distanța dintre plantația n și depozit. Pe linia a treia se găsesc numerele naturale q[1], q[2],…, q[n-1], q[n] separate două câte două prin câte un spaţiu, q[i] reprezentând cantitatea de îngrășăminte necesară pentru plantația i (1≤i≤n).
Date de ieșire
Fișierul de ieșire fermier.out va conține pe prima linie un număr natural conform cerinţei.
Restricții și precizări
1 ≤ n ≤ 1001 ≤ n ≤ 2, pentru teste în valoare de 20 de puncte;1 ≤ d[i] ≤ 1000,1 ≤ i ≤ n;1 ≤ q[i] ≤ 1000,1 ≤ i ≤ n;1 ≤ c ≤ 1000;- În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemplu.
Exemplu
fermier.in
3 6 1 10 2 3 13 2 7
fermier.out
22
Explicație
La plantația 1 trebuie transportată o cantitate egală cu 13, valoarea maximă pe care o poate transporta mașina fiind de 6. La plantația 1 se ajunge pe drumul cel mai scurt direct de la depozit. Astfel se va merge mai întâi cu cantitatea 6, ne întoarcem la depozit, încărcam iar mașina, ducem 6, ne întoarcem, încărcăm și lăsăm doar 1 (atât mai este necesar). Pentru aceasta, s-a parcurs distanța de 1+1+1+1+1=5. În mașină a mai rămas acum o cantitate egală cu 5. Trebuie să mergem acum la plantația 2 pe drumul cel mai scurt. Pe drumul direct distanța este 10, iar pe drumul invers care trece iar prin depozit este 6 (1+3+2). Vom alege drumul cu distanța 6. Lăsăm cantitatea 2 (atât e necesar plantației 2), ne mai rămân 3 și pentru plantația 3. De la plantația 2 se ajunge direct la plantația 3 pe o distanță egală cu 2 sau invers, trecând prin depozit pe o distanță de 14 (10+1+3). Alegem drumul cu distanța 2. Lăsăm îngrășămintele rămase și mai mergem iar la depozit, încărcăm și lăsăm 4 la plantația 3. Pentru aceasta mai parcurgem distanța 3+3. La final mașina trebuie să se întoarcă la depozit, deci încă un drum cu distanța 3. În total: 5+6+2+6+3=22.
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 Fermier:
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("fermier.in");
ofstream g("fermier.out");
long long maxx, sens[102],st[102],dr[102],n, d[102], p[102];
void deplasari_st_dr(int i)
{ int j;
if (i==1)
{st[i]=d[0];
dr[i]=0;
for (j=n;j>=1;j--)
dr[i]+= d[j];
}
else
if (i==n)
{
dr[i]=d[n];
st[i]=d[0];
for(j=1;j<=n-1;j++)
st[i]+=d[j];
}
else
{
st[i]=st[i-1]+d[i-1];
dr[i]=dr[i-1]-d[i-1];
}
if (st[i]<dr[i])
sens[i]=1;
else
sens[i]=-1;
}
int km()
{ long long nr,nr1,rest;
int i,j,depoz;
nr=0;
depoz=0;
i=1;
rest=maxx;
while (i<=n)
{
if (depoz==0)
{ rest=maxx;
if (p[i]!=0)
if (sens[i]==1)
{
nr1=p[i]/maxx;
nr+=nr1*2*st[i];
rest=maxx*nr1;
if (p[i]%maxx!=0)
{
nr+=st[i]; depoz=1;rest+=maxx;}
if (rest<p[i])
{
rest=0;
p[i]-=rest;
}
else
{
rest=rest-p[i];
p[i]=0;
}
}
else
{
nr1=p[i]/maxx;
nr+=nr1*2*dr[i];
rest=maxx*nr1;
if (p[i]%maxx!=0)
{
nr+=dr[i]; depoz=1; rest+=maxx;
}
if (rest<=p[i])
{
p[i]-=rest;
rest=0;
}
else
{
rest=rest-p[i];
p[i]=0;
}
}
else i++;
}
else
if (rest==0 || i==n)
//ma intorc in depozit
if (sens[i]==1)
{
nr+=st[i];
depoz=0;
if (p[i]==0) i++;
}
else
{
nr+=dr[i];
depoz=0;
if (p[i]==0) i++;
}
else
{
//merg la urmatorul
if (d[i]<st[i]+dr[i+1])
nr+=d[i];
else
nr+=st[i]+dr[i+1];
if (rest<p[i+1])
{
p[i+1]-=rest;
rest=0;
depoz=1;
}
else
{
rest-=p[i+1];
p[i+1]=0;
}
i++;
}
}
return nr;
}
int main()
{ int i;
f>>n>>maxx;
for(i=0;i<=n;i++)
f>>d[i];
for(i=1;i<=n;i++)
f>>p[i];
for (i=1;i<=n;i++)
deplasari_st_dr(i);
g<<km();
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 
.
Rezolvarea problemei #2010 Fermier
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2010 Fermier 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!