Latest comments replied to shuyo

nkmrtks's comment on トランプの和と積のパズル

#1610で試してみたら

(trump-pairs 14)
=> ((3 4) (1 4))
(trump-pairs 38)
=> ((5 8) (4 7) (1 4))
(trump-pairs 300)
=> ((16 43) (16 37) (8 29) (16 19) (8 23) (4 17) (7 8) (1 9) (1 8) (1 4))

で300の時に「2^n (n>=0) と奇数の組み合わせ」になってない(1 9)があるんだけど、これはコッチが間違ってるかな？かな？

shuyo's comment on トランプの和と積のパズル

トランプの和と積のパズル (Nested Flatten)

300までの解とかみると、全ての解が 2^n (n>=0) と奇数の組み合わせになってるんだけど、なんかそういう法則性があることを示せたりするのかな～？

shuyo's comment on 倍数になる13進数

倍数になる13進数 (Nested Flatten)

先のコードはバグがあって、解の見落としが発生することがわかりました。すんません。ということで修正＆最適化したものを投稿。３０桁くらいまでならほぼ瞬殺で出力します。

def search(m, rem, result)
  rem2 = rem[1..rem.length-1]
  ai = -rem[0]
  min = rem2.inject(m+ai-1){|sum,a|sum+(a>0?0:a*9)}/ai
  max = rem2.inject(m){|sum,a|sum+(a>0?a*9:0)}/ai
  #puts "#{m}, #{rem.inspect}, #{min}, #{max}"
  min = 0 if min < 0
  max = 9 if max > 9
  return if min > max
  min.upto(max) do |x|
    if rem2.length == 1
      if (m-x*ai) % rem2[0] == 0
        y = (x*ai-m) / rem2[0]
        puts "#{result}#{x}#{y}" if y>=0 && y<=9
      end
    else
      search m-x*ai, rem2, "#{result}#{x}"
    end
  end
end

d=3 # keta - 1
while true
  puts "keta: #{d+1} =========================================================="
  max_n = 13**d / 10**d
  1.upto(9) do |ad| # highest digit
    x13 = ad*13**d
    x10 = ad*10**d
    min_n = (x13 + 9*(13**d-1)/12) / (x10 + (10**d-1))
    puts [min_n, max_n].join(', ') if min_n > max_n
    min_n.upto(max_n) do |n|
      m = x13 - x10*n
      rem = []
      0.upto(d-1){|i| rem.unshift 13**i - 10**i * n }
      search m, rem, "#{ad}"
    end
  end
  d+=1
end

[ Ruby ] [ download code ] ]

shuyo's comment on 倍数になる13進数

倍数になる13進数 (Nested Flatten)

お題から少し外れるが、条件を満たす数を探し続けるプログラム。汚かったり最適化の余地が残っているのはご勘弁。これを２時間走らせて４６桁まで探索済み。見つかっている一番大きい値は 60065682893774087238167921857827939124689630 (44桁)。やっぱり無限にありそうだなあ。

def search(m, rem, result)
  rem2 = rem[1..rem.length-1]
  sum = rem2.inject{|a,b|a+b}
  min = (-sum*9 - m)/rem[0]
  max = (sum*9 - m)/rem[0]
  min = 0 if min < 0
  max = 9 if max > 9
  return if min > max
  min.upto(max) do |x|
    if rem2.length == 1
      if (m+x*rem[0]) % rem2[0] == 0
        y = - (m+x*rem[0]) / rem2[0]
        puts (result+[x, y]).join('') if y>=0 && y<=9
      end
    else
      search m+x*rem[0], rem2, result+[x]
    end
  end
end

d=3 # keta - 1
while
  min_n = 13**d / 10**d
  max_n = (9*(13**(d+1)-1)/12) / (10**(d+1)-1)
  min_n, max_n = max_n, min_n if min_n > max_n
  puts "keta: #{d+1}"
  1.upto(9) do |ad| # highest digit
    x13 = 13**d*ad
    x10 = 10**d*ad
    min_n.upto(max_n) do |n|
      m = x13 - x10*n
      #puts [m, n].join(',')
      rem = []
      0.upto(d-1){|i| rem.unshift 13**i - 10**i * n }
      search m, rem, [ad]
    end
  end
  d+=1
end

[ Ruby ] [ download code ] ]

shuyo's comment on 倍数になる13進数

倍数になる13進数 (Nested Flatten)

この解が有限個なのか無限個なのかが気になる…… とりあえず４桁の次は８桁に３つあるなあ。

yuin's comment on コインを減らす払い方

コインを減らす払い方 (Nested Flatten)

pay(147, {1=> 2, 5=>300, 10=> 4, 100=> 3})
=> {5=>299, 1=>2, 100=>2}

これあってますよね。
たぶん#73の方と同じ疑問点なのだと思いますが、

5 * 299 + 1 * 2 + 100 * 2 = 1697
1697 - 147 = 1550

でおつりは500 * 3, 50 * 1。確かに一番減ります。こんなお金の出され方したら怒りますけど（笑

Pythonでも同じアルゴリズムで書いてみました。

from operator import *
def pay(m, w):
  r = dict()
  m = sum((k*w[k] for k in w)) - m
  if m < 0: raise "money"
  for c in (500,100,50,10,5,1):
    r[c] = w.get(c, 0) - m / c
    m %= c
  return dict(((k,v) for k,v in r.items() if v > 0))

[ Python ] [ download code ] ]