Editing 2010 - Fermier (section)

= Exemplu: =
<code>fermier.in</code>
 3 6
 1 10 2 3
 13 2 7
<code>fermier.out</code>
 22

=== Explicație ===
La plantația <code>1</code> trebuie transportată o cantitate egală cu <code>13</code>, valoarea maximă pe care o poate transporta mașina fiind de <code>6</code>. La plantația <code>1</code> se ajunge pe drumul cel mai scurt direct de la depozit. Astfel se va merge mai întâi cu cantitatea <code>6</code>, ne întoarcem la depozit, încărcam iar mașina, ducem <code>6</code>, ne întoarcem, încărcăm și lăsăm doar <code>1</code> (atât mai este necesar). Pentru aceasta, s-a parcurs distanța de <code>1+1+1+1+1=5</code>. În mașină a mai rămas acum o cantitate egală cu <code>5</code>. Trebuie să mergem acum la plantația <code>2</code> pe drumul cel mai scurt. Pe drumul direct distanța este <code>10</code>, iar pe drumul invers care trece iar prin depozit este <code>6</code> (<code>1+3+2</code>). Vom alege drumul cu distanța <code>6</code>. Lăsăm cantitatea <code>2</code> (atât e necesar plantației <code>2</code>), ne mai rămân <code>3</code> și pentru plantația <code>3</code>. De la plantația <code>2</code> se ajunge direct la plantația <code>3</code> pe o distanță egală cu <code>2</code> sau invers, trecând prin depozit pe o distanță de <code>14</code> (<code>10+1+3</code>). Alegem drumul cu distanța <code>2</code>. Lăsăm îngrășămintele rămase și mai mergem iar la depozit, încărcăm și lăsăm <code>4</code> la plantația <code>3</code>. Pentru aceasta mai parcurgem distanța <code>3+3</code>. La final mașina trebuie să se întoarcă la depozit, deci încă un drum cu distanța <code>3</code>. În total: <code>5+6+2+6+3=22</code>.

<syntaxhighlight lang="python" line="1">
def shortest_distance(depot_to_1, depot_to_n, distances, c, requirements):
    n = len(requirements)
    total_distance = 0
    current_fertilizer = 0

    # Helper function to calculate shortest path between two plantations
    def calculate_shortest_path(i, j):
        if i < j:
            direct_path = sum(distances[i:j])
        else:
            direct_path = sum(distances[j:i])
        through_depot = depot_to_1 + depot_to_n
        return min(direct_path, through_depot)

    # Start from depot to the first plantation
    total_distance += depot_to_1
    current_index = 0

    while current_index < n:
        # If not enough fertilizer, go back to depot
        if current_fertilizer < requirements[current_index]:
            total_distance += depot_to_1  # Return to depot
            current_fertilizer = c
            total_distance += depot_to_1  # Go back to the current plantation

        # Fulfill the current plantation's requirement
        while current_index < n and current_fertilizer >= requirements[current_index]:
            current_fertilizer -= requirements[current_index]
            current_index += 1
            if current_index < n:
                total_distance += calculate_shortest_path(current_index - 1, current_index)

    # Return to depot after the last plantation
    total_distance += depot_to_1

    return total_distance

# Example of usage:
depot_to_1 = 10
depot_to_n = 15
distances = [5, 8, 10, 12, 6]  # Distances between consecutive plantations
c = 20  # Capacity of the truck
requirements = [5, 10, 8, 12, 6]  # Fertilizer requirements for each plantation

result = shortest_distance(depot_to_1, depot_to_n, distances, c, requirements)
print(result)
</syntaxhighlight>