2338 - Ski Pass: Difference between revisions
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... |
No edit summary |
||
Line 1: | Line 1: | ||
: | |||
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 | |||
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 <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). | |||
= Date de ieșire = | |||
Î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 | |||
folosite. | |||
= Restricții și precizări = | |||
* <code>1 ≤ G ≤ 50</code> | |||
* <code>1 ≤ N ≤ 1000</code> | |||
* Pentru 40% din punctaj una dintre cozi va fi formata doar din oameni din același grup. | |||
* Pentru 60% din punctaj <code>N <= 10</code> | |||
* Pentru 90% din punctaj <code>N <= 300</code> | |||
* Atenție la limita de memorie! | |||
</ | = Exemplu 1: = | ||
<code>skipassIN.txt</code> | |||
4 | |||
6 1 2 1 3 3 4 | |||
4 3 1 2 4 | |||
<code>skipassOUt.txt</code> | |||
6 | |||
== | === 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 | ||
Primii de la ambele cozi | Primii de la ambele cozi | ||
Primii de la ambele cozi | Primii de la ambele cozi | ||
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> | ||
== Rezolvare == | |||
< | <syntaxhighlight lang="python" line="1"> | ||
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> |
Latest revision as of 13:24, 18 May 2024
Cerința[edit | edit source]
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[edit | edit source]
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[edit | edit source]
Î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[edit | edit source]
-
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:[edit | edit source]
skipassIN.txt
4 6 1 2 1 3 3 4 4 3 1 2 4
skipassOUt.txt
6
Explicație[edit | edit source]
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:[edit | edit source]
skipassIN.txt
51 6 1 2 1 3 3 4 4 3 1 2 4
skipassOUt.txt
Datele nu corespund restrictiilor impuse
Rezolvare[edit | edit source]
<syntaxhighlight lang="python" line="1"> 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>