4029 - Depozit: Diferență între versiuni
(Pagină nouă: == Cerința == Într-un depozit, managerul dorește să organizeze mărfurile în diverse combinații pe rafturi. Fiecare raft poate conține 1, 2 sau 3 unități de marfă. Să se determine în câte moduri diferite poate managerul să aranjeze mărfurile pe rafturi pentru a avea un total de n unități de marfă. == Date de intrare == Programul citește de la tastatură un număr întreg n reprezentând numărul total de unități de marfă pe care managerul dorește să le...) |
|||
(Nu s-a afișat o versiune intermediară efectuată de același utilizator) | |||
Linia 1: | Linia 1: | ||
== Cerința == | == Cerința == | ||
Într-un depozit, | Într-un depozit au fost așezate cutii identice, una după alta, eventual suprapuse, astfel încât numărul maxim de cutii suprapuse într-o stivă este N, iar între două stive cu același număr de cutii să existe cel puțin una cu mai multe cutii decât oricare dintre cele două. Considerăm că o stivă poate fi formată dintr-o singură cutie. | ||
Proprietarul depozitului vă cere să aflați numărul maxim de stive care pot construi respectând regulile date și numărul de cutii care pot fi aranjate astfel. Pentru că numerele pot fi foarte mari rezultatele se vor afișa modulo 1.000.000.007. | |||
== Date de intrare == | == Date de intrare == | ||
Programul citește de la tastatură | Programul citește de la tastatură N. | ||
== Date de ieșire == | == Date de ieșire == | ||
Programul afișează pe ecran numărul maxim de stive care pot construi și numărul de cutii care pot fi aranjate modulo 1.000.000.007. | |||
== Restricții și precizări == | == Restricții și precizări == | ||
*1 | *1 ≤ N ≤ 1.000.000.000 | ||
== Exemplu 1 == | == Exemplu 1 == | ||
;Intrare | ;Intrare | ||
3 | |||
;Iesire | ;Iesire | ||
7 | 7 11 | ||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python" line | <syntaxhighlight lang="python" line="1"> | ||
MOD = 1_000_000_007 | |||
def | def factorial(n, mod): | ||
if n | result = 1 | ||
for i in range(2, n + 1): | |||
result = (result * i) % mod | |||
return result | |||
def mod_inverse(x, mod): | |||
return pow(x, mod - 2, mod) | |||
def comb(n, k, mod): | |||
if k > n: | |||
return 0 | return 0 | ||
num = factorial(n, mod) | |||
denom = (factorial(k, mod) * factorial(n - k, mod)) % mod | |||
return (num * mod_inverse(denom, mod)) % mod | |||
def calculate_stive_and_cuts(N): | |||
# Numărul maxim de stive este (N + 1) * N // 2 | |||
max_stive = (N + 1) * N // 2 | |||
moduri | # Numărul de moduri de a aranja cutiile | ||
num_cuts = 1 | |||
for i in range(1, N): | |||
num_cuts = (num_cuts * (2 * N - i) * mod_inverse(i, MOD)) % MOD | |||
return max_stive, num_cuts | |||
def main(): | def main(): | ||
N = int(input().strip()) | |||
assert 1 <= N <= 1000000000, "N nu este in parametru" | |||
max_stive, num_cuts = calculate_stive_and_cuts(N) | |||
print(max_stive+1, num_cuts+1) | |||
print( | |||
if __name__ == "__main__": | if __name__ == "__main__": | ||
main() | main() | ||
</syntaxhighlight> | </syntaxhighlight> |
Versiunea curentă din 3 iunie 2024 01:51
Cerința
Într-un depozit au fost așezate cutii identice, una după alta, eventual suprapuse, astfel încât numărul maxim de cutii suprapuse într-o stivă este N, iar între două stive cu același număr de cutii să existe cel puțin una cu mai multe cutii decât oricare dintre cele două. Considerăm că o stivă poate fi formată dintr-o singură cutie. Proprietarul depozitului vă cere să aflați numărul maxim de stive care pot construi respectând regulile date și numărul de cutii care pot fi aranjate astfel. Pentru că numerele pot fi foarte mari rezultatele se vor afișa modulo 1.000.000.007.
Date de intrare
Programul citește de la tastatură N.
Date de ieșire
Programul afișează pe ecran numărul maxim de stive care pot construi și numărul de cutii care pot fi aranjate modulo 1.000.000.007.
Restricții și precizări
- 1 ≤ N ≤ 1.000.000.000
Exemplu 1
- Intrare
3
- Iesire
7 11
Rezolvare
MOD = 1_000_000_007
def factorial(n, mod):
result = 1
for i in range(2, n + 1):
result = (result * i) % mod
return result
def mod_inverse(x, mod):
return pow(x, mod - 2, mod)
def comb(n, k, mod):
if k > n:
return 0
num = factorial(n, mod)
denom = (factorial(k, mod) * factorial(n - k, mod)) % mod
return (num * mod_inverse(denom, mod)) % mod
def calculate_stive_and_cuts(N):
# Numărul maxim de stive este (N + 1) * N // 2
max_stive = (N + 1) * N // 2
# Numărul de moduri de a aranja cutiile
num_cuts = 1
for i in range(1, N):
num_cuts = (num_cuts * (2 * N - i) * mod_inverse(i, MOD)) % MOD
return max_stive, num_cuts
def main():
N = int(input().strip())
assert 1 <= N <= 1000000000, "N nu este in parametru"
max_stive, num_cuts = calculate_stive_and_cuts(N)
print(max_stive+1, num_cuts+1)
if __name__ == "__main__":
main()