Mraa: /* Rezolvare */

2024-01-11T18:32:20Z

Rezolvare

← Older revision		Revision as of 18:32, 11 January 2024
Line 34:		Line 34:
	Cum 66049 modulo 999983 = 66049, se obţine rezultatul 66049.		Cum 66049 modulo 999983 = 66049, se obţine rezultatul 66049.
	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python3">		<syntaxhighlight lang="python3" line="1">
	MOD = 999983		MOD = 999983

Mraa at 17:38, 11 January 2024

2024-01-11T17:38:27Z

← Older revision		Revision as of 17:38, 11 January 2024
Line 34:		Line 34:
	Cum 66049 modulo 999983 = 66049, se obţine rezultatul 66049.		Cum 66049 modulo 999983 = 66049, se obţine rezultatul 66049.
	==Rezolvare==		==Rezolvare==
			<syntaxhighlight lang="python3">
	MOD = 999983		MOD = 999983

	def numar_coregrafii(n, k, lungimi_figuri):		def numar_coregrafii(n, k, lungimi_figuri):
	~~# Inițializăm lista dp cu 0-uri~~
	~~dp = [0] * (k + 1)~~

	# Există o singură modalitate de a avea coregrafia de lungime 0		# Inițializăm lista dp cu 0-uri
	dp[0] = 1		dp = [0] * (k + 1)
			# Există o singură modalitate de a avea coregrafia de lungime 0
	# Calculăm numărul de coregrafii		dp[0] = 1
	for i in range(1, n + 1):		# Calculăm numărul de coregrafii
	for j in range(lungimi_figuri[i - 1], k + 1):		for i in range(1, n + 1):
	dp[j] = (dp[j] + dp[j - lungimi_figuri[i - 1]]) % MOD		for j in range(lungimi_figuri[i - 1], k + 1):
			dp[j] = (dp[j] + dp[j - lungimi_figuri[i - 1]]) % MOD
	return dp[k]		return dp[k]

	if __name__ == "__main__":		if __name__ == "__main__":
	~~with open("tango.in", "r") as f:~~
	~~n, k = map(int, f.readline().split())~~
	~~lungimi_figuri = list(map(int, f.readline().split()))~~

	~~rezultat = numar_coregrafii(n, k, lungimi_figuri)~~

	with open("tango.out", "w") as g:		with open("tango.in", "r") as f:
	g.write(str(rezultat) + "\n")		n, k = map(int, f.readline().split())
	~~python tango.py~~		lungimi_figuri = list(map(int, f.readline().split()))
			rezultat = numar_coregrafii(n, k, lungimi_figuri)
			with open("tango.out", "w") as g:
			g.write(str(rezultat) + "\n")
			</syntaxhighlight>

Mraa: Pagină nouă: Un tango este format din fraze muzicale, fiecare dintre acestea având 8 timpi muzicali. Timpii muzicali au aceeaşi durată. La fel de importantă ca melodia unui tango este şi dansul asociat ei. Mişcările efectuate în timpul dansului se numesc figuri. Succesiunea de figuri efectuate în timpul dansului formează o coregrafie. Două coregrafii se consideră diferite dacă succesiunea figurilor care le alcătuiesc este diferită. O coregrafie frumoasă asociată unui tang...

2023-12-21T21:19:23Z

Pagină nouă: Un tango este format din fraze muzicale, fiecare dintre acestea având 8 timpi muzicali. Timpii muzicali au aceeaşi durată. La fel de importantă ca melodia unui tango este şi dansul asociat ei. Mişcările efectuate în timpul dansului se numesc figuri. Succesiunea de figuri efectuate în timpul dansului formează o coregrafie. Două coregrafii se consideră diferite dacă succesiunea figurilor care le alcătuiesc este diferită. O coregrafie frumoasă asociată unui tang...

New page

Un tango este format din fraze muzicale, fiecare dintre acestea având 8 timpi muzicali. Timpii muzicali au aceeaşi durată. La fel de importantă ca melodia unui tango este şi dansul asociat ei. Mişcările efectuate în timpul dansului se numesc figuri. Succesiunea de figuri efectuate în timpul dansului formează o coregrafie. Două coregrafii se consideră diferite dacă succesiunea figurilor care le alcătuiesc este diferită. O coregrafie frumoasă asociată unui tango are particularitatea următoare: atunci când se termină o frază muzicală trebuie să se termine şi o figură.

D şi S se pregătesc pentru primul lor concurs de dans şi ei lucreaza momentan la coregrafia de tango. Chiar dacă va fi primul lor concurs, ei deja ştiu n figuri de dans şi au calculat pentru fiecare dintre aceste figuri câţi timpi muzicali durează. Fiindcă le place foarte mult să danseze împreună, ei vor să pregătească o coregrafie frumoasă pentru o piesă care durează exact k timpi muzicali.

==Cerința==
Determinaţi numărul coregrafiilor frumoase modulo 999983 pentru o piesă, care: durează exact k timpi muzicali, respectă condiţiile de mai sus şi sunt formate doar din cele n figuri cunoscute de D şi S (mai este prea puţin timp până la concurs, ca ei să inveţe şi figuri noi).

==Date de intrare==
Pe prima linie a fişierului de intrare tango.in se află numerele naturale nenule n şi k, separate printr-un singur spaţiu. Pe a doua linie se află exact n numere separate prin câte un spaţiu, reprezintând lungimile figurilor.

==Date de ieșire==
În fişierul de ieşire tango.out se va afişa numărul de coregrafii posibile modulo 999983.

==Restricții și precizări==
n ≤ 100 000.
k ≤ 2 000 000 000.
k va fi întotdeauna divizibil cu 8.
1 ≤ lungimea unei figuri ≤ 8.
Pentru 30% din teste va exista o singură figură de o anumită lungime.
Pentru 50% din teste n ≤ 30.
Pentru 70% din teste lungimile figurilor vor fi numai valori din mulţimea {2, 4, 6, 8}.
Prin a modulo b se înţelege restul împărţirii lui a la b.
==Exemplu==:
tango.in

3 16
1 1 8
tango.out

66049
==Explicație==
Sunt 16 timpi muzicali deci o coregrafie frumoasă se va dansa pe 16 / 8 = 2 fraze muzicale.
Dacă notăm figurile cu litere, avem figura A de lungime 1, figura B de lungime 1 şi figura C de lungime 8. Prima frază muzicală poate fi alcătuită din orice secvenţă alcătuită din opt bucăţi de A sau B, deci în total 2^8 = 256 posibilităţi. Încă o posibilitate de alcătuire a primei fraze este printr-un singur C. Rezultă un total de 257 posibilităţi. Pentru a doua frază avem tot atâtea posibilităţi, deci în total există 257 * 257 = 66049 coregrafii frumoase posibile.
Cum 66049 modulo 999983 = 66049, se obţine rezultatul 66049.
==Rezolvare==
MOD = 999983

def numar_coregrafii(n, k, lungimi_figuri):
# Inițializăm lista dp cu 0-uri
dp = [0] * (k + 1)

# Există o singură modalitate de a avea coregrafia de lungime 0
dp[0] = 1

# Calculăm numărul de coregrafii
for i in range(1, n + 1):
for j in range(lungimi_figuri[i - 1], k + 1):
dp[j] = (dp[j] + dp[j - lungimi_figuri[i - 1]]) % MOD

return dp[k]

if __name__ == "__main__":
with open("tango.in", "r") as f:
n, k = map(int, f.readline().split())
lungimi_figuri = list(map(int, f.readline().split()))

rezultat = numar_coregrafii(n, k, lungimi_figuri)

with open("tango.out", "w") as g:
g.write(str(rezultat) + "\n")
python tango.py

3571 - Tango - Revision history

Mraa: /* Rezolvare */

Mraa at 17:38, 11 January 2024