4029 - Depozit

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

<syntaxhighlight lang="python" line> 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 <= 10000007, "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()

</syntaxhighlight>