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 n_permutations(a)
  7.   factrial = ->n {(1..n).inject(:*) || 1}
  8.   factrial.(a.size) / a.tally.values.map(&factrial).inject(:*)
  9. end
  10. def next_or_nil(a)
  11.   (a.size - 2).downto(0).each_with_object(nil) {|i, _|
  12.     next if a[i] == a[i + 1]
  13.     next if not j = (i + 1...a.size).find {|j| 2 <= a[j] - a[i]}
  14.     return a.dup.tap {|a|
  15.       a[i] += 1; a[j] -= 1
  16.       w = a.size - j
  17.       w3, r = (a[j, w].sum - w * a[i]).divmod(5 - a[i])
  18.       w2 = 0 < r ? 1 : 0
  19.       w1 = w - w2 - w3
  20.       a.fill(a[i], j, w1).fill(a[i] + r, j + w1,  w2).fill(5, j + w1 + w2, w3)
  21.     }
  22.   }
  23. end
  24. def nexts(a)
  25.   a && [a].tap {|b| b << a while a = next_or_nil(a)}
  26. end
  27. def initial(s, w)
  28.   q, r = (s - w).divmod 4
  29.   0 < w && w <= s && s <= w * 5 && (r == 0 || q + 1 <= w) && Array.new(w, 1).tap {|b|
  30.     (1..q).each {|i| b[-i] += 4}
  31.     b[-q -1] += r if 0 < r
  32.   } || nil
  33. end
  34. def f(m, n)
  35.   count_permutations = ->s, w {
  36.     nexts(initial(s, w))&.map(&method(:n_permutations))&.sum || 0
  37.   }
  38.   aux = ->acc, b, s, w {
  39.     return acc if s < 1 || w < 1
  40.     return acc << s if w == 1
  41.     (1..5).inject(b) {|b, d|
  42.       c = count_permutations.(s - d, w - 1)
  43.       return aux.(acc << d, b, s - d, w - 1) if n <= b + c
  44.       b + c
  45.     } && nil
  46.   }
  47.   (1..m).inject(0) {|b, w|
  48.     c = count_permutations.(m, w)
  49.     return aux.([], b, m, w).join.to_i if n <= b + c
  50.     b + c
  51.   } && 0
  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.05s 10692KB
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/iwQNCH
language:
Ruby (ruby 2.5.5)
created:
1 day 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!