2338 - Ski Pass: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: == Cerința == La un parc de sporturi de iarnă au venit G grupuri de schiori numerotate de la 1 la G. Aceștia coboară pe una dintre cele 2 pârtii disponibile dar urcă cu același teleschi. Teleschiul folosește T-bar-uri, o modalitate eficientă de a urca schiorii pe vârful pârtiei. Un T-bar poate trage maxim 2 schiori odată. Deoarece sunt 2 pârtii, se formează 2 rânduri de oameni de-o parte și de alta a punctului de urcare în teleschi. Se știe că 2 schiori nu...)
 
Fără descriere a modificării
 
Linia 1: Linia 1:
== Cerința ==
:
La un parc de sporturi de iarnă au venit G grupuri de schiori numerotate de la 1 la G. Aceștia coboară pe
 
una dintre cele 2 pârtii disponibile dar urcă cu același teleschi. Teleschiul folosește T-bar-uri, o modalitate eficientă de a urca schiorii pe vârful pârtiei.
= Cerința =
La un parc de sporturi de iarnă au venit <code>G</code> grupuri de schiori numerotate de la <code>1</code> la <code>G</code>. Aceștia coboară pe
 
una dintre cele <code>2</code> pârtii disponibile dar urcă cu același teleschi. Teleschiul folosește T-bar-uri, o modalitate eficientă de a urca schiorii pe vârful pârtiei.
 
Un T-bar poate trage maxim <code>2</code> schiori odată. Deoarece sunt <code>2</code> pârtii, se formează <code>2</code> rânduri de oameni de-o parte și de alta a punctului de urcare în teleschi. Se știe că <code>2</code> schiori nu vor folosi același T-bar decât dacă fac parte din același grup. De asemenea, niciun schior nu se baga în fața altuia (toți sunt foarte corecți și răbdători). Atunci când un T-bar sosește, primul om de la una dintre cozi se urcă în el și pleacă sau așteaptă să se


Un T-bar poate trage maxim 2 schiori odată. Deoarece sunt 2 pârtii, se formează 2 rânduri de oameni de-o parte și de alta a punctului de urcare în teleschi. Se știe că 2 schiori nu vor folosi același T-bar decât dacă fac parte din același grup. De asemenea, niciun schior nu se baga în fața altuia (toți sunt foarte corecți și răbdători). Atunci când un T-bar sosește, primul om de la una dintre cozi se urcă în el și pleacă sau așteaptă să se
urce încă cineva (din același grup cu el). Acest al doilea schior trebuie sa fie totuși primul de la coada lui (nimeni nu se bagă în față).
urce încă cineva (din același grup cu el). Acest al doilea schior trebuie sa fie totuși primul de la coada lui (nimeni nu se bagă în față).


Care este numărul minim de T-bar-uri ce trebuie folosite astfel încât toți schiorii de la ambele rânduri să ajungă în vârful pârtiei?
Care este numărul minim de T-bar-uri ce trebuie folosite astfel încât toți schiorii de la ambele rânduri să ajungă în vârful pârtiei?
== Date de intrare ==
Pe prima linie a fișierului de intrare skipassin.txt ​se află numărul de grupuri G. Pe următoarele două linii sunt descrise cele 2 cozi în felul următor: numărul N de oameni de la acea coada urmat de N numere reprezentând grupul din care face parte al i-lea schior (1<=i<=N).
== Date de ieșire ==
În fișierul de ieșire skipassout.txt​ se află un singur număr reprezentând numărul minim de T-bar-uri ce trebuie folosite.
== Restricții și precizări ==
​*'''1 ≤ G ≤ 50'''
*'''1 ≤ N ≤ 1000'''
*Pentru 40% din punctaj una dintre cozi va fi formata doar din oameni din același grup.
*Pentru 60% din punctaj N <= 10
*Pentru 90% din punctaj N <= 300
*Atenție la limita de memorie!
== Exemplul 1 ==
; skipassin.txt
: 4
: 6 1 2 1 3 3 4
: 4 3 1 2 4
; skipassout.txt
: 6
<br>
== Exemplul 2 ==
; skipassin.txt
: 3
: 5 1 2 1 2 3
: 5 3 1 2 3 1
; skipassout.txt
: 4
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#2338 - Ski Pass
def minimum_t_bars(G, queues):
    # Verificăm restricția 1
    if not (1 <= G <= 50):
        return False
   
    # Verificăm restricția 2
    for q in queues:
        if not (1 <= q[0] <= 1000):
            return False
        for person in q[1]:
            if not (1 <= person <= 100):
                return False
   
    # Sortăm cozile în ordine descrescătoare a numărului de oameni din fiecare grup
    queues.sort(key=lambda x: len(set(x[1])), reverse=True)
   
    # Numărul minim de T-bar-uri necesare
    min_t_bars = 0
   
    # Parcurgem cozile
    for q in queues:
        group_set = set(q[1])
       
        # În set-ul group_set vom reține grupurile care încă nu au ajuns sus
        while group_set:
            # Prima persoană din coadă
            first_person = q[1][0]
           
            # Eliminăm grupul la care aparține persoana din group_set
            group_set -= {first_person}
           
            # Eliminăm toate persoanele din coada curentă care fac parte din același grup
            q[1] = q[1][1:]
           
            # Eliminăm și grupurile care au ajuns deja sus și nu mai au membri în coadă
            group_set -= set([x[0] for x in queues if not set(x[1]) & group_set and not x[1]])
           
        # Incrementăm numărul minim de T-bar-uri
        min_t_bars += 1
   
    # Verificăm restricția 3
    if not (min_t_bars <= 2 * G):
        return False
   
    return min_t_bars


# Citim datele de intrare
= Date de intrare =
try:
Pe prima linie a fișierului de intrare <code>skipassIN.txt</code> ​se află numărul de grupuri <code>G</code>. Pe următoarele două linii sunt descrise cele <code>2</code> cozi în felul următor: numărul <code>N</code> de oameni de la acea coada urmat de <code>N</code> numere reprezentând grupul din care face parte al <code>i</code>-lea schior (1<=i<=N).
    with open('skipassin.txt', 'r') as f:
 
        G = int(f.readline().strip())
= Date de ieșire =
        queues = []
În fișierul de ieșire <code>skipassOUT.txt</code> se află un singur număr reprezentând numărul minim de T-bar-uri ce trebuie
        for _ in range(2):
 
            N = int(f.readline().strip())
folosite.
            people = list(map(int, f.readline().strip().split()))
            queues.append((N, people))


    # Calculăm rezultatul
= Restricții și precizări =
    result = minimum_t_bars(G, queues)


    # Verificăm rezultatul și scriem în fișierul de ieșire
* ​<code>1 ≤ G ≤ 50</code>
    if result is not False:
* <code>1 ≤ N ≤ 1000</code>
        with open('skipassout.txt', 'w') as f:
* Pentru 40% din punctaj una dintre cozi va fi formata doar din oameni din același grup.
            f.write(str(result))
* Pentru 60% din punctaj <code>N <= 10</code>
    else:
* Pentru 90% din punctaj <code>N <= 300</code>
        print("Fals")
* Atenție la limita de memorie!
except Exception as e:
    print("Fals")


</syntaxhighlight>
= Exemplu 1: =
<code>skipassIN.txt</code>
4
6 1 2 1 3 3 4
4 3 1 2 4
<code>skipassOUt.txt</code>
6


== Explicatie ==
=== Explicație ===
Schiorii urca în următoarea ordine:
Schiorii urca în următoarea ordine:


Primul de la a 2-a coada singur
Primul de la a <code>2</code>-a coada singur
<br>
 
Primii de la ambele cozi
Primii de la ambele cozi
<br>
 
Primii de la ambele cozi
Primii de la ambele cozi
<br>
 
Primul de la prima coada
Primul de la prima coada
Primii <code>2</code> de la prima coada
Primii de la ambele cozi
= Exemplu 2: =
<code>skipassIN.txt</code>
51
6 1 2 1 3 3 4
4 3 1 2 4
<code>skipassOUt.txt</code>
Datele nu corespund restrictiilor impuse
<br>
<br>
Primii 2 de la prima coada
== Rezolvare ==
<br>
<syntaxhighlight lang="python" line="1">
Primii de la ambele cozi
def verifica_restrictii(g, n1, n2):
    if not (1 <= g <= 50 and 1 <= n1 <= 1000 and 1 <= n2 <= 1000):
        with open("skipassOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse")
        return False
    return True
 
def citeste_datele(filename):
    with open(filename, "r") as fin:
        g = int(fin.readline().strip())
        q1 = list(map(int, fin.readline().strip().split()))
        q2 = list(map(int, fin.readline().strip().split()))
    return g, q1, q2
 
def main():
    g, q1, q2 = citeste_datele("skipassIN.txt")
    n1 = len(q1)
    n2 = len(q2)
 
    if not verifica_restrictii(g, n1, n2):
        return
 
    # Initialize dp array with a large number
    dp = [[float('inf')] * (n2 + 1) for _ in range(n1 + 1)]
    dp[0][0] = 0
 
    for i in range(n1 + 1):
        for j in range(n2 + 1):
            if i > 0:
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
            if j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)
            if i > 0 and j > 0:
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
            if i > 1 and q1[i - 1] == q1[i - 2]:
                dp[i][j] = min(dp[i][j], dp[i - 2][j] + 1)
            if j > 1 and q2[j - 1] == q2[j - 2]:
                dp[i][j] = min(dp[i][j], dp[i][j - 2] + 1)
            if i > 0 and j > 0 and q1[i - 1] == q2[j - 1]:
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
 
    with open("skipassOUT.txt", "w") as fout:
        fout.write(str(dp[n1][n2]))
 
if __name__ == "__main__":
    main()
 
</syntaxhighlight>

Versiunea curentă din 18 mai 2024 13:24

Cerința

La un parc de sporturi de iarnă au venit G grupuri de schiori numerotate de la 1 la G. Aceștia coboară pe

una dintre cele 2 pârtii disponibile dar urcă cu același teleschi. Teleschiul folosește T-bar-uri, o modalitate eficientă de a urca schiorii pe vârful pârtiei.

Un T-bar poate trage maxim 2 schiori odată. Deoarece sunt 2 pârtii, se formează 2 rânduri de oameni de-o parte și de alta a punctului de urcare în teleschi. Se știe că 2 schiori nu vor folosi același T-bar decât dacă fac parte din același grup. De asemenea, niciun schior nu se baga în fața altuia (toți sunt foarte corecți și răbdători). Atunci când un T-bar sosește, primul om de la una dintre cozi se urcă în el și pleacă sau așteaptă să se

urce încă cineva (din același grup cu el). Acest al doilea schior trebuie sa fie totuși primul de la coada lui (nimeni nu se bagă în față).

Care este numărul minim de T-bar-uri ce trebuie folosite astfel încât toți schiorii de la ambele rânduri să ajungă în vârful pârtiei?

Date de intrare

Pe prima linie a fișierului de intrare skipassIN.txt ​se află numărul de grupuri G. Pe următoarele două linii sunt descrise cele 2 cozi în felul următor: numărul N de oameni de la acea coada urmat de N numere reprezentând grupul din care face parte al i-lea schior (1<=i<=N).

Date de ieșire

În fișierul de ieșire skipassOUT.txt se află un singur număr reprezentând numărul minim de T-bar-uri ce trebuie

folosite.

Restricții și precizări

  • ​1 ≤ G ≤ 50
  • 1 ≤ N ≤ 1000
  • Pentru 40% din punctaj una dintre cozi va fi formata doar din oameni din același grup.
  • Pentru 60% din punctaj N <= 10
  • Pentru 90% din punctaj N <= 300
  • Atenție la limita de memorie!

Exemplu 1:

skipassIN.txt 

4
6 1 2 1 3 3 4
4 3 1 2 4

skipassOUt.txt 

6

Explicație

Schiorii urca în următoarea ordine:

Primul de la a 2-a coada singur

Primii de la ambele cozi

Primii de la ambele cozi

Primul de la prima coada

Primii 2 de la prima coada

Primii de la ambele cozi

Exemplu 2:

skipassIN.txt 

51
6 1 2 1 3 3 4
4 3 1 2 4

skipassOUt.txt 

Datele nu corespund restrictiilor impuse


Rezolvare

def verifica_restrictii(g, n1, n2):
    if not (1 <= g <= 50 and 1 <= n1 <= 1000 and 1 <= n2 <= 1000):
        with open("skipassOUT.txt", "w") as fout:
            fout.write("Datele nu corespund restrictiilor impuse")
        return False
    return True

def citeste_datele(filename):
    with open(filename, "r") as fin:
        g = int(fin.readline().strip())
        q1 = list(map(int, fin.readline().strip().split()))
        q2 = list(map(int, fin.readline().strip().split()))
    return g, q1, q2

def main():
    g, q1, q2 = citeste_datele("skipassIN.txt")
    n1 = len(q1)
    n2 = len(q2)

    if not verifica_restrictii(g, n1, n2):
        return

    # Initialize dp array with a large number
    dp = [[float('inf')] * (n2 + 1) for _ in range(n1 + 1)]
    dp[0][0] = 0

    for i in range(n1 + 1):
        for j in range(n2 + 1):
            if i > 0:
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
            if j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)
            if i > 0 and j > 0:
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
            if i > 1 and q1[i - 1] == q1[i - 2]:
                dp[i][j] = min(dp[i][j], dp[i - 2][j] + 1)
            if j > 1 and q2[j - 1] == q2[j - 2]:
                dp[i][j] = min(dp[i][j], dp[i][j - 2] + 1)
            if i > 0 and j > 0 and q1[i - 1] == q2[j - 1]:
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)

    with open("skipassOUT.txt", "w") as fout:
        fout.write(str(dp[n1][n2]))

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