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 cumsum(a)
  7.   a.inject([]) {|acc, x| acc << (acc.last || 0) + x}
  8. end
  9. def n_permutations(a)
  10.   factrial = ->n {(1..n).inject(:*) || 1}
  11.   factrial.(a.size) / a.tally.values.map(&factrial).inject(:*)
  12. end
  13. def next_or_nil(a)
  14.   (a.size - 2).downto(0).each_with_object(nil) {|i, _|
  15.     next if not j = (i + 1...a.size).find {|j| 2 <= a[j] - a[i]}
  16.     return a.dup.tap {|a|
  17.       a[i] += 1; a[j] -= 1
  18.       loop {
  19.         j = (i + 1...a.size).find {|j| a[i] < a[j]}
  20.         k = j && (a.size - 1).downto(j + 1).find {|k| a[j] <= a[k] && a[k] < 5}
  21.         break if !k
  22.         a[j] -= 1; a[k] += 1
  23.       }
  24.     }
  25.   }
  26. end
  27. def nexts(a)
  28.   a && [a].tap {|b| b << a while a = next_or_nil(a)}
  29. end
  30. def initial(s, w = nil)
  31.   w ||= s.divmod(5).tap {|q, r| break q + (r == 0 ? 0 : 1)}
  32.   q, r = (s - w).divmod 4
  33.   0 < w && w <= s && s <= w * 5 && (r == 0 || q + 1 <= w) && Array.new(w, 1).tap {|b|
  34.     (1..q).each {|i| b[-i] += 4}
  35.     b[-q -1] += r if 0 < r
  36.   } || nil
  37. end
  38. def f(m, n)
  39.   count_permutations = ->s, w {
  40.     nexts(initial(s, w))&.map(&method(:n_permutations))&.sum || 0
  41.   }
  42.   aux = ->acc, b, s, w {
  43.     return acc if !b || s < 1 || w < 1
  44.     c = cumsum((1..5).map {|hd| count_permutations.(s - hd, w - 1)}).prepend(0)
  45.     hd = c.index {|c| n <= b + c} || s
  46.     aux.(acc << hd, b + c[hd - 1], s - hd, w - 1)
  47.   }
  48.   c = cumsum((1..m).map {|w| count_permutations.(m, w)}).prepend(0)
  49.   w = c.index {|c| n <= c}
  50.   b = w && c[w - 1]
  51.   aux.([], b, m, w).join.to_i
  52. end
  53. g = ->m, n {puts "(#{m},#{n}) → #{f(m, n)}"}
  54. g.(2,1)
  55. g.(2,2)
  56. g.(2,3)
  57. g.(20,1)
  58. g.(20,2)
  59. g.(20,3)
  60. g.(20,400096)
  61. g.(20,400097)
  62. g.(32,1)
  63. g.(32,2)
  64. g.(32,3)
  65. g.(32,1000)
  66. g.(32,1000000)
  67. g.(32,1000000000)
  68. g.(32,1333610936)
  69. g.(32,1333610937)
  70.  
Success #stdin #stdout 0.15s 8524KB
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/oAQimi
language:
Ruby (ruby 2.5.5)
created:
3 days 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!