Ghisa Catalin at 14:34, 26 December 2023

2023-12-26T14:34:04Z

← Older revision		Revision as of 14:34, 26 December 2023
Line 1:		Line 1:
	== Cerinţa ==		== Cerinţa ==
	~~Hercule trebuie sa strabată un labirint cu capcane reprezentat de~~ o ~~matrice cu '''n''' linii și '''m''' coloane. Pentru fiecare celula a labirintului, se cunoaște timpul exprimat în minute după~~ care ~~celula respectivă devine capcană. După ce o celula devine capcana, Hercule piere dacă intră în acea celulă. Initial Hercule se află în celula de coordonate '''(1, 1)'''~~ și ~~trebuie să ajungă în celula de cordonate '''(n,m)'''~~.		Se dă o propoziție care conține numai litere mici ale alfabetului englez și spații. Să se afișeze cuvintele din propoziție care conțin numai vocale.

	Sa se afișeze ~~numarul total de drumuri pe~~ care ~~le poate urma Hercule prin labirint, astfel încât Hercule să nu piară~~.
	== Date de intrare ==		== Date de intrare ==
	~~Fișierul~~ de ~~intrare '''herculein.txt''' conține pe prima linie numerele '''n m''', iar pe următoarele '''n''' linii câte m valori naturale~~.		Programul citește de la tastatură șirul dat.
	== Date de ieșire ==		== Date de ieșire ==
	~~Fișierul de ieșire '''herculeout.txt'''~~ va ~~conține~~ pe ~~prima~~ linie ~~numărul total de drumuri prin care Hercule poate ajunge în celula destinație~~.		Programul va afișa pe ecran cuvintele cerute, în ordinea din propoziție, câte un cuvânt pe linie.
	== Restricţii şi precizări ==		== Restricţii şi precizări ==
	* ~~1 &les; m,n &les; 10~~		* propoziția va conține cel mult '''255''' de caractere
	* Hercule nu poate intra de mai multe ori in aceeasi celula		== Exemplu 1 ==
	* Hercule are nevoie de ~~un minut,ca sa treacă dintr-o celula într-una vecină~~		; Intrare
	* Hercule se deplasează pe direcțiile N-S și E-V.		ei pazesc o oaie
	== Exemplu ==		; Iesire
	; ~~herculein.txt~~
	~~4 5~~
	~~4 1 1 8 1~~
	~~6 3 4 5 1~~
	~~3 2 8 8 8~~
	~~1 3 4 2 9~~
	; ~~herculeout.txt~~
	Datele de intrare corespund restrictiilor impuse		Datele de intrare corespund restrictiilor impuse
	2		ei
			o
			oaie
	<br>		<br>
	== Exemplu 2 ==		== Exemplu 2 ==
	; ~~herculein.txt~~		; Intrare
	~~4 11~~		Ei pazesc o oaie
	~~4 1 1 8 1~~		; Iesire
	~~6 3 4 5 1~~
	~~3 2 8 8 8~~
	~~1 3 4 2 9~~
	; ~~herculeout.txt~~
	Datele de intrare nu corespund restrictiilor impuse		Datele de intrare nu corespund restrictiilor impuse
	<br>		<br>
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	def ~~numar_drumuri~~(~~matrice, n, m~~):		def main():
	dp = ~~[[0 for _ in range~~(m)~~] for _ in range~~(n)]		# Citirea propoziției de la tastatură
	~~dp[0][0] = 1~~		propozitie = input().strip()

	for i in ~~range(n~~):		# Verifică dacă propoziția respectă restricțiile
	~~for j in range~~(m):		if len(propozitie) > 255 or any(not caracter.islower() and not caracter.isspace() for caracter in propozitie):
	~~if i > 0 and matrice[i][j] > i + j:~~		print("Datele de intrare nu corespund restrictiilor impuse")
	~~dp[i][j] += dp[i-1][j]~~		return
	~~if j > 0 and matrice[i][j] > i + j:~~		else:
	~~dp[i][j] += dp[i][j-1]~~		print("Datele de intrare corespund restrictiilor impuse")

	return ~~dp[n-1][m-1]~~

	~~def main():~~
	~~with open('herculein.txt', 'r') as fin~~:
	~~n, m = map(int, fin.readline().split())~~
	~~matrice = [list(map(int, linie.split~~()~~)) for linie in fin]~~

	~~with open~~('~~herculeout~~.~~txt', 'w'~~) ~~as fout~~:		# Afișarea cuvintelor din propoziție care conțin numai vocale
	if ~~not~~ (~~1 <= n <= 10 and 1 <= m <= 10~~):		vocale = set('aeiou')
	~~fout~~.~~write~~(~~"Datele de intrare nu corespund restrictiilor impuse\n"~~)		cuvinte = propozitie.split()
	~~return~~		for cuvant in cuvinte:
	~~fout.write~~(~~"Datele de intrare corespund restrictiilor impuse\n"~~)		if set(cuvant).issubset(vocale):
			print(cuvant)

	~~fout.write(str(numar_drumuri(matrice, n, m)) + '\n')~~

	if __name__ == "__main__":		if __name__ == "__main__":
Line 65:		Line 47:

	</syntaxhighlight>		</syntaxhighlight>
	~~== Explicatie ==~~
	~~; Cele două trasee posibile ale lui Hercule sunt:~~
	~~1 0 0 0 0~~
	~~2 3 4 5 0~~
	~~0 0 0 6 7~~
	~~0 0 0 0 8~~
	~~; si~~
	~~1 0 0 0 0~~
	~~2 3 4 0 0~~
	~~0 0 5 6 7~~
	~~0 0 0 0 8~~

Ghisa Catalin: Pagină nouă: == Cerinţa == Hercule trebuie sa strabată un labirint cu capcane reprezentat de o matrice cu '''n''' linii și '''m''' coloane. Pentru fiecare celula a labirintului, se cunoaște timpul exprimat în minute după care celula respectivă devine capcană. După ce o celula devine capcana, Hercule piere dacă intră în acea celulă. Initial Hercule se află în celula de coordonate '''(1, 1)''' și trebuie să ajungă în celula de cordonate '''(n,m)'''. Sa se afișeze numaru...

2023-12-12T19:02:04Z

Pagină nouă: == Cerinţa == Hercule trebuie sa strabată un labirint cu capcane reprezentat de o matrice cu '''n''' linii și '''m''' coloane. Pentru fiecare celula a labirintului, se cunoaște timpul exprimat în minute după care celula respectivă devine capcană. După ce o celula devine capcana, Hercule piere dacă intră în acea celulă. Initial Hercule se află în celula de coordonate '''(1, 1)''' și trebuie să ajungă în celula de cordonate '''(n,m)'''. Sa se afișeze numaru...

New page

== Cerinţa ==
Hercule trebuie sa strabată un labirint cu capcane reprezentat de o matrice cu '''n''' linii și '''m''' coloane. Pentru fiecare celula a labirintului, se cunoaște timpul exprimat în minute după care celula respectivă devine capcană. După ce o celula devine capcana, Hercule piere dacă intră în acea celulă. Initial Hercule se află în celula de coordonate '''(1, 1)''' și trebuie să ajungă în celula de cordonate '''(n,m)'''.

Sa se afișeze numarul total de drumuri pe care le poate urma Hercule prin labirint, astfel încât Hercule să nu piară.
== Date de intrare ==
Fișierul de intrare '''herculein.txt''' conține pe prima linie numerele '''n m''', iar pe următoarele '''n''' linii câte m valori naturale.
== Date de ieșire ==
Fișierul de ieșire '''herculeout.txt''' va conține pe prima linie numărul total de drumuri prin care Hercule poate ajunge în celula destinație.
== Restricţii şi precizări ==
* 1 &les; m,n &les; 10
* Hercule nu poate intra de mai multe ori in aceeasi celula
* Hercule are nevoie de un minut,ca sa treacă dintr-o celula într-una vecină
* Hercule se deplasează pe direcțiile N-S și E-V.
== Exemplu ==
; herculein.txt
4 5
4 1 1 8 1
6 3 4 5 1
3 2 8 8 8
1 3 4 2 9
; herculeout.txt
Datele de intrare corespund restrictiilor impuse
2
<br>
== Exemplu 2 ==
; herculein.txt
4 11
4 1 1 8 1
6 3 4 5 1
3 2 8 8 8
1 3 4 2 9
; herculeout.txt
Datele de intrare nu corespund restrictiilor impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
def numar_drumuri(matrice, n, m):
dp = [[0 for _ in range(m)] for _ in range(n)]
dp[0][0] = 1

for i in range(n):
for j in range(m):
if i > 0 and matrice[i][j] > i + j:
dp[i][j] += dp[i-1][j]
if j > 0 and matrice[i][j] > i + j:
dp[i][j] += dp[i][j-1]

return dp[n-1][m-1]

def main():
with open('herculein.txt', 'r') as fin:
n, m = map(int, fin.readline().split())
matrice = [list(map(int, linie.split())) for linie in fin]

with open('herculeout.txt', 'w') as fout:
if not (1 <= n <= 10 and 1 <= m <= 10):
fout.write("Datele de intrare nu corespund restrictiilor impuse\n")
return
fout.write("Datele de intrare corespund restrictiilor impuse\n")

fout.write(str(numar_drumuri(matrice, n, m)) + '\n')

if __name__ == "__main__":
main()

</syntaxhighlight>
== Explicatie ==
; Cele două trasee posibile ale lui Hercule sunt:
1 0 0 0 0
2 3 4 5 0
0 0 0 6 7
0 0 0 0 8
; si
1 0 0 0 0
2 3 4 0 0
0 0 5 6 7
0 0 0 0 8

0973 - Cuvinte 1 - Revision history

Ghisa Catalin at 14:34, 26 December 2023