3084 - Cub Dinamic: Difference between revisions

From Bitnami MediaWiki
Mraa (talk | contribs)
Pagină nouă: ==Cerința== Se dă un tablou tridimensional, de dimensiune n x n x n , fiecare element reprezentând o camera. m dintre acestea sunt blocate și nu pot fi traversate. Dintr-o cameră având coordonatele (i,j,k) te poți deplasa in camerele de coordonate (i+1,j,k) , (i,j+1,k) și (i,j,k+1) . Știind că pornești din camera cu coordonate (1,1,1) , se cere să se afișeze numărul de moduri modulo 1234567 de a ajunge in camera de coordonate (n,n,n,) . ==Date de intrare...
 
Mraa (talk | contribs)
No edit summary
Line 45: Line 45:
  fără a trece prin camere blocate.
  fără a trece prin camere blocate.
==Rezolvare==
==Rezolvare==
<syntaxhighlight lang="python3">
MOD = 1234567
MOD = 1234567


def numar_moduri(n, m, camere_blocate):
def numar_moduri(n, m, camere_blocate):
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]


    # Inițializăm matricea cu 0-uri
  dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(n + 1):
  # Inițializăm matricea cu 0-uri
        for j in range(n + 1):
  for i in range(n + 1):
            for k in range(n + 1):
      for j in range(n + 1):
                dp[i][j][k] = 0
          for k in range(n + 1):
 
              dp[i][j][k] = 0
    # Marcam camerele blocate cu -1
  # Marcam camerele blocate cu -1
    for i, j, k in camere_blocate:
  for i, j, k in camere_blocate:
        dp[i][j][k] = -1
      dp[i][j][k] = -1
 
  # Dacă camera finală este blocată sau camera de plecare este blocată, returnăm 0
    # Dacă camera finală este blocată sau camera de plecare este blocată, returnăm 0
  if dp[1][1][1] == -1 or dp[n][n][n] == -1:
    if dp[1][1][1] == -1 or dp[n][n][n] == -1:
      return 0
        return 0
  dp[1][1][1] = 1
 
  for i in range(1, n + 1):
    dp[1][1][1] = 1
      for j in range(1, n + 1):
 
          for k in range(1, n + 1):
    for i in range(1, n + 1):
              # Dacă camera este blocată, continuăm
        for j in range(1, n + 1):
              if dp[i][j][k] == -1:
            for k in range(1, n + 1):
                  continue
                # Dacă camera este blocată, continuăm
              # Actualizăm modul în care putem ajunge în camerele adiacente
                if dp[i][j][k] == -1:
              if i + 1 <= n and dp[i + 1][j][k] != -1:
                    continue
                  dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % MOD
 
              if j + 1 <= n and dp[i][j + 1][k] != -1:
                # Actualizăm modul în care putem ajunge în camerele adiacente
                  dp[i][j + 1][k] = (dp[i][j + 1][k] + dp[i][j][k]) % MOD
                if i + 1 <= n and dp[i + 1][j][k] != -1:
              if k + 1 <= n and dp[i][j][k + 1] != -1:
                    dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % MOD
                  dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i][j][k]) % MOD
                if j + 1 <= n and dp[i][j + 1][k] != -1:
  return dp[n][n][n]
                    dp[i][j + 1][k] = (dp[i][j + 1][k] + dp[i][j][k]) % MOD
                if k + 1 <= n and dp[i][j][k + 1] != -1:
                    dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i][j][k]) % MOD
 
    return dp[n][n][n]


if __name__ == "__main__":
if __name__ == "__main__":
    with open("cub_dinamic.in", "r") as f:
        n, m = map(int, f.readline().split())
        camere_blocate = [tuple(map(int, f.readline().split())) for _ in range(m)]
    rezultat = numar_moduri(n, m, camere_blocate)


    with open("cub_dinamic.out", "w") as g:
  with open("cub_dinamic.in", "r") as f:
        g.write(str(rezultat) + "\n")
      n, m = map(int, f.readline().split())
python cub_dinamic.py
      camere_blocate = [tuple(map(int, f.readline().split())) for _ in range(m)]
  rezultat = numar_moduri(n, m, camere_blocate)
  with open("cub_dinamic.out", "w") as g:
      g.write(str(rezultat) + "\n")
</syntaxhighlight>

Revision as of 17:35, 11 January 2024

Cerința

Se dă un tablou tridimensional, de dimensiune n

x n
x n

, fiecare element reprezentând o camera. m

dintre acestea sunt blocate și nu pot fi traversate. Dintr-o cameră având coordonatele (i,j,k)
te poți deplasa in camerele de coordonate (i+1,j,k)

, (i,j+1,k)

și (i,j,k+1)

.

Știind că pornești din camera cu coordonate (1,1,1) , se cere să se afișeze numărul de moduri modulo 1234567

de a ajunge in camera de coordonate (n,n,n,)

.

Date de intrare

Fișierul de intrare cub_dinamic.in conține pe prima linie numerele n și m, iar pe următoarele m linii câte 3 numere reprezentând coordonatele camerelor blocate.

Date de ieșire

Fișierul de ieșire cub_dinamic.out va conține pe prima linie numărul S, reprezentând numărul de moduri modulo 1234567

de a ajunge din camera (1,1,1)
în camera (n,n,n)

.

Restricții și precizări

1 ≤ n ≤ 200 1 ≤ coordonatele camerelor ≤ n 0 ≤ m ≤ n*n*n Dacă nu se poate ajunge in camera (n,n,n)

sau una dintre camerele (1,1,1)
sau (n,n,n)
este blocată, atunci se va afișa 0.

==Exemplu==: cub_dinamic.in

3 1 2 2 2 cub_dinamic.out

54

Explicație

Există 54 de moduri de a ajunge din camera (1,1,1)

în camera (n,n,n)
fără a trece prin camere blocate.

Rezolvare

<syntaxhighlight lang="python3"> MOD = 1234567

def numar_moduri(n, m, camere_blocate):

  dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
  # Inițializăm matricea cu 0-uri
  for i in range(n + 1):
      for j in range(n + 1):
          for k in range(n + 1):
              dp[i][j][k] = 0
  # Marcam camerele blocate cu -1
  for i, j, k in camere_blocate:
      dp[i][j][k] = -1
  # Dacă camera finală este blocată sau camera de plecare este blocată, returnăm 0
  if dp[1][1][1] == -1 or dp[n][n][n] == -1:
      return 0
  dp[1][1][1] = 1
  for i in range(1, n + 1):
      for j in range(1, n + 1):
          for k in range(1, n + 1):
              # Dacă camera este blocată, continuăm
              if dp[i][j][k] == -1:
                  continue
              # Actualizăm modul în care putem ajunge în camerele adiacente
              if i + 1 <= n and dp[i + 1][j][k] != -1:
                  dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % MOD
              if j + 1 <= n and dp[i][j + 1][k] != -1:
                  dp[i][j + 1][k] = (dp[i][j + 1][k] + dp[i][j][k]) % MOD
              if k + 1 <= n and dp[i][j][k + 1] != -1:
                  dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i][j][k]) % MOD
  return dp[n][n][n]

if __name__ == "__main__":

  with open("cub_dinamic.in", "r") as f:
      n, m = map(int, f.readline().split())
      camere_blocate = [tuple(map(int, f.readline().split())) for _ in range(m)]
  rezultat = numar_moduri(n, m, camere_blocate)
  with open("cub_dinamic.out", "w") as g:
      g.write(str(rezultat) + "\n")

</syntaxhighlight>