Fişierul intrare/ieşire:fermier1.in, fermier1.outSursăOJI 2017 clasa a 6-a
AutorRoxana TimplaruAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.2 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Fermier1 (clasa a 6-a)

Notă: problema este punctată uşor diferit faţă de original din cauza restricţiilor impuse de evaluatorul infoarena.

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ţă

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 fermier1.in conţine pe prima linie numerele naturale n şi c, separate printr-un spaţiu. A doua linie conţine numerele naturale d0, d1, d2, ..., dn-1, dn separate două câte două prin câte un spaţiu, unde d0 este distanţa dintre prima plantaţie şi depozit, di (1 ≤ i ≤ n-1) este distanţa între plantaţia i şi plantaţia i+1, iar dn este distanţa dintre plantaţia n şi depozit. Pe linia a treia se găsesc numerele naturale q1, q2, ..., qn-1, qn separate două câte două prin câte un spaţiu, qi reprezentând cantitatea de îngrăşăminte necesară pentru plantaţia i (1 ≤ i ≤ n).

Date de ieşire

Fişierul de ieşire fermier1.out va conţine pe prima linie un număr natural conform cerinţei.

Restricţii

  • 1 ≤ n ≤ 100;
  • 1 ≤ n ≤ 2, pentru teste în valoare de 20 de puncte;
  • 1 ≤ di ≤ 1000, 0 ≤ in;
  • 1 ≤ qi ≤ 1000, 1 ≤ in;
  • 1 ≤ c ≤ 1000;
  • Se acordă 10 puncte din oficiu.

Exemplu

fermier1.infermier1.outExplicaţie
3 6
1 10 2 3
13 2 7
22
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici