4220 - Alimentarea Masinii: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: == Cerința == Într-un ținut îndepărtat, un șofer trebuie să călătorească de la un capăt la altul al unui drum lung și pustiu. Pe acest drum există benzinării la diverse distanțe de la punctul de plecare. Mașina șoferului are o capacitate limitată a rezervorului, iar șoferul dorește să ajungă la destinație cu un număr minim de opriri la benzinării pentru a alimenta. == Date de intrare == Programul citește de la tastatură: Un număr întreg distanta_...)
 
Fără descriere a modificării
 
Linia 1: Linia 1:
== Cerința ==
== Cerința ==
Într-un ținut îndepărtat, un șofer trebuie să călătorească de la un capăt la altul al unui drum lung și pustiu. Pe acest drum există benzinării la diverse distanțe de la punctul de plecare. Mașina șoferului are o capacitate limitată a rezervorului, iar șoferul dorește să ajungă la destinație cu un număr minim de opriri la benzinării pentru a alimenta.
Vrei să călătorești n kilometri din orașul A în orașul B cu o mașină care are un rezervor de combustibil care poate asigura un număr de m kilometri. Între cele două orașe sunt amplasate stații de alimentare cu combustibil. Mașina pleacă din orașul A cu rezervorul plin. Vrei să știi numărul minim de alimentări necesare parcurgerii distanței între cele două orașe sau dacă nu se poate parcurge distanța din cauza alimentării (ai o mașină electrică și nu prea sunt stații electrice de alimentare).
== Date de intrare ==
== Date de intrare ==
Programul citește de la tastatură:
Fișierul de intrare masina.in conține pe prima linie numărul n care reprezintă distanța dintre orașele A și B, pe a doua linie numărul m care reprezintă numărul de kilometri care pot fi parcurși cu o alimentare. Pe a treia linie o valoare k reprezentând numărul de stații de alimentare. Pe a patra linie se află un șir de k valori: d[1], d[2], d[3], …, d[k] reprezentând distanța dintre fiecare stație de alimentare și orașul de pornire A.
 
Un număr întreg distanta_totala reprezentând distanța totală până la destinație.
Un număr întreg capacitate_rezervor reprezentând capacitatea rezervorului mașinii.
Un număr întreg numar_benzinarii reprezentând numărul de benzinării de pe drum.
O listă de numar_benzinarii numere întregi reprezentând distanțele la care se află benzinăriile de la punctul de plecare.
== Date de ieșire ==
== Date de ieșire ==
Pe ecran se va afișa numărul minim de opriri necesare pentru a ajunge la destinație. Dacă nu este posibil să ajungi la destinație, se va afișa "-1".
Fișierul de ieșire masina.out va conține pe prima linie numărul a, reprezentând numărul minim de alimentări dintre cele două orașe sau -1 dacă nu se poate parcurge distanța .
== Restricții și precizări ==
== Restricții și precizări ==
*1 ≤ n ≤ 205.000
*1 ≤ m ≤ 400
*1 ≤ k ≤ 1000
*1 ≤ d[i] ≤ n
== Exemplu 1 ==
== Exemplu 1 ==
;Intrare
;Intrare
distanta_totala = 1000
800<br>
capacitate_rezervor = 400
300<br>
numar_benzinarii = 4
4<br>
benzinarii = [200, 375, 550, 750]
200 475 550 750
 
;Iesire
;Iesire
2
3
== Exemplu 2 ==
 
;Intrare
distanta_totala = 500
capacitate_rezervor = 200
numar_benzinarii = 3
benzinarii = [100, 200, 300]
;Iesire
-1
== Rezolvare ==
== Rezolvare ==
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line>
def numar_minim_opriri(distanta_totala, capacitate_rezervor, numar_benzinarii, benzinarii):
def citire_date():
     benzinarii.append(distanta_totala)
    with open("masina.in", "r") as f:
     benzinarii.sort()
        n = int(f.readline().strip())
        m = int(f.readline().strip())
        k = int(f.readline().strip())
        statii = list(map(int, f.readline().strip().split()))
    return n, m, k, statii
 
def minim_opriri(n, m, k, statii):
     statii.append(n) # Adaugam destinatia ca ultima statie
     statii.sort()


     opriri = 0
     opriri = 0
     pozitie_curenta = 0
     pozitie_curenta = 0
     carburant_ramas = capacitate_rezervor
     ultima_oprire = 0
    i = 0


     while pozitie_curenta < distanta_totala:
     for i in range(len(statii)):
        distanta_maxima = pozitie_curenta + carburant_ramas
        if statii[i] - pozitie_curenta > m:
   
             if pozitie_curenta == ultima_oprire:
        while i < len(benzinarii) and benzinarii[i] <= distanta_maxima:
                return -1
             i += 1
            opriri += 1
 
            pozitie_curenta = ultima_oprire
 
         if statii[i] - pozitie_curenta <= m:
        if pozitie_curenta == benzinarii[i - 1]:
             ultima_oprire = statii[i]
            return -1
   
 
    return opriri if pozitie_curenta != n else -1
 
         if pozitie_curenta < distanta_totala:
             pozitie_curenta = benzinarii[i - 1]
            carburant_ramas = capacitate_rezervor
            if pozitie_curenta < distanta_totala:
                opriri += 1
 
    return opriri


def scrie_rezultate(rezultat):
    with open("masina.out", "w") as f:
        f.write(f"{rezultat}\n")


def main():
def main():
     distanta_totala = int(input("Introduceți distanța totală până la destinație: "))
     n, m, k, statii = citire_date()
    capacitate_rezervor = int(input("Introduceți capacitatea rezervorului: "))
    numar_benzinarii = int(input("Introduceți numărul de benzinării: "))
 
    if numar_benzinarii > 0:
        benzinarii = list(
            map(int, input("Introduceți distanțele la care se află benzinăriile, separate prin spațiu: ").split()))
    else:
        benzinarii = []


     rezultat = numar_minim_opriri(distanta_totala, capacitate_rezervor, numar_benzinarii, benzinarii)
     # Verificarea restrictiilor
 
    assert 1 <= n <= 205000, "n trebuie sa fie intre 1 si 205.000"
     if rezultat == -1:
     assert 1 <= m <= 400, "m trebuie sa fie intre 1 si 400"
        print("Nu este posibil să ajungi la destinație.")
    assert 1 <= k <= 1000, "k trebuie sa fie intre 1 si 1000"
     else:
     assert all(1 <= d <= n for d in statii), "fiecare d[i] trebuie sa fie intre 1 si n"
        print(rezultat)


    rezultat = minim_opriri(n, m, k, statii)
    scrie_rezultate(rezultat)


if __name__ == "__main__":
if __name__ == "__main__":
     main()
     main()
</syntaxhighlight>
</syntaxhighlight>

Versiunea curentă din 2 iunie 2024 21:31

Cerința

Vrei să călătorești n kilometri din orașul A în orașul B cu o mașină care are un rezervor de combustibil care poate asigura un număr de m kilometri. Între cele două orașe sunt amplasate stații de alimentare cu combustibil. Mașina pleacă din orașul A cu rezervorul plin. Vrei să știi numărul minim de alimentări necesare parcurgerii distanței între cele două orașe sau dacă nu se poate parcurge distanța din cauza alimentării (ai o mașină electrică și nu prea sunt stații electrice de alimentare).

Date de intrare

Fișierul de intrare masina.in conține pe prima linie numărul n care reprezintă distanța dintre orașele A și B, pe a doua linie numărul m care reprezintă numărul de kilometri care pot fi parcurși cu o alimentare. Pe a treia linie o valoare k reprezentând numărul de stații de alimentare. Pe a patra linie se află un șir de k valori: d[1], d[2], d[3], …, d[k] reprezentând distanța dintre fiecare stație de alimentare și orașul de pornire A.

Date de ieșire

Fișierul de ieșire masina.out va conține pe prima linie numărul a, reprezentând numărul minim de alimentări dintre cele două orașe sau -1 dacă nu se poate parcurge distanța .

Restricții și precizări

  • 1 ≤ n ≤ 205.000
  • 1 ≤ m ≤ 400
  • 1 ≤ k ≤ 1000
  • 1 ≤ d[i] ≤ n

Exemplu 1

Intrare

800
300
4
200 475 550 750

Iesire

3

Rezolvare

def citire_date():
    with open("masina.in", "r") as f:
        n = int(f.readline().strip())
        m = int(f.readline().strip())
        k = int(f.readline().strip())
        statii = list(map(int, f.readline().strip().split()))
    return n, m, k, statii

def minim_opriri(n, m, k, statii):
    statii.append(n)  # Adaugam destinatia ca ultima statie
    statii.sort()

    opriri = 0
    pozitie_curenta = 0
    ultima_oprire = 0

    for i in range(len(statii)):
        if statii[i] - pozitie_curenta > m:
            if pozitie_curenta == ultima_oprire:
                return -1
            opriri += 1
            pozitie_curenta = ultima_oprire
        if statii[i] - pozitie_curenta <= m:
            ultima_oprire = statii[i]
    
    return opriri if pozitie_curenta != n else -1

def scrie_rezultate(rezultat):
    with open("masina.out", "w") as f:
        f.write(f"{rezultat}\n")

def main():
    n, m, k, statii = citire_date()

    # Verificarea restrictiilor
    assert 1 <= n <= 205000, "n trebuie sa fie intre 1 si 205.000"
    assert 1 <= m <= 400, "m trebuie sa fie intre 1 si 400"
    assert 1 <= k <= 1000, "k trebuie sa fie intre 1 si 1000"
    assert all(1 <= d <= n for d in statii), "fiecare d[i] trebuie sa fie intre 1 si n"

    rezultat = minim_opriri(n, m, k, statii)
    scrie_rezultate(rezultat)

if __name__ == "__main__":
    main()
Adus de la „http://wiki.universitas.ro/index.php?title=4220_-_Alimentarea_Masinii&oldid=9886”