0707 - Sum K: Difference between revisions
Pagină nouă: sumk este un joc de perspicacitate, cu N stagii numerotate de la 1 la N. Un joc se termină cu succes dacă jucătorul a parcurs în ordine, de la 1 la N, toate cele N stagii ale jocului şi în fiecare stagiu a obţinut exact K puncte. Fiecare stagiu are N niveluri, numerotate de asemenea de la 1 la N. Jucătorul are posibilitatea să câştige 0, 1, …, K puncte pe oricare nivel al stagiului curent. Dacă jucătorul se găseşte în stagiul i pe nivelul j și numărul tot... |
No edit summary |
||
Line 1: | Line 1: | ||
sumk este un joc de perspicacitate, cu N stagii numerotate de la 1 la N. Un joc se termină cu succes dacă jucătorul a parcurs în ordine, de la 1 la N, toate cele N stagii ale jocului şi în fiecare stagiu a obţinut exact K puncte. Fiecare stagiu are N niveluri, numerotate de asemenea de la 1 la N. Jucătorul are posibilitatea să câştige 0, 1, …, K puncte pe oricare nivel al stagiului curent. | <code>sumk</code> este un joc de perspicacitate, cu <code>N</code> stagii numerotate de la <code>1</code> la <code>N</code>. Un joc se termină cu succes dacă jucătorul a parcurs în ordine, de la <code>1</code> la <code>N</code>, toate cele <code>N</code> stagii ale jocului şi în fiecare stagiu a obţinut exact <code>K</code> puncte. Fiecare stagiu are <code>N</code> niveluri, numerotate de asemenea de la <code>1</code> la <code>N</code>. Jucătorul are posibilitatea să câştige <code>0</code>, <code>1</code>, …, <code>K</code> puncte pe oricare nivel al stagiului curent. | ||
Dacă jucătorul se găseşte în stagiul <code>i</code> pe nivelul <code>j</code> și numărul total de puncte obţinute până în acel moment în acest stagiu este mai mic decât <code>K</code>, el va trece în mod obligatoriu pe nivelul <code>j+1</code> al stagiului <code>i</code>. Dacă jucătorul primește cel puţin un punct pe nivelul <code>j</code> și astfel punctajul său în stagiul <code>i</code> devine exact <code>K</code>, atunci jucătorul trece în mod automat pe nivelul <code>j</code> al stagiului <code>i+1</code> sau termină jocul cu succes dacă <code>i=N</code>. | |||
= Cerința = | |||
Cunoscând numărul <code>N</code> de stagii ale jocului şi numărul <code>K</code> de puncte care trebuie să fie obţinute în fiecare stagiu, să se determine numărul de posibilităţi modulo <code>578537</code> pentru ca jocul să se termine cu succes. | |||
= Date de intrare = | |||
Fișierul de intrare <code>sumkIN.txt</code> conține pe prima linie două numere naturale <code>N K</code> cu semnificația descrisă anterior. | |||
= Date de ieșire = | |||
Fișierul de ieșire <code>sumkOUT.txt</code> va conține pe prima linie un singur număr natural <code>P</code> reprezentând numărul total de posibilităţi modulo <code>578537</code> pentru ca jocul să se termine cu succes. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse". | |||
= Restricții și precizări = | |||
* <code>1 ≤ K ≤ N ≤ 500</code> | |||
* Fie <code>x</code> punctajul final într-un stagiu oarecare. Atunci dacă <code>x ≠ K</code>, jocul se termină cu eșec. | |||
* Pentru <code>20%</code> din teste, <code>K ≤ N ≤ 10</code>, iar pentru <code>30%</code> din teste, <code>K≤N≤100</code> | |||
= Exemplu 1: = | |||
<code>sumkIN.txt</code> | |||
2 2 | |||
<code>sumkOUT.txt</code> | |||
5 | |||
= Exemplu 2: = | |||
<code>sumkIN.txt</code> | |||
2 3 | |||
<code>sumkOUT.txt</code> | |||
Datele nu corespund restrictiilor impuse. | |||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python" line> | <syntaxhighlight lang="python" line="1"> | ||
def calcul(z1, z2, n, a): | |||
x = [0] * 502 | |||
for j in range(1, n + 1): | |||
s = 0 | |||
for i in range(1, j + 1): | |||
t = z1[i] | |||
t = (t * z2[j - i + 1]) % a | |||
s = (s + t) % a | |||
x[j] = s | |||
for j in range(1, n + 1): | |||
z1[j] = x[j] | |||
def main(): | |||
try: | |||
with open("sumkIN.txt", "rt") as fin: | |||
n, k = map(int, fin.readline().split()) | |||
except Exception as e: | |||
with open("sumkOUT.txt", "wt") as fout: | |||
fout.write("Eroare la citirea datelor de intrare.") | |||
return | |||
if not (1 <= k <= n <= 500): | |||
with open("sumkOUT.txt", "wt") as fout: | |||
fout.write("Datele nu corespund restrictiilor impuse.") | |||
return | |||
r = [0] * 502 | |||
z = [0] * 502 | |||
r[1] = 1 | |||
a = 578537 | |||
for j in range(1, k + 1): | |||
for | for i in range(2, n + 1): | ||
for | r[i] = (r[i - 1] + r[i]) % a | ||
v = n | |||
z[1] = 1 | |||
while v != 0: | |||
if v % 2 == 1: | |||
calcul(z, r, n, a) | |||
calcul(r, r, n, a) | |||
v = v // 2 | |||
s = 0 | |||
for i in range(1, n + 1): | |||
s = (s + z[i]) % a | |||
with open("sumkOUT.txt", "wt") as fout: | |||
fout.write(f"{int(s)}") | |||
if __name__ == "__main__": | |||
main() | |||
</syntaxhighlight> | </syntaxhighlight> |
Latest revision as of 07:08, 18 May 2024
sumk
este un joc de perspicacitate, cu N
stagii numerotate de la 1
la N
. Un joc se termină cu succes dacă jucătorul a parcurs în ordine, de la 1
la N
, toate cele N
stagii ale jocului şi în fiecare stagiu a obţinut exact K
puncte. Fiecare stagiu are N
niveluri, numerotate de asemenea de la 1
la N
. Jucătorul are posibilitatea să câştige 0
, 1
, …, K
puncte pe oricare nivel al stagiului curent.
Dacă jucătorul se găseşte în stagiul i
pe nivelul j
și numărul total de puncte obţinute până în acel moment în acest stagiu este mai mic decât K
, el va trece în mod obligatoriu pe nivelul j+1
al stagiului i
. Dacă jucătorul primește cel puţin un punct pe nivelul j
și astfel punctajul său în stagiul i
devine exact K
, atunci jucătorul trece în mod automat pe nivelul j
al stagiului i+1
sau termină jocul cu succes dacă i=N
.
Cerința[edit | edit source]
Cunoscând numărul N
de stagii ale jocului şi numărul K
de puncte care trebuie să fie obţinute în fiecare stagiu, să se determine numărul de posibilităţi modulo 578537
pentru ca jocul să se termine cu succes.
Date de intrare[edit | edit source]
Fișierul de intrare sumkIN.txt
conține pe prima linie două numere naturale N K
cu semnificația descrisă anterior.
Date de ieșire[edit | edit source]
Fișierul de ieșire sumkOUT.txt
va conține pe prima linie un singur număr natural P
reprezentând numărul total de posibilităţi modulo 578537
pentru ca jocul să se termine cu succes. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".
Restricții și precizări[edit | edit source]
1 ≤ K ≤ N ≤ 500
- Fie
x
punctajul final într-un stagiu oarecare. Atunci dacăx ≠ K
, jocul se termină cu eșec. - Pentru
20%
din teste,K ≤ N ≤ 10
, iar pentru30%
din teste,K≤N≤100
Exemplu 1:[edit | edit source]
sumkIN.txt
2 2
sumkOUT.txt
5
Exemplu 2:[edit | edit source]
sumkIN.txt
2 3
sumkOUT.txt
Datele nu corespund restrictiilor impuse.
Rezolvare[edit | edit source]
<syntaxhighlight lang="python" line="1"> def calcul(z1, z2, n, a):
x = [0] * 502 for j in range(1, n + 1): s = 0 for i in range(1, j + 1): t = z1[i] t = (t * z2[j - i + 1]) % a s = (s + t) % a x[j] = s for j in range(1, n + 1): z1[j] = x[j]
def main():
try: with open("sumkIN.txt", "rt") as fin: n, k = map(int, fin.readline().split()) except Exception as e: with open("sumkOUT.txt", "wt") as fout: fout.write("Eroare la citirea datelor de intrare.") return
if not (1 <= k <= n <= 500): with open("sumkOUT.txt", "wt") as fout: fout.write("Datele nu corespund restrictiilor impuse.") return
r = [0] * 502 z = [0] * 502 r[1] = 1 a = 578537
for j in range(1, k + 1): for i in range(2, n + 1): r[i] = (r[i - 1] + r[i]) % a
v = n z[1] = 1 while v != 0: if v % 2 == 1: calcul(z, r, n, a) calcul(r, r, n, a) v = v // 2
s = 0 for i in range(1, n + 1): s = (s + z[i]) % a
with open("sumkOUT.txt", "wt") as fout: fout.write(f"{int(s)}")
if __name__ == "__main__":
main()
</syntaxhighlight>