Problem:


ばらばら饅頭

会津若松市にある和菓子屋・友栗堂の店長さんは、とても腕のいい職人さんなのにちょっと気分屋なのが玉にキズです。店長さんの作る饅頭はとても美味しいのですが、その時の気分によって大きさがまちまちになってしまいます。

見かねた店長さんの奥さんは、大きさと重さがばらばらな饅頭を袋に詰めて売り出すことを思いつきました。一定の重さになるように饅頭を袋に詰めて売れば、一つ一つの大きさはばらばらでも一定の値段で売り出すことが出来ますし、どんな饅頭が入っているのか開けるまでわからないというサプライズも売りになるかもしれません。
「ばらばら饅頭」という名前で売りだしたところ、新しいアイディアが話題となり友栗堂はたちまち評判となりました。しかし、問題もあり、袋に入れる饅頭の組み合わせ方によって作れる「ばらばら饅頭」の数が変わり、無駄が発生してしまうことがありました。アルバイトで友栗堂に来ていたあなたは無駄なく袋に詰めるためにプログラムをつくることにしました。

饅頭の重さは1から9の9種類あります。袋に詰める時には、饅頭の重さの合計がぴったり10になるように詰め込みます。饅頭の組み合わせ方は1+1+2+4+2=10や1+1+1+1+1+5=10などで、同じ重さの饅頭をいくつ使っても構いません。

作られる饅頭の個数と饅頭の重さの情報を入力とし、作ることのできる「ばらばら饅頭」の最大の数を出力するプログラムを作成してください。

入力

複数のデータセットが与えられます。入力の終わりはゼロひとつで示されます。各データセットは以下の形式で与えられます。

n
m1 m2 ... mn

1行目に饅頭の個数 n (2 ≤ n ≤ 100) が与えられます。
2行目に各饅頭の重さmi (1 ≤ mi ≤ 9) が与えられます。

データセットの数は 100 を超えません。

出力

データセットごとに、詰め込むことのできた「ばらばら饅頭」の最大の数を1行に出力します。

入力例

5
4 9 1 3 8
10
8 5 3 6 2 1 4 5 4 5
9
5 7 3 8 2 9 6 4 1
0

出力例

1
4
4



Sample input:
5
4 9 1 3 8
10
8 5 3 6 2 1 4 5 4 5
9
5 7 3 8 2 9 6 4 1
0


Sample output:
1
4
4

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
  def make_num(target, counter):
    if target == 0:
      return True
    for i in range(target, 0, -1):
      if counter[i] > 0:
        counter[i] -= 1
        flag = make_num(target - i, counter)
        if flag:
          return True
        else:
          counter[i] += 1
    return False
  
  while True:
    n = int(input())
    if n == 0:
      break
    counter = Counter(map(int, input().split()))
    ans = 0
    for max_num in range(9, 0, -1):
      target = 10 - max_num
      delete_num = counter[max_num]
      while delete_num:
        counter[max_num] -= 1
        if make_num(target, counter):
          delete_num -= 1
          ans += 1
        else:
          counter[max_num] += 1
          break
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
  def make_num(target, counter):
    if target == 0:
      return True
    for i in range(target, 0, -1):
      if counter[i] > 0:
        counter[i] -= 1
        flag = make_num(target - i, counter)
        if flag:
          return True
        else:
          counter[i] += 1
    return False
  
  while True:
    n = int(input())
    if n == 0:
      break
    counter = Counter(map(int, input().split()))
    ans = 0
    for max_num in range(9, 0, -1):
      target = 10 - max_num
      delete_num = counter[max_num]
      while delete_num:
        counter[max_num] -= 1
        if make_num(target, counter):
          delete_num -= 1
          ans += 1
        else:
          counter[max_num] += 1
          break
    print(ans)
main()