Problem:


ランチ

お昼に食べるお弁当を作るために、お店で食べ物を買いました。お店では、食べ物を入れるのに細長い袋しかもらえなかったので、すべての食べ物を縦に積んで袋に入れる必要があります。袋が倒れにくいように、できるだけ重い物を下にして詰めたいのですが、食べ物の中にはやわらかい物もあって、上に重い物を乗せるとつぶれてしまいます。

そこで、食べ物の情報を入力とし、全ての食べ物がつぶれず、かつ全体の重心が最も低くなるような積み方を出力するプログラムを作成してください。それぞれの食べ物ごとに、名前 f、重さ w、上に載せて耐えられる重さ s  が指定されます。
「全ての食べ物がつぶれない」というのは、下から順に、（f1、f2、... 、fn）と n 個の食べ物を積んだ時、すべての f について、

sfi ≥ wfi+1 + wfi+2 +  ...  + wfn

であることを意味します。また、全体の重心 G は、

G = (1 &times; wf1 + 2 &times; wf2 +  ...  + n &times; wfn) / (wf1 + wf2+ ... +wfn)

とします。ただし、解はちょうど1つだけ存在するものとします。

Input

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

n
f1 w1 s1
f2 w2 s2
:
fn wn sn

１行目に食べ物の個数 n (1 ≤ n ≤ 10)、続く n 行に i 番目の食べ物の名前 fi (20 文字以内の半角英文字列)、重さ wi (1 ≤ wi ≤ 1000)、耐えられる重さ si (1 ≤ si ≤ 1000) が空白区切りで与えられます。

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

Output

データセットごとに、次の形式で食べ物の名前を下から積み上げる順に出力します。

1 行目: 1 番下の食べ物の名前（半角英文字列） 

2 行目: 下から2 番目の食べ物の名前

：

n 行目: 1 番上の食べ物の名前

Sample Input

4
sandwich 80 120
apple 50 200
cheese 20 40
cake 100 100
9
onigiri 80 300
onigiri 80 300
anpan 70 280
mikan 50 80
kanzume 100 500
chocolate 50 350
cookie 30 80
purin 40 400
cracker 40 160
0

Output for the Sample Input

apple
cake
sandwich
cheese
kanzume
purin
chocolate
onigiri
onigiri
anpan
mikan
cracker
cookie



Sample input:
4
sandwich 80 120
apple 50 200
cheese 20 40
cake 100 100
9
onigiri 80 300
onigiri 80 300
anpan 70 280
mikan 50 80
kanzume 100 500
chocolate 50 350
cookie 30 80
purin 40 400
cracker 40 160
0


Sample output:
apple
cake
sandwich
cheese
kanzume
purin
chocolate
onigiri
onigiri
anpan
mikan
cracker
cookie

Submission status: Wrong Answer

Solution code:
a=list(map(int, input().split()))
x=["A","B","C"]
print(x[a.index(max(a))])

Submission status: Wrong Answer

Solution code:
def solve(placed, w1, w2):
  n = len(N) - len(placed)
  x = list(set(N) - set(placed))
  if x == []:
    a = tuple(placed)
    D1[a] = w1
    D2[a] = w2
    return 1
  
  for e in x:
    w = Food[e]
    if w2 > Lim[e]: return 0
    a = w1 + w * n
    b = w2 + w
    f = solve(placed+[e], a, b)
    if f: return 1
  return 0

while 1:
  n = input()
  if n==0: break
  D1 = {}
  D2 = {}
  N = range(n)
  x = []
  for i in N:
    a = raw_input().split()
    x.append(map(int, a[1:])+[a[0]])
  x = zip(*sorted(x))
  Name = list(x[2])
  Food = list(x[0])
  Lim = list(x[1])
  solve([], 0, 0)
  
  Index, e = sorted(D1.items(), key = lambda x: x[1])[0]
  for e in list(Index)[::-1]:
    print Name[e]

Submission status: Wrong Answer

Solution code:
def solve(placed, w1, w2):
  global weight, D
  n = len(N) - len(placed)
  x = list(set(N) - set(placed))
  if x == []:
    if weight > w1:
      D = placed
      weight = w1
    return
   
  for e in x:
    w = W[e]
    if w2 > S[e]: return
    a = w1 + w * n
    if a > weight: return 1
    b = w2 + w
    if solve(placed+[e], a, b): return 1
  return
 
while 1:
  n = input()
  if n==0: break
  D = []
  weight = 1e9
  N = range(n)
  f = lambda x: [int(x[1]),int(x[2]),x[0]]
  x = [f(raw_input().split()) for _ in [0]*n]
  W, S, Name = zip(*sorted(x))
  solve([], 0, 0)
  for e in D[::-1]:
    print Name[e]

Submission status: Wrong Answer

Solution code:
def solve(G1, G2, w1, w2):
  global ans
  n = len(G2)
  for e in G2:
    w, lim, s = Food[e]
    if w2 > lim:
      return
    a = w1 + w * n
    if a > ans[0]:
      return
    if n==1:
      ans = min(ans, [w1, G1+[e]])
    else:
      x = G2[:]
      x.remove(e)
      solve(G1+[e], x, a, w2 + w)
  return
 
while 1:
  n = input()
  if n == 0: break
  ans = [1e9, []]
  N = range(n)
  f = lambda x: map(int, x[1:3]) + [x[0]]
  Food = [f(raw_input().split()) for _ in [0] * n]
  solve([], N, 0, 0)
  for e in ans[1][::-1]:
    print Food[e][2]

Submission status: Wrong Answer

Solution code:
import itertools
from copy import deepcopy

def stuck(array):
	order=[]
	while array:
		r = len(array)
		w = sum([array[i][1] for i in range(r)])
		mx = 0
		for i in range(r):
			if array[i][2] >= w-array[i][1] and array[i][2] > mx:
				mx = array[i][2]
				id=i
		order.append(array.pop(id)[0])
	return order

def change(a):
	return a[0],int(a[1]),int(a[2])
	
while 1:
	n=input()
	if n==0:break
	lunch=[change(raw_input().split()) for i in range(n)]
	ans=stuck(lunch)
	for i in range(n):
		print ans[i]

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0170

"""
import sys
from sys import stdin
input = stdin.readline
from collections import namedtuple
from itertools import permutations


def solve(items):
    total_weight = 0
    for i in items:
        total_weight += i.w

    best_ans = []
    best_gp = float('inf')
    # ???????????????????????????????????????????????°?????????????????§????????????
    for perm in permutations(items):
        ans = []
        squashed = False
        cw = 0
        gp = 0
        n = len(items)

        for p in perm:
            if p.s < cw:
                squashed = True
                break
            cw += p.w
            ans.append(p.name)
            gp += n * p.w
            n -= 1
        # ????????°???????????£?????´????????????????¨???????????????????????????????????????£?????????????????§????????????
        if not squashed:
            gp /= total_weight
            if gp < best_gp:
                best_gp = gp
                best_ans = ans[:]
    # ????????????????????????????????£??????????????§?????????????±?????????????????????????????????????????????????
    best_ans.reverse()
    return best_ans


item = namedtuple('item', ['name', 'w', 's'])
def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        items = []
        for _ in range(n):
            name, w, s = input().split()
            items.append(item(name, int(w), int(s)))

        result = solve(items)
        print('\n'.join(result))


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
import itertools
from copy import deepcopy

def stuck(Array,Order):
	remain = len(Array)
	if remain == 0: return G(Order),Order
	minG,minOrder = 9999999,[]
	w = sum([int(Array[i][1]) for i in range(remain)])
	for i in range(remain):
		if int(Array[i][2]) >= w-int(Array[i][1]):
			array = deepcopy(Array)
			order = deepcopy(Order)
			order[n-remain] = array.pop(i)
			curG,curOrder = stuck(array,order)
			if curG < minG:
				minG = curG
				minOrder = curOrder
	return minG,minOrder

def G(array):
	nume=sum([(i+1)*int(array[i][1]) for i in range(n)])*1.0
	denomi=sum([int(array[i][1]) for i in range(n)])
	return nume/denomi
	
while 1:
	n=input()
	if n==0:break
	lunch=[raw_input().split() for i in range(n)]
	minG,ans=stuck(lunch,[0]*n)
	for i in range(n):
		print ans[i][0]

Submission status: Accepted

Solution code:
def solve(placed, w1, w2):
  n = len(N) - len(placed)
  x = list(set(N) - set(placed))
  if x == []:
    a = tuple(placed)
    D1[a] = w1
    D2[a] = w2
    return
  
  for e in x:
    w = Food[e][0]
    if w2 > Food[e][1]: return
    a = w1 + w * n
    b = w2 + w
    solve(placed+[e], a, b)
  return

while 1:
  n = input()
  if n==0: break
  D1 = {}
  D2 = {}
  Name = {}
  Food = {}
  N = range(n)
  for i in N:
    a = raw_input().split()
    Food[i] = map(int, a[1:])
    Name[i] = a[0]
    
  solve([], 0, 0)
  
  Index, e = sorted(D1.items(), key = lambda x: x[1])[0]
  for e in list(Index)[::-1]:
    print Name[e]

Submission status: Accepted

Solution code:
def solve(placed, w1, w2):
  global weight, D
  n = len(N) - len(placed)
  x = list(set(N) - set(placed))
  if x == []:
    if weight > w1:
      D = placed
      weight = w1
    return
   
  for e in x:
    w = Food[0][e]
    if w2 > Food[1][e]: return
    a = w1 + w * n
    if a > weight: return
    b = w2 + w
    solve(placed+[e], a, b)
  return
 
while 1:
  n = input()
  if n==0: break
  Food = {}
  weight = 1e9
  N = range(n)
  x = []
  for i in N:
    a = raw_input().split()
    x.append(map(int, a[1:])+[a[0]])
  Food = zip(*sorted(x))
  solve([], 0, 0)
  for e in D[::-1]:
    print Food[2][e]

Submission status: Accepted

Solution code:
def solve(placed, w1, w2):
  global weight, D
  n = len(N) - len(placed)
  x = list(set(N) - set(placed))
  if x == []:
    if weight > w1:
      D = placed
      weight = w1
    return
   
  for e in x:
    w = W[e]
    if w2 > S[e]: return
    a = w1 + w * n
    if a > weight: return
    b = w2 + w
    solve(placed+[e], a, b)
  return
 
while 1:
  n = input()
  if n==0: break
  D = []
  weight = 1e9
  N = range(n)
  f = lambda x: [int(x[1]),int(x[2]),x[0]]
  x = [f(raw_input().split()) for _ in [0]*n]
  W, S, Name = zip(*sorted(x))
  solve([], 0, 0)
  for e in D[::-1]:
    print Name[e]

Submission status: Accepted

Solution code:
def solve(placed, w1, w2):
  global ans
  n = len(N) - len(placed)
  if n==0:
    ans = min(ans, [w1, placed])
    return

  for e in N:
    if e in placed: continue
    w, lim, s = Food[e]
    if w2 > lim: return
    a = w1 + w * n
    if a > ans[0]: return
    solve(placed+[e], a, w2 + w)
  return
 
while 1:
  n = input()
  if n==0: break
  ans = [1e9, []]
  N = range(n)
  f = lambda x: map(int, x[1:3]) + [x[0]]
  Food = [f(raw_input().split()) for _ in [0]*n]
  solve([], 0, 0)
  for e in ans[1][::-1]:
    print Food[e][2]

Submission status: Accepted

Solution code:
def solve(G1, G2, w1, w2):
  global ans
  n = len(G2)
  for e in G2:
    w, lim, s = Food[e]
    a = w1 + w * n
    if w2 > lim or a > ans[0]: return
    b = G1 + [e]
    if n == 1:
      ans = min(ans, [a, b])
    else:
      x = G2[:]
      x.remove(e)
      solve(b, x, a, w2 + w)
  return
 
while 1:
  n = input()
  if n==0: break
  ans = [1e9, []]
  N = range(n)
  f = lambda x: map(int, x[1:3]) + [x[0]]
  Food = [f(raw_input().split()) for _ in [0]*n]
  solve([], N, 0, 0)
  for e in ans[1][::-1]:
    print Food[e][2]

Submission status: Accepted

Solution code:
import copy

while True:
    n = input()
    if n == 0: break
    L = []
    for i in range(n):
        f, w, s = raw_input().split()
        L.append([f, int(w), int(s)])
    else:
        L = sorted(L, key=lambda x: int(x[1]), reverse=True)
    
    ans = []
    while len(L) != 1:
        for i in range(len(L)):
            _L = copy.deepcopy(L)
            f = _L[i][0]
            s = _L[i][2]
            del _L[i]
            t = sum([_L[o][1] for o in range(len(_L))])
            if t <= s:
                ans.append(f)
                del L[i]
                break
    else:
        ans.append(L[0][0])
        for line in ans:
            print line

Submission status: Accepted

Solution code:
import copy

while True:
    n = input()
    if n == 0: break
    L = []
    for i in range(n):
        f, w, s = raw_input().split()
        L.append([f, int(w), int(s)])
    else:
        L = sorted(L, key=lambda x: x[1], reverse=True)
    
    ans = []
    while len(L) != 1:
        for i in range(len(L)):
            _L = copy.deepcopy(L)
            f = _L[i][0]
            s = _L[i][2]
            del _L[i]
            t = sum([_L[o][1] for o in range(len(_L))])
            if t <= s:
                ans.append(f)
                del L[i]
                break
    else:
        ans.append(L[0][0])
        for f in ans:
            print f

Submission status: Accepted

Solution code:
while 1:
    n = input()
    if n == 0:
        break
    F = [0]*n
    W = [0]*n
    S = [0]*n

    def dfs(c, state, used, su):
        if c == n:
            return [sum((1+i)*W[state[n-1-i]] for i in xrange(n)), state[::-1]]
        mi = [10**9, None]
        for i in xrange(n):
            if not used[i] and S[i] >= su:
                state[c] = i
                used[i] = 1
                mi = min(mi, dfs(c+1, state, used, su + W[i]))
                used[i] = 0
        return mi

    for i in xrange(n):
        F[i], w, s = raw_input().split()
        W[i] = int(w)
        S[i] = int(s)
    for i in dfs(0, [0]*n, [0]*n, 0)[1]:
        print F[i]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0170

"""
import sys
from sys import stdin
input = stdin.readline
from collections import namedtuple
from itertools import permutations


def solve(items):
    total_weight = 0
    for i in items:
        total_weight += i.w
    best_ans = []
    best_gp = float('inf')
    # ???????????????????????????????????????????????°?????????????????§????????????
    for perm in permutations(items):
        ans = []
        squashed = False
        cw = 0
        gp = 0
        n = len(items)
        for p in perm:
            if p.s < cw:
                squashed = True
                break
            cw += p.w
            ans.append(p.name)
            gp += n * p.w
            n -= 1
        # ????????°???????????£?????´????????????????¨???????????????????????????????????????£?????????????????§????????????
        if not squashed:
            gp /= total_weight
            if gp < best_gp:
                best_gp = gp
                best_ans = ans[:]
    # ????????????????????????????????£??????????????§?????????????±?????????????????????????????????????????????????
    best_ans.reverse()
    return best_ans


def solve2(items):
    items.sort(key=lambda x:x.w, reverse=True)
    ans = []
    while items:
        total_weight = 0
        for i in items:
            total_weight += i.w
        cap = [x.s - total_weight + x.w for x in items]
        for i in range(len(items)):
            if cap[i] >= 0:
                ans.append(items[i].name)
                items.pop(i)
                break
    return ans



item = namedtuple('item', ['name', 'w', 's'])
def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        items = []
        for _ in range(n):
            name, w, s = input().split()
            items.append(item(name, int(w), int(s)))
        result = solve2(items)
        print('\n'.join(result))


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0170

"""
import sys
from sys import stdin
input = stdin.readline
from collections import namedtuple


def solve(items):
    from itertools import permutations
    total_weight = 0
    for i in items:
        total_weight += i.w
    best_ans = []
    best_gp = float('inf')
    # ???????????????????????????????????????????????°?????????????????§????????????
    for perm in permutations(items):
        ans = []
        squashed = False
        cw = 0
        gp = 0
        n = len(items)
        for p in perm:
            if p.s < cw:
                squashed = True
                break
            cw += p.w
            ans.append(p.name)
            gp += n * p.w
            n -= 1
        # ????????°???????????£?????´????????????????¨???????????????????????????????????????£?????????????????§????????????
        if not squashed:
            gp /= total_weight
            if gp < best_gp:
                best_gp = gp
                best_ans = ans[:]
    # ????????????????????????????????£??????????????§?????????????±?????????????????????????????????????????????????
    best_ans.reverse()
    return best_ans


def solve2(items):
    items.sort(key=lambda x:x.w, reverse=True) # ??????????????????????????????
    total_weight = 0            #  ??¢?????????????????????
    for i in items:
        total_weight += i.w
    ans = []
    # ?????£???????????¢??????????????????????????????????????????????????§???????????¢??????????????????????????????????????????????????????????????????????????¢?????????????????????????????§??°????????????
    while items:
        cap = [x.s - total_weight + x.w for x in items] #  ????????\??????????????¢?????????????????????????????¨????????°??????????????????????????????????????????????????????0??\?????????OK
        for i in range(len(items)):
            if cap[i] >= 0:     #  ??°???????????????????????????????????????????????????????????????????????????
                ans.append(items[i].name)
                i = items.pop(i)
                total_weight -= i.w #  ???????????¢?????????????????????????????????
                break
    return ans


item = namedtuple('item', ['name', 'w', 's'])
def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        items = []
        for _ in range(n):
            name, w, s = input().split()
            items.append(item(name, int(w), int(s)))
        result = solve2(items)
        print('\n'.join(result))


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
from collections import namedtuple

Data = namedtuple("Data", "name weight limit")


def search(food_list, select_list, total_weight):
    if len(food_list) == 0:
        return select_list

    limit = select_list[len(select_list) - 1].limit

    for lp, food in enumerate(food_list):

        if total_weight <= limit:

            select_list.append(food)
            food_list.remove(food)
            total_weight -= food.weight

            search(food_list, select_list, total_weight)

            if len(food_list) == 0:
                return select_list
            else:
                select_list.pop()
                food_list.insert(lp, food)
                total_weight += food.weight

    return None


while True:
    input_count = int(input())

    if input_count == 0:
        break

    input_data = [input().split(" ") for _ in range(input_count)]
    input_data = [Data(item[0], int(item[1]), int(item[2])) for item in input_data]

    input_data.sort(key=lambda x: (x.weight, x.limit), reverse=True)

    total_weight = sum([item.weight for item in input_data])

    result = search(input_data, [Data("sentinel", 0, 999999)], total_weight)
    del result[0]

    output = [item.name for item in result]
    print("\n".join(output))

Submission status: Accepted

Solution code:
def stuck(array):
	order=[]
	while array:
		r = len(array)
		w = sum([array[i][1] for i in range(r)])
		mx = 0
		for i in range(r):
			if array[i][2] >= w-array[i][1] and array[i][1] > mx:
				mx = array[i][1]
				id = i
		order.append(array.pop(id)[0])
	return order

def change(a):
	return a[0],int(a[1]),int(a[2])
	
while 1:
	n = input()
	if n == 0:break
	lunch = [change(raw_input().split()) for i in range(n)]
	ans = stuck(lunch)
	for i in range(n):
		print ans[i]

Submission status: Accepted

Solution code:
INF = 10 ** 20
while True:
  n = int(input())
  if n == 0:
    break
  names = []
  weights = []
  safes = []
  for _ in range(n):
    f, w, s = input().split()
    names.append(f)
    weights.append(int(w))
    safes.append(int(s))
  all_weight = sum(weights)
  dic = [None] * (2 ** n)
  
  def score(rest, total_weight, count):
    if dic[rest] != None:
      return dic[rest]
    if rest == 0:
      return (0, [])

    ret = (INF, [])
    mask = 1
    for i in range(n):
      if rest & mask:
        if safes[i] >= all_weight - total_weight - weights[i]:
          temp = score(rest & ~mask, total_weight + weights[i], count + 1) 
          ret = min(ret, (temp[0] + weights[i] * (count + 1), [names[i]] + temp[1]))
      mask <<= 1
    dic[rest] = ret
    return ret

  print(*score(2 ** n - 1, 0, 0)[1], sep="\n")

Submission status: Runtime Error

Solution code:
import itertools

def isOK(array):
	for i in range(n-1):
		if int(array[i][2])<sum([int(array[i][1]) for x in range(i+1,n)]):
			return False
	return G(array)

def G(array):
	nume=sum([(i+1)*int(array[i][1]) for i in range(n)])*1.0
	denomi=sum([int(array[i][1]) for i in range(n)])
	return nume/denomi
	
while 1:
	n=input()
	if n==0:break
	lunch=[raw_input().split() for i in range(n)]
	ans,minG=[],10000
	for order in itertools.permutations(lunch,n):
		print order
		val=isOK(order)
		if val is not False and val<minG:
			ans=[order[i][:] for i in range(n)]
			minG=val
	for i in range(n):
		print ans[i][0]