fork download
copy 
  1. module Enumerable
  2.   def tally(h = {})
  3.     each_with_object(h) {|x, h| h[x] = (h[x] || 0) + 1}
  4.   end
  5. end
  6. def initial(s, w)
  7.   return nil if s < w || w * 5 < s
  8.   q, r = (s - w).divmod 4
  9.   [w - q - (0 < r ? 1 : 0), 0, 0, 0, q].tap {|b| b[r] = 1 if 0 < r}
  10. end
  11. def next_or_nil(a)
  12.   (a.size - 2).downto(0).each_with_object(nil) {|i, _|
  13.     next if a[i] == 0
  14.     next if not j = (i + 2...a.size).find {|j| a[j] != 0}
  15.     return a.dup.tap {|a|
  16.       a[i] -= 1; a[i + 1] += 1
  17.       a[j] -= 1; a[j - 1] += 1
  18.       k = i + 1
  19.       s = a[k..-1].each.with_index(k + 1).inject(0) {|s, (c, d)| s + c * d}
  20.       w = a[k..-1].sum
  21.       w3, r = (s - w * (k + 1)).divmod(5 - (k + 1))
  22.       w2 = 0 < r ? 1 : 0
  23.       w1 = w - w2 - w3
  24.       a.fill(0, k..-1)
  25.       a[k] = w1
  26.       a[k + r] += w2
  27.       a[-1] = w3
  28.     }
  29.   }
  30. end
  31. def nexts(a)
  32.   a && [a].tap {|b| b << a while a = next_or_nil(a)}
  33. end
  34. def f(m, n)
  35.   n_permutations = ->a {
  36.     factrial = ->n {(1..n).inject(:*) || 1}
  37.     factrial.(a.sum) / a.map(&factrial).inject(:*)
  38.   }
  39.   count_permutations = ->s, w {
  40.     nexts(initial(s, w))&.map(&n_permutations)&.sum || 0
  41.   }
  42.   aux = ->acc, b, s, w {
  43.     return acc if s < 1 || w < 1
  44.     return acc << s if w == 1
  45.     (1..5).inject(b) {|b, d|
  46.       c = count_permutations.(s - d, w - 1)
  47.       return aux.(acc << d, b, s - d, w - 1) if n <= b + c
  48.       b + c
  49.     } && nil
  50.   }
  51.   (1..m).inject(0) {|b, w|
  52.     c = count_permutations.(m, w)
  53.     return aux.([], b, m, w).join.to_i if n <= b + c
  54.     b + c
  55.   } && 0
  56. end
  57. g = ->m, n {puts "(#{m},#{n}) → #{f(m, n)}"}
  58. g.(2,1)
  59. g.(2,2)
  60. g.(2,3)
  61. g.(20,1)
  62. g.(20,2)
  63. g.(20,3)
  64. g.(20,400096)
  65. g.(20,400097)
  66. g.(32,1)
  67. g.(32,2)
  68. g.(32,3)
  69. g.(32,1000)
  70. g.(32,1000000)
  71. g.(32,1000000000)
  72. g.(32,1333610936)
  73. g.(32,1333610937)
  74.  
Success #stdin #stdout 0.04s 10424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
(2,1) → 2
(2,2) → 11
(2,3) → 0
(20,1) → 5555
(20,2) → 14555
(20,3) → 15455
(20,400096) → 11111111111111111111
(20,400097) → 0
(32,1) → 2555555
(32,2) → 3455555
(32,3) → 3545555
(32,1000) → 34355354
(32,1000000) → 11532334334
(32,1000000000) → 2141111311212411131
(32,1333610936) → 11111111111111111111111111111111
(32,1333610937) → 0
https://ideone.com/jHqv2L
language:
Ruby (ruby 2.5.5)
created:
21 hours ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!