0707 - Sum K: Difference between revisions

From Bitnami MediaWiki
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.


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 ==
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 ==
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 ==
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.
== Restricții și precizări ==
*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 pentru 30% din teste, K≤N≤100
== Exemplul 1 ==
; sumkin.txt
: 2 2
; sumkout.txt
: 5
<br>
== Explicatie ==
Sunt N=2 stagii, cu câte N=2 niveluri. Suma este K=2 pe fiecare stagiu.
<br>
Nivelurile sunt reprezentate de către coloanele matricelor.
<br>
Există 5 posibilități ca jocul să se termine cu succes.
== Exemplul 2 ==
; sumkin.txt
: 3 2
; sumkout.txt
: 28
<br>
== Explicatie ==
Sunt N=3 stagii, cu câte N=3 niveluri. Suma este K=2 pe fiecare stagiu.
<br>
Sunt reprezentate doar câteva dintre cele 28 de posibilități.
== Rezolvare ==  
== Rezolvare ==  
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line="1">
#0707 - Sum K
def calcul(z1, z2, n, a):
def numar_posibilitati(N, K):
    x = [0] * 502
    MOD = 578537
    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]


     if not (1 <= K <= N <= 500):
def main():
         print("Fals")
     try:
        exit()
        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


     # Inițializare matrice dp cu zero-uri
     if not (1 <= k <= n <= 500):
    dp = [[0] * (K + 1) for _ in range(N + 1)]
        with open("sumkOUT.txt", "wt") as fout:
            fout.write("Datele nu corespund restrictiilor impuse.")
        return


     # Caz de bază: dp[i][0] = 1 pentru orice i
     r = [0] * 502
     for i in range(N + 1):
    z = [0] * 502
        dp[i][0] = 1
     r[1] = 1
    a = 578537


    # Calculul dinamic pentru numărul de posibilități
     for j in range(1, k + 1):
     for i in range(1, N + 1):
         for i in range(2, n + 1):
         for j in range(1, K + 1):
             r[i] = (r[i - 1] + r[i]) % a
             dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD


     return dp[N][K]
     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


# Citirea datelor de intrare din fișierul "sumkin.txt"
    s = 0
try:
     for i in range(1, n + 1):
     with open("sumkin.txt", "r") as file:
         s = (s + z[i]) % a
         N, K = map(int, file.readline().split())
except Exception as e:
    print("Fals")
    exit()


# Calculul rezultatului și afișarea acestuia în fișierul "sumkout.txt"
    with open("sumkOUT.txt", "wt") as fout:
result = numar_posibilitati(N, K)
        fout.write(f"{int(s)}")


with open("sumkout.txt", "w") as file:
if __name__ == "__main__":
     file.write(str(result) + "\n")
     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 pentru 30% 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>