最大Nの桁数が

Question

スティック絵はあなたが数字のそれぞれを描画する必要がありますどのように多くの棒を示しています。 にはN桁の数字が指定されています。私は数を最大にするためにいくつかの棒を動かしたい。私は桁数を変更できません。それはN桁の数字を常に持っていなければなりませんでした。マッチ棒を取り除くことはできません。

例：

given 512 
answer:977 
given 079 
answer:997 

私のソリューションは、私たちが使用できるマッチ棒の数をカウントしました。それから我々はそれを使い果たすまで9を置く。次に、一致するスティックが残っているような問題が発生したときには、それをバックトラックして数字を別の選択肢にします。これがすべての事件を取り込むかどうかはわかりません。 私のロジックに欠陥がありますか？もしそうなら、もっと良い方法は何ですか？

Answer 1

最初にスティックを自由に動かすことができるので、最初の数字の実際の値は私たちにとって重要ではないことがわかります。最初の数（s）と数字の桁数（n）にスティックの数を保持するだけで済みます。だから最初に最初の数のスティックの数を計算します。

数字の桁数が同じである必要があるため、必要な桁ごとに必要最小限の数字を割り当てることができます。数字は2つのスティックしか必要としないので、数字をn で初期化します。このようにして、私たちは桁数の要件を満たしていると確信しています。

で番号を初期化した後、から2*nスティックを削除する必要があります。

s -= 2*n 

各は、2本の棒を必要とし、我々はn個のものを使用していたので。

数字を最大限にするためには、できるだけ多く試してみてください。各には6本のスティックが必要です。すでに1桁に2本のスティックを使用していますので、桁に4本のスティックが必要です。私たちは余分なスティックを持つべきではない

1. ：

   たちは慎重であるべきである2つの例外があります。したがって、各ステップで、他のすべての数字を最もスティックをとる数字で使用するかどうかを計算する必要があります。スティックは残っていますか？ の数字が最も多く、7つのスティックが必要です。だから、の数字を作るためには、5本のスティックが必要です。いずれかのステップで残りのスティックsが残りの数字の5倍に等しい場合、残りの数字にはを使用する必要があります。 4（からを作るために必要なスティックの量）よりも、残りの少ないスティックがある場合

2. することは、我々は残りの数字と残りのスティックに関して最善の意思決定を取る必要があります。以下は

Python実装です：

def solve (s, # number of sticks 
      n): #number of digits 
    s -= 2*n # use n 1 digits 

    result = ["1"]*n 

    for i in range(n): 
     if s == 0: # no sticks remained 
      break 
     if s == 5*(n-i): # we should use 8 from now on or else there will be extra sticks 
      result[i] = "8" 
      s -= 5 
     elif s < 4: # not enough sticks to make a 9 
      if i == n-1: # this is the last digit make the most of if 
       if s == 3: # maximum digit is 5 with 5 sticks 
        result[i] = "5" 
        s -= 3 
       elif s == 2: # maximum digit is 4 with 4 sticks 
        result[i] = "4" 
        s -= 2 
       elif s == 1: # maximum digit is 7 with 3 sticks 
        result[i] = "7" 
        s -= 1 
      else: 
       result[i] = "7" 
       s -= 1 # maximum digit is 7 with less than 6 sticks 
     else: 
      result[i] = "9" 
      s -= 4 
    print "".join(result) 


needed_stick = {"0":6, "1":2, "2":5, "3":5, "4":4, "5":5, "6":6, "7":3, "8":7, "9":6} 
initial_number = raw_input("Initial number: ") 
s = sum(needed_stick[c] for c in initial_number) 
n = len(initial_number) 
solve(s,n) 

出力：

Initial number: 512 
977 

Initial number: 079 
997 

Initial number: 88888888888888 
88888888888888 

Initial number: 8881 
9995