2676 - Afise - Revision history

Oros Ioana Diana at 17:19, 18 May 2024

2024-05-18T17:19:08Z

Oros Ioana Diana at 17:24, 8 January 2024

2024-01-08T17:24:53Z

← Older revision		Revision as of 17:24, 8 January 2024
Line 1:		Line 1:
			Campania electorală s-a terminat de mult, dar zidul din parcul central al oraşului în care au fost puse afişele este încă într-o formă dezolantă. Ploile şi vântul au acţionat şi au urâţit şi mai mult această zonă pe care altă dată erau afişe frumos colorate. Primăria a decis să se ocupe de această problemă. A format o comisie şi a decis realizarea unor panouri reclamă care să ascundă porţiunile deteriorate. Deoarece fondurile sunt mici s-a decis să fie alocate doar un anumit număr de panouri publicitare care trebuie să ocupe o suprafaţă cât mai mică posibil. Comisia a primit datele din teren sub forma: lungime zid, câte unităţi sunt ocupate cu afişe ce trebuie acoperite şi care este numărul de panouri pe care le poate folosi. De asemenea se primesc ca date şi care sunt unităţile de zid ocupate cu afişe deja deteriorate.
	== Cerința ==		== Cerința ==
	Fiind date lungimea zidului, câte unităţi sunt deteriorate, care este numărul maxim de panouri ce pot fi folosite şi care sunt unităţile de zid deteriorate, se cere să se determine lungimea minimă totală a panourilor care sunt folosite pentru a acoperi zona şi câte panouri se folosesc. Lungimea minimă o definim ca numărul total de unităţi de zid acoperite astfel încât să fie mascate zonele problemă. Pentru acoperirea unităţilor de zid deteriorate, nu este neapărat necesar să se folosească toate panourile. Numărul de panouri folosite fiind limitat există posibilitatea să fie acoperite şi zone din zid care sunt curate.		Fiind date lungimea zidului, câte unităţi sunt deteriorate, care este numărul maxim de panouri ce pot fi folosite şi care sunt unităţile de zid deteriorate, se cere să se determine lungimea minimă totală a panourilor care sunt folosite pentru a acoperi zona şi câte panouri se folosesc. Lungimea minimă o definim ca numărul total de unităţi de zid acoperite astfel încât să fie mascate zonele problemă. Pentru acoperirea unităţilor de zid deteriorate, nu este neapărat necesar să se folosească toate panourile. Numărul de panouri folosite fiind limitat există posibilitatea să fie acoperite şi zone din zid care sunt curate.
	== Date de intrare ==		== Date de intrare ==
	Fișierul de intrare ~~afise~~.in conţine pe prima linie trei valori separate prin câte un spaţiu L n k, cu semnificația: L lungimea totală a zidului, n numărul de unităţi ce urmează a fi acoperite şi k numărul maxim de panouri ce pot fi folosite. Pe a doua linie separate prin câte un spațiu sunt n valori x1, x2, … , xn, unde xi reprezintă unitatea din zid care este acoperită de un afiș vechi. Valorile x1, x2, … , xn apar într-o ordine aleatoare.		Fișierul de intrare afisein.txt conţine pe prima linie trei valori separate prin câte un spaţiu L n k, cu semnificația: L lungimea totală a zidului, n numărul de unităţi ce urmează a fi acoperite şi k numărul maxim de panouri ce pot fi folosite. Pe a doua linie separate prin câte un spațiu sunt n valori x1, x2, … , xn, unde xi reprezintă unitatea din zid care este acoperită de un afiș vechi. Valorile x1, x2, … , xn apar într-o ordine aleatoare.
	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire ~~afise~~.~~out~~ va conține o singură linie cu două valori val Nk, ce reprezintă lungimea minimă totală folosită și numărul de panouri folosite astfel încât toate zonele deteriorate să fie acoperite.		Fișierul de ieșire afiseout.txt va conține o singură linie cu două valori val Nk, ce reprezintă lungimea minimă totală folosită și numărul de panouri folosite astfel încât toate zonele deteriorate să fie acoperite.
	== Restricții și precizări ==		== Restricții și precizări ==
	~ 0 < L ≤ 1000		*0 < L ≤ 1000
	~~<br>~~		*0 < n ≤ L
	~ 0 < n ≤ L		*0 < k ≤ L / 2
	~~<br>~~		== Exemplul 1 ==
	~ 0 < k ≤ L / 2		; afisein.txt
	== ~~Exemplu~~ 1 ==
	; ~~Intrare~~
	~~: afise~~.in
	:25 8 3		:25 8 3
	:3 11 6 4 19 15 20 12		:3 11 6 4 19 15 20 12
	; ~~Ieșire~~		; afiseout.txt
	~~: afise~~.~~out~~
	:11 3		:11 3
	<br>		<br>
	== ~~Exemplu~~ 2 ==		== Exemplul 2 ==
	; ~~Intrare~~		; afisein.txt
	~~: afise~~.in
	:10 4 6		:10 4 6
	:7 3 8 1		:7 3 8 1
	; ~~Ieșire~~		; afiseout.txt
	~~: afise~~.~~out~~
	:4 3		:4 3
	<br>		<br>
Line 49:		Line 44:

	return lungime_minima, panouri_folosite		return lungime_minima, panouri_folosite

			def verificare_restrictii(L, n, k):
			if 0 < L <= 1000
			0 < n <= L
			0 < k <= L / 2 :
			return True
			else:
			return False


	def main():		def main():
	with open("~~afise~~.in", "r") as file_in:		with open("afisein.txt", "r") as file_in:
	L, n, k = map(int, file_in.readline().split())		L, n, k = map(int, file_in.readline().split())
	unitati_deteriorate = list(map(int, file_in.readline().split()))		unitati_deteriorate = list(map(int, file_in.readline().split()))
Line 57:		Line 61:
	lungime_minima, panouri_folosite = acoperire_zid(L, n, k, unitati_deteriorate)		lungime_minima, panouri_folosite = acoperire_zid(L, n, k, unitati_deteriorate)

	with open("~~afise~~.~~out~~", "w") as file_out:		with open("afiseout.txt", "w") as file_out:
	file_out.write(f"{lungime_minima} {panouri_folosite}\n")		file_out.write(f"{lungime_minima} {panouri_folosite}\n")

Oros Ioana Diana: Pagină nouă: == Cerința == Fiind date lungimea zidului, câte unităţi sunt deteriorate, care este numărul maxim de panouri ce pot fi folosite şi care sunt unităţile de zid deteriorate, se cere să se determine lungimea minimă totală a panourilor care sunt folosite pentru a acoperi zona şi câte panouri se folosesc. Lungimea minimă o definim ca numărul total de unităţi de zid acoperite astfel încât să fie mascate zonele problemă. Pentru acoperirea unităţilor de zid dete...

2023-12-12T18:45:03Z

Pagină nouă: == Cerința == Fiind date lungimea zidului, câte unităţi sunt deteriorate, care este numărul maxim de panouri ce pot fi folosite şi care sunt unităţile de zid deteriorate, se cere să se determine lungimea minimă totală a panourilor care sunt folosite pentru a acoperi zona şi câte panouri se folosesc. Lungimea minimă o definim ca numărul total de unităţi de zid acoperite astfel încât să fie mascate zonele problemă. Pentru acoperirea unităţilor de zid dete...

New page

== Cerința ==
Fiind date lungimea zidului, câte unităţi sunt deteriorate, care este numărul maxim de panouri ce pot fi folosite şi care sunt unităţile de zid deteriorate, se cere să se determine lungimea minimă totală a panourilor care sunt folosite pentru a acoperi zona şi câte panouri se folosesc. Lungimea minimă o definim ca numărul total de unităţi de zid acoperite astfel încât să fie mascate zonele problemă. Pentru acoperirea unităţilor de zid deteriorate, nu este neapărat necesar să se folosească toate panourile. Numărul de panouri folosite fiind limitat există posibilitatea să fie acoperite şi zone din zid care sunt curate.
== Date de intrare ==
Fișierul de intrare afise.in conţine pe prima linie trei valori separate prin câte un spaţiu L n k, cu semnificația: L lungimea totală a zidului, n numărul de unităţi ce urmează a fi acoperite şi k numărul maxim de panouri ce pot fi folosite. Pe a doua linie separate prin câte un spațiu sunt n valori x1, x2, … , xn, unde xi reprezintă unitatea din zid care este acoperită de un afiș vechi. Valorile x1, x2, … , xn apar într-o ordine aleatoare.
== Date de ieșire ==
Fișierul de ieșire afise.out va conține o singură linie cu două valori val Nk, ce reprezintă lungimea minimă totală folosită și numărul de panouri folosite astfel încât toate zonele deteriorate să fie acoperite.
== Restricții și precizări ==
~ 0 < L ≤ 1000
<br>
~ 0 < n ≤ L
<br>
~ 0 < k ≤ L / 2
== Exemplu 1 ==
; Intrare
: afise.in
:25 8 3
:3 11 6 4 19 15 20 12
; Ieșire
: afise.out
:11 3
<br>
== Exemplu 2 ==
; Intrare
: afise.in
:10 4 6
:7 3 8 1
; Ieșire
: afise.out
:4 3
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#2676 - Afise
def acoperire_zid(L, n, k, unitati_deteriorate):
unitati_deteriorate.sort()
lungime_minima = 0
panouri_folosite = 0

if k >= n:
lungime_minima = L
panouri_folosite = n
else:
for i in range(n - k + 1):
lungime_sectiune = unitati_deteriorate[i + k - 1] - unitati_deteriorate[i] + 1
if lungime_sectiune > lungime_minima:
lungime_minima = lungime_sectiune

panouri_folosite = min(n, k)

return lungime_minima, panouri_folosite

def main():
with open("afise.in", "r") as file_in:
L, n, k = map(int, file_in.readline().split())
unitati_deteriorate = list(map(int, file_in.readline().split()))

lungime_minima, panouri_folosite = acoperire_zid(L, n, k, unitati_deteriorate)

with open("afise.out", "w") as file_out:
file_out.write(f"{lungime_minima} {panouri_folosite}\n")

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