Problem:


巨樹の刻み手

あなたは N 種類の道具を使って、目の前の巨樹を切り倒そうとしています。はじめは、樹の耐久力は D、あなたの経験値は 0 ですが、道具 i で１回樹を叩くと樹の耐久力は ai 減り、あなたは ei の経験値を得ます。ただし、道具 i を使うためには、あなたは ri 以上の経験値を持っていなければなりません。樹の耐久力が 0 以下になると樹は倒れます。

樹の耐久力と道具についての情報が与えられたとき、樹を切り倒すには最低何回樹を叩かなければいけないかを求めるプログラムを作成してください。

入力

入力は複数のデータセットからなる。入力の終わりはゼロ２つの行で示される。各データセットは以下の形式で与えられる。

D N
a1 e1 r1
a2 e2 r2
:
aN eN rN

1 行目に樹の耐久力を表す整数 D (1 ≤ D ≤ 100) と道具の種類の数 N(1 ≤ N ≤ 100) が与えられる。続く N 行に道具 1 から N までの情報が与えられる。ai (0 ≤ ai ≤ 100) と ei (0 ≤ ei ≤ 100) は、道具iを１回使うことで減る樹の耐久力とあなたが得ることのできる経験値をそれぞれ表す。ri (0 ≤ ri ≤ 100) は道具を使うために必要な経験値を表す。ai, ei, ri はすべて整数である。

データセットの数は 50 を超えない。

出力

樹を切り倒すのに必要な、樹を叩く最小の回数を１行に出力する。ただし、樹を切り倒すことが不可能な場合は NA と出力する。

入出力例

入力例

15 4
1 1 0
1 2 2
5 10 5
8 1 15
60 4
5 2 0
8 8 2
3 5 0
49 0 18
100 1
1 1 1
0 0

出力例

6
4
NA



Sample input:
15 4
1 1 0
1 2 2
5 10 5
8 1 15
60 4
5 2 0
8 8 2
3 5 0
49 0 18
100 1
1 1 1
0 0


Sample output:
6
4
NA

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
INF = 10 ** 20

def search(item_lst):
  visited = {}
  visited[(0, 0)] = True
  que = []
  heappush(que, (0, 0, 0))
  while que:
    score, a, e = heappop(que)
    for da, de in item_lst[e]:
      na = a + da
      if na == d:
        print(score + 1)
        return True
      ne = e + de
      if ne > 100:
        ne = 100
      
      if (na, ne) not in visited:
        visited[(na, ne)] = True
        heappush(que, (score + 1, na, ne))
  
  print("NA")
  return False
def main():
  while True:
    d, n = map(int, input().split())
    if d == 0:
      break
    item_lst = [[] for _ in range(101)]
    for _ in range(n):
      a, e, r = map(int, input().split())
      for i in range(r, 101):
        item_lst[i].append((a, e))
    search(item_lst)

Submission status: Time Limit Exceeded

Solution code:
while 1:
  d,n=map(int,input().split())
  if d+n==0: break
  a,e,r=zip(*list(map(int,input().split()) for _ in range(n)))
  
  m=max(e+r)
  # dp[残り耐久力][経験値]=最小回数
  dp=[[float("inf")]*(m+1) for _ in range(d+1)]
  dp[d][0]=0
  for i in reversed(range(d+1)):
    for j in range(m+1):
      for k in range(n):
        if r[k]<=j:
          u,v=max(i-a[k],0),min(j+e[k],m)
          dp[u][v]=min(dp[u][v],dp[i][j]+1)
  
  res=min(dp[0])
  print(res if res<float("inf") else "NA")

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
INF = 10 ** 20
def search(item_lst):
  dp = [[INF] * 101 for _ in range(101)]
  dp[0][0] = 0
  que = []
  heappush(que, (0, 0, 0))
  while que:
    score, a, e = heappop(que)
    for da, de in item_lst[e]:
      na, ne = min(d, a + da), min(100, e + de)
      if na == d:
        print(score + 1)
        return True

      if dp[na][ne] > score + 1:
        dp[na][ne] = score + 1
        heappush(que, (score + 1, na, ne))
  
  print("NA")
  return False

while True:
  d, n = map(int, input().split())
  if d == 0:
    break
  item_lst = [[] for _ in range(101)]
  for _ in range(n):
    a, e, r = map(int, input().split())
    for i in range(r, 101):
      item_lst[i].append((a, e))
  search(item_lst)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
INF = 10 ** 20

def search(item_lst):
  visited = {}
  visited[(0, 0)] = True
  que = []
  heappush(que, (0, 0, 0))
  while que:
    score, a, e = heappop(que)
    for da, de in item_lst[e]:
      na, ne = min(d, a + da), min(100, e + de)
      if na == d:
        print(score + 1)
        return True

      if (na, ne) not in visited:
        visited[(na, ne)] = True
        heappush(que, (score + 1, na, ne))
  
  print("NA")
  return False

while True:
  d, n = map(int, input().split())
  if d == 0:
    break
  item_lst = [[] for _ in range(101)]
  for _ in range(n):
    a, e, r = map(int, input().split())
    for i in range(r, 101):
      item_lst[i].append((a, e))
  search(item_lst)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = 10 ** 20

def search(item_lst, d):
  visited = {}
  visited[(0, 0)] = True
  que = []
  heappush(que, (0, 0, 0))
  while que:
    score, a, e = heappop(que)
    for da, de in item_lst[e]:
      na = a + da
      if na >= d:
        print(score + 1)
        return True
      ne = e + de
      if ne > 100:
        ne = 100
      
      if (na, ne) not in visited:
        visited[(na, ne)] = True
        heappush(que, (score + 1, na, ne))
  
  print("NA")
  return False

def main():
  while True:
    d, n = map(int, input().split())
    if d == 0:
      break
    item_lst = [[] for _ in range(101)]
    for _ in range(n):
      a, e, r = map(int, input().split())
      for i in range(r, 101):
        item_lst[i].append((a, e))
    search(item_lst, d)
main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def main():
    while 1:
        D, N = map(int, readline().split())
        if D == N == 0:
            break
        P = [list(map(int, readline().split())) for i in range(N)]
        P.sort(key=lambda x: x[2])
        INF = 10**9

        memo = [[INF]*101 for i in range(D+1)]
        memo[D][0] = 0
        for i in range(D, 0, -1):
            P0 = [(max(i-a, 0), e, r) for a, e, r in P]
            for j, v in ((j, e+1) for j, e in enumerate(memo[i]) if e < INF):
                for A0, e, r in P0:
                    if j < r:
                        break
                    E0 = min(j+e, 100)
                    if v < memo[A0][E0]:
                        memo[A0][E0] = v
        res = min(memo[0])
        if res == INF:
            write("NA\n")
        else:
            write("%d\n" % res)
main()