Danciu: Pagină nouă: Algorel a primit un set de `n` bile numerotate de la `1` la `n` pe care trebuie să le pună în trei cutii identice astfel încât în nicio cutie să nu fie două bile numerotate cu numere consecutive. = Cerința = În câte moduri poate face Algorel acest lucru? = Date de intrare = Fișierul de intrare `bile1.in` conține pe prima linie numărul `n`. = Date de ieșire = Fișierul de ieșire `bile1.out` v...

2024-06-04T09:07:13Z

Pagină nouă: Algorel a primit un set de <code>n</code> bile numerotate de la <code>1</code> la <code>n</code> pe care trebuie să le pună în trei cutii identice astfel încât în nicio cutie să nu fie două bile numerotate cu numere consecutive. = Cerința = În câte moduri poate face Algorel acest lucru? = Date de intrare = Fișierul de intrare <code>bile1.in</code> conține pe prima linie numărul <code>n</code>. = Date de ieșire = Fișierul de ieșire <code>bile1.out</code> v...

New page

Algorel a primit un set de <code>n</code> bile numerotate de la <code>1</code> la <code>n</code> pe care trebuie să le pună în trei cutii identice astfel încât în nicio cutie să nu fie două bile numerotate cu numere consecutive.

= Cerința =
În câte moduri poate face Algorel acest lucru?

= Date de intrare =
Fișierul de intrare <code>bile1.in</code> conține pe prima linie numărul <code>n</code>.

= Date de ieșire =
Fișierul de ieșire <code>bile1.out</code> va conține pe prima linie numărul de moduri de distribuire a bilelor.

= Restricții și precizări =

* <code>n ≤ 300</code>

= Exemplu: =
<code>bile1.in</code>
4
<code>bile1.out</code>
24

== Rezolvare ==
<syntaxhighlight lang="python3">
MOD = 1000000007

def count_ball_distributions(n):
dp = [[0 for _ in range(4)] for _ in range(n + 1)]

for i in range(1, n + 1):
dp[i][1] = 3

for i in range(2, n + 1):
for j in range(1, 4):
dp[i][j] = 0

if j < 3:
dp[i][j] += dp[i - 1][j - 1] * 3
dp[i][j] += dp[i - 2][1] * 3

if j <= dp[i - 1][0]:
dp[i][j] += dp[i - 1][j - 1]

return dp[n][1] % MOD

def main():
with open("bile1.in", "r") as input_file:
n = int(input_file.readline())

ball_distributions_count = count_ball_distributions(n)

with open("bile1.out", "w") as output_file:
output_file.write(str(ball_distributions_count))

if __name__ == "__main__":
main()

</syntaxhighlight>

1489 - Bile1 - Revision history