Problem:


会津地鶏

2008 年 4 月に、会津若松市は長さ20 m 85 cm のやきとり作りに挑戦して成功しました。このとき使われた鶏肉が、会津特産の会津地鶏です。会津地鶏はとてもおいしいのですが、飼育がむずかしいので生産量が少なく、値段が高いのが難点です。

今日は一郎君の家に、遠くから親戚が遊びに来ます。お母さんは鶏肉の水炊きを作って親戚をもてなすことにしました。近くのお肉屋さんでは会津地鶏とふつうの鶏肉の 2 種類の鶏肉を売っています。お母さんは、以下のような指示を一郎君に与えて、お肉屋さんに行って鶏肉を買ってくるように
頼みました。

鶏肉が足りなくなると困るので、決められた量以上の鶏肉を買う。

予算の許す範囲で会津地鶏をできるだけ多く買う(会津地鶏は必ず買うこと)。

会津地鶏を買った残りでふつうの鶏肉をできるだけ多く買う(予算が足りなければ買わない)。

一郎君がお肉屋さんに行くと、会津地鶏が品薄のため一人が買える量を制限していました。一郎君が、お母さんから与えられたすべての指示を守って買い物をするとき、一郎君が買う会津地鶏と普通の鶏肉の量はそれぞれ何グラムになるでしょう?

買うべき鶏肉の量の下限 q1、予算 b、このお肉屋さんでの会津地鶏 100 グラムの値段 c1、ふつうの鶏肉 100 グラムの値段 c2、会津地鶏を一人が買える量の上限 q2  を入力とし、一郎君が買う会津地鶏とふつうの鶏肉の量を 100 グラム単位で出力するプログラムを作成してください。ただし、このお肉屋さんではお母さんの指示通りに買えない場合には、「NA」と出力してください。

Input

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

q1 b c1 c2 q2

鶏肉の量を表すデータ q1 と q2 は100 グラム単位で指定されます。また、b、c1、c2、q1、q2 は 1 以上 1,000,000 以下の整数とします。

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

Output

データセット毎に、一郎君が購入する会津地鶏の量とふつうの鶏肉の量(半角空白区切り) または「NA」を１行に出力します。

Sample Input

48 9297 240 126 32
20 3010 157 141 7
30 117002 5680 962 15
8 1673 1712 190 22
64 8478 87 54 307
23 5477 117 92 12
50 7558 1396 187 17
279 88677 4522 514 14
0

Output for the Sample Input

28 20
7 13
15 33
NA
97 0
12 44
NA
NA



Sample input:
48 9297 240 126 32
20 3010 157 141 7
30 117002 5680 962 15
8 1673 1712 190 22
64 8478 87 54 307
23 5477 117 92 12
50 7558 1396 187 17
279 88677 4522 514 14
0


Sample output:
28 20
7 13
15 33
NA
97 0
12 44
NA
NA

Submission status: Wrong Answer

Solution code:
# Aizu Problem 0186: Aizu Chicken
#
import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def aizu_chicken(q1, b, c1, c2, q2):
    for i in range(q2, 0, -1):
        cj = i * c1
        normal = int((b - cj) / c2)
        if i + normal < q1:
            continue
        elif normal >= 0:
            print(i, normal)
            break
    else:
        print("NA")


while True:
    inp = [int(_) for _ in input().split()]
    if len(inp) == 1:
        break
    q1, b, c1, c2, q2 = inp[:]
    aizu_chicken(q1, b, c1, c2, q2)

Submission status: Wrong Answer

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

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


def Cond(q1, b, mid, c1, c2):
    b -= (c1 * mid)
    if b < 0:
        return False
    b -= (c2 * (q1 - mid))
    if b < 0:
        return False
    return True


def solve(q1, b, c1, c2, q2):
    if c2 * q1 > b:
        return False, 0, 0

    ub = q2
    lb = 1
    max_aizu = 0

    while (ub - lb) > 1:
        mid = (ub + lb) // 2
        if Cond(q1, b, mid, c1, c2):
            lb = mid
            max_aizu = mid
        else:
            ub = mid

    if Cond(q1, b, ub, c1, c2):
        max_aizu = ub

    b -= (max_aizu * c1)
    normal_chicken = b // c2
    if normal_chicken < 0 or max_aizu == 0:
        return False, 0, 0
    else:
        return True, max_aizu, normal_chicken


def main(args):
    while True:
        txt = input().strip()
        if txt[0] == '0':
            break

        q1, b, c1, c2, q2 = map(int, txt.split())
        result, aizu, normal = solve(q1, b, c1, c2, q2)
        if result is False:
            print('NA')
        else:
            print(aizu, normal)


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

Submission status: Wrong Answer

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

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


def Cond(q1, b, mid, c1, c2):
    b -= (c1 * mid)
    if b < 0:
        return False
    b -= (c2 * (q1 - mid))
    if b < 0:
        return False
    return True


def solve(q1, b, c1, c2, q2):
    ub = q2
    lb = 1
    aizu_chicken = 0

    while (ub - lb) > 1:
        mid = (ub + lb) // 2
        if Cond(q1, b, mid, c1, c2):
            lb = mid
            aizu_chicken = max(aizu_chicken, mid)
        else:
            ub = mid

    if Cond(q1, b, ub, c1, c2):
        aizu_chicken = max(aizu_chicken, ub)

    b -= (aizu_chicken * c1)
    normal_chicken = b // c2
    if normal_chicken < 0 or aizu_chicken == 0:
        return False, 0, 0
    else:
        return True, aizu_chicken, normal_chicken


def main(args):
    while True:
        txt = input().strip()
        if txt[0] == '0':
            break

        q1, b, c1, c2, q2 = map(int, txt.split())
        result, aizu, normal = solve(q1, b, c1, c2, q2)
        if result is False:
            print('NA')
        else:
            print(aizu, normal)


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

Submission status: Wrong Answer

Solution code:
while True:
    N = input()
    if N == "0":
        break

    q1,b,c1,c2,q2 = [int(i) for i in N.split()]

    if c1 == c2:
        x = min(q2, b // c1)
    else:
        x = min((b-c2*q1) // (c1-c2), q2, b // c1)
    y = (b-c1*x) // c2

    if x <= 0:
        print("NA")
    else:
        print(x,y)

Submission status: Wrong Answer

Solution code:
def check(mid, b, c1, c2, q1):
  if mid + (b - mid * c1) // c2 < q1:
    return False
  return True

while True:
  s = input()
  if s == "0":
    break
  q1, b, c1, c2, q2 = map(int, s.split())
  max_aizu = min(b // c1, q2)
  if max_aizu <= 0:
    print("NA")
    continue
  if c2 >= c1:
    if max_aizu >= q1:
      print(max_aizu, 0)
    else:
      print("NA")
    continue
  
  left = 0
  right = max_aizu + 1
  while right - left > 1:
    mid = (left + right) // 2
    if check(mid, b, c1, c2, q1):
      left = mid
    else:
      right = mid
  
  if (b - left * c1) // c2 + left < q1:
    print("NA")
  else:
    print(left, (b - left * c1) // c2)

Submission status: Wrong Answer

Solution code:
def check(mid, b, c1, c2, q1):
  if mid + (b - mid * c1) // c2 < q1:
    return False
  return True

while True:
  s = input()
  if s == "0":
    break
  q1, b, c1, c2, q2 = map(int, s.split())
  max_aizu = min(b // c1, q2)
  if max_aizu <= 0:
    print("NA")
    continue
  if c2 >= c1:
    if max_aizu >= q1:
      print(max_aizu, (b - max_aizu * c1) // c2)
    else:
      print("NA")
    continue
  
  left = 0
  right = max_aizu + 1
  while right - left > 1:
    mid = (left + right) // 2
    if check(mid, b, c1, c2, q1):
      left = mid
    else:
      right = mid
  
  if (b - left * c1) // c2 + left < q1:
    print("NA")
  else:
    print(left, (b - left * c1) // c2)

Submission status: Wrong Answer

Solution code:
def check(mid, b, c1, c2, q1):
  if mid + (b - mid * c1) // c2 < q1:
    return False
  return True

while True:
  s = input()
  if s == "0":
    break
  
  q1, b, c1, c2, q2 = map(int, s.split())
  max_aizu = min(b // c1, q2)
  
  if max_aizu <= 0:
    print("NA")
    continue
  
  if c2 >= c1:
    max_normal = (b - max_aizu * c1) // c2
    if max_aizu + max_normal < q1:
      print("NA")
    else:
      print(max_aizu, max_normal)
    continue

  left = 0
  right = max_aizu + 1
  while right - left > 1:
    mid = (left + right) // 2
    if check(mid, b, c1, c2, q1):
      left = mid
    else:
      right = mid
  
  if (b - left * c1) // c2 + left < q1:
    print("NA")
  else:
    print(left, (b - left * c1) // c2)

Submission status: Wrong Answer

Solution code:
while True:
    try:
        q1,b,c1,c2,q2 = map(int,raw_input().split())
    except ValueError:
        break
    f = lambda x:(b-c1*x)/c2
    if f(q2)+q2 >= q1:
        print q2,f(q2)
    else:
        left,right = 0,q2
        while left < right:
            mid = (right+left)/2
            if f(mid)+mid > q1 and f(mid) > 0:
                left = mid + 1
            else:
                right = mid                
        if left == 0 or left+f(left) < q1:
            print "NA"
        else:
            print left,f(left)

Submission status: Wrong Answer

Solution code:
while 1:
	inp = raw_input()
	if inp == "0": break
	q1,b,c1,c2,q2 = map(int,inp.split())
	if (b - c1) / c2 < q1 - 1:
		print "NA"
		continue
	buy1 = min(b/c1,q2)
	buy2 = (b - buy1 * c1) / c2
	print buy1, buy2

Submission status: Wrong Answer

Solution code:
while 1:
	inp = raw_input()
	if inp == "0": break
	q1,b,c1,c2,q2 = map(int,inp.split())
	buy1 = min(b / c1,q2)
	buy2 = (b - buy1 * c1) / c2
	while buy1 * c1 + buy2 * c2 > b or buy1 + buy2 <q1:
		buy1 -= 1
		buy2 = (b - buy1 * c1) / c2
		if buy1 == 0:
			print "NA"
			break
	else:
		print buy1, buy2

Submission status: Time Limit Exceeded

Solution code:
while 1:
	inp = raw_input()
	if inp == "0": break
	q1,b,c1,c2,q2 = map(int,inp.split())
	buy1 = min(b/c1,q2)
	buy2 = (b - buy1 * c1) / c2
	while buy1 * c1 + buy2 * c2 > b or buy1 + buy2 <q1:
		buy1 -= 1
		buy2 = (b - buy1 * c1) / c2
	if buy1 > 0:
		print buy1, buy2
	else:
		print "NA"

Submission status: Time Limit Exceeded

Solution code:
while 1:
	inp = raw_input()
	if inp == "0": break
	q1,b,c1,c2,q2 = map(int,inp.split())
	buy1 = min(b / c1,q2)
	buy2 = (b - buy1 * c1) / c2
	while buy1 * c1 + buy2 * c2 > b or buy1 + buy2 <q1:
		buy1 -= 1
		buy2 = (b - buy1 * c1) / c2
		if buy1 == 0:
			print "NA"
	else:
		print buy1, buy2

Submission status: Accepted

Solution code:
while(1):
    indata=raw_input().split()
    if indata==["0"]:
        break
    else:
        [q1,b,c1,c2,q2]=[int(x) for x in indata]
        #try to buy jidori
        jideal=b/c1
        jqmax=min(jideal,q2)
        if jqmax==0:
            print"NA"
        else:
            jq=jqmax
            while jq>0:
                b1=b-jq*c1
                cq=b1/c2
                if (jq+cq)>=q1:
                    print jq,cq
                    break
                else:
                    jq=jq-1
            if jq==0:
                print "NA"

Submission status: Accepted

Solution code:

class Solve:
    def __init__(self):
        tmp = [int(i) for i in input().split()]
        if len(tmp) == 1:
            self.cal = False
        else:
            self.cal = True
            q1, b, c1, c2, q2 = tmp

            self.B = b
            self.C = (c1, c2)
            self.Q = (q1, q2)

            self.a = 0  # >= 0; True;
            self.b = min(self.Q[1]+1, self.B//self.C[0]+1)  # <= 10**6+1; False

    def check(self, A):
        b = self.B
        b -= self.C[0] * A  # self.b(??????)?????????????´\?¶????100A[g]????????\??¶?????????????????????
        b -= self.C[1] * max(0, self.Q[0]-A)
        if b >= 0:
            return True
        else:
            return False

    def solve(self):
        while self.b - self.a > 1:
            m = (self.a + self.b) // 2
            if self.check(m):
                self.a = m
            else:
                self.b = m
        return self.buy(self.a)

    def buy(self, A):
        if A == 0:
            return ['NA']
        else:
            return [str(A), str((self.B-self.C[0]*A)//self.C[1])]

while True:
    s = Solve()
    if not s.cal:
        break

    print(" ".join(s.solve()))

Submission status: Accepted

Solution code:
# Aizu Problem 0186: Aizu Chicken
#
import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def aizu_chicken(q1, b, c1, c2, q2):
    for i in range(q2, 0, -1):
        cj = i * c1
        normal = int((b - cj) // c2)
        if i + normal < q1:
            continue
        elif normal >= 0:
            print(i, normal)
            break
    else:
        print("NA")


while True:
    inp = [int(_) for _ in input().split()]
    if len(inp) == 1:
        break
    q1, b, c1, c2, q2 = inp[:]
    aizu_chicken(q1, b, c1, c2, q2)

Submission status: Accepted

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

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


def Cond(q1, b, mid, c1, c2):
    b -= (c1 * mid)
    if b < 0:
        return False
    b -= (c2 * (q1 - mid))
    if b < 0:
        return False
    return True


def solve(q1, b, c1, c2, q2):
    ub = q2
    lb = 1
    aizu_chicken = 0

    while (ub - lb) > 1:
        mid = (ub + lb) // 2
        if Cond(q1, b, mid, c1, c2):
            lb = mid
            aizu_chicken = max(aizu_chicken, mid)
        else:
            ub = mid

    if Cond(q1, b, lb, c1, c2):
        aizu_chicken = max(aizu_chicken, lb)
    if Cond(q1, b, ub, c1, c2):
        aizu_chicken = max(aizu_chicken, ub)

    b -= (aizu_chicken * c1)
    normal_chicken = b // c2
    if normal_chicken < 0 or aizu_chicken == 0:
        return False, 0, 0
    else:
        return True, aizu_chicken, normal_chicken


def main(args):
    while True:
        txt = input().strip()
        if txt[0] == '0':
            break

        q1, b, c1, c2, q2 = map(int, txt.split())
        result, aizu, normal = solve(q1, b, c1, c2, q2)
        if result is False:
            print('NA')
        else:
            print(aizu, normal)


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

Submission status: Accepted

Solution code:
def binary_search(quantity, budget, aizu_chicken_price, chicken_price, aizu_chicken_limit):
    if budget < (quantity - 1) * chicken_price + aizu_chicken_price:
        return None

    if aizu_chicken_price * quantity <= budget:
        aizu_chicken_count = budget // aizu_chicken_price

        if aizu_chicken_limit < aizu_chicken_count:
            aizu_chicken_count = aizu_chicken_limit

        rest = budget - aizu_chicken_price * aizu_chicken_count
        chicken_count = rest // chicken_price
        return aizu_chicken_count, chicken_count

    if aizu_chicken_price * aizu_chicken_limit + chicken_price * (quantity - aizu_chicken_limit) < budget:
        rest = budget - aizu_chicken_price * aizu_chicken_limit
        chicken_count = rest // chicken_price
        return aizu_chicken_limit, chicken_count

    # 二分探索
    aizu_chicken_count = aizu_chicken_limit // 2
    chicken_count = quantity - aizu_chicken_count
    update_count = aizu_chicken_count // 2 + 1

    max_pair = (0, quantity)

    while 0 < update_count:

        if aizu_chicken_count * aizu_chicken_price + chicken_count * chicken_price <= budget:
            max_pair = (aizu_chicken_count, chicken_count)
            aizu_chicken_count += update_count + 1
            chicken_count -= (update_count + 1)

        else:
            aizu_chicken_count -= (update_count + 1)
            chicken_count += update_count + 1

        update_count //= 2

    return max_pair


while True:

    input_data = input()

    if input_data == "0":
        break

    quantity, budget, aizu_chicken_price, chicken_price, aizu_chicken_limit = [int(item) for item in
                                                                               input_data.split(" ")]

    result = binary_search(quantity, budget, aizu_chicken_price, chicken_price, aizu_chicken_limit)

    if result is not None:
        print(result[0], result[1])
    else:
        print("NA")

Submission status: Accepted

Solution code:
while True:
    N = input()
    if N == "0":
        break

    q1,b,c1,c2,q2 = [int(i) for i in N.split()]

    if c1 <= c2:
        x = min(q2, b // c1)
    else:
        x = min((b-c2*q1) // (c1-c2), q2, b // c1)
    y = (b-c1*x) // c2

    if x <= 0 or x + y < q1:
        print("NA")
    else:
        print(x,y)

Submission status: Accepted

Solution code:
def check(mid, b, c1, c2, q1):
  if mid + (b - mid * c1) // c2 < q1:
    return False
  return True

while True:
  s = input()
  if s == "0":
    break
  
  q1, b, c1, c2, q2 = map(int, s.split())
  max_aizu = min(b // c1, q2)
  
  if max_aizu <= 0:
    print("NA")
    continue
  
  if c2 >= c1:
    max_normal = (b - max_aizu * c1) // c2
    if max_aizu + max_normal < q1:
      print("NA")
    else:
      print(max_aizu, max_normal)
    continue
  
  if (b - c1) // c2 + 1 < q1:
    print("NA")
    continue

  left = 0
  right = max_aizu + 1
  while right - left > 1:
    mid = (left + right) // 2
    if check(mid, b, c1, c2, q1):
      left = mid
    else:
      right = mid
  
  print(left, (b - left * c1) // c2)

Submission status: Accepted

Solution code:
while True:
    L=map(int,raw_input().split())
    if L==[0]:break
    q1,b,c1,c2,q2=L
    for i in range(q2,0,-1):
        cj=i*c1
        normal=int((b-cj)/c2)
        if i+normal<q1:
            continue
        elif normal>=0:
            print i,normal
            break
    else:
        print "NA"

Submission status: Accepted

Solution code:
#coding: utf-8
def solve():
    for ac in xrange(q2, 0, -1):
        nc = (b - c1 * ac) / c2
        if nc >= 0 and nc + ac >= q1:
            return "{} {}".format(ac, nc)
    return "NA"
    
while True:
    data = raw_input().strip()
    if data == "0":
        break
    q1, b, c1, c2, q2 = map(int, data.split())
    print solve()

Submission status: Accepted

Solution code:
while 1:
	inp = raw_input()
	if inp == "0": break
	q1,b,c1,c2,q2 = map(int,inp.split())
	buy1 = min(b/c1,q2)
	buy2 = (b - buy1 * c1) / c2
	while buy1 * c1 + buy2 * c2 > b or buy1 + buy2 <q1:
		buy1 -= 1
		buy2 = (b - buy1 * c1) / c2
		if buy1 == 0:
			break
	if buy1 > 0:
		print buy1, buy2
	else:
		print "NA"

Submission status: Accepted

Solution code:
while 1:
	inp = raw_input()
	if inp == "0": break
	q1,b,c1,c2,q2 = map(int,inp.split())
	buy1 = min(b/c1,q2)
	buy2 = (b - buy1 * c1) / c2
	while buy1 > 0  and (buy1 * c1 + buy2 * c2 > b or buy1 + buy2 < q1):
		buy1 -= 1
		buy2 = (b - buy1 * c1) / c2
	if buy1 > 0:
		print buy1, buy2
	else:
		print "NA"

Submission status: Accepted

Solution code:
while 1:
	inp = raw_input()
	if inp == "0": break
	q1,b,c1,c2,q2 = map(int,inp.split())
	a1 = min(b/c1, q2)
	a2 = (b - a1*c1)/c2
	while a1 > 0  and (a1*c1 + a2*c2 > b or a1 + a2 < q1):
		a1 -= 1
		a2 = (b - a1*c1)/c2
	print "%d %d"%(a1,a2) if a1 > 0 else "NA"

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    ipt = readline()
    if ipt == "0\n":
        return False
    q1, b, c1, c2, q2 = map(int, ipt.split())
    for p1 in range(q2, 0, -1):
        b1 = b - p1*c1
        if b1 < 0:
            continue
        p2 = b1 // c2
        if p1 + p2 >= q1:
            write("%d %d\n" % (p1, p2))
            break
    else:
        write("NA\n")
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


while True:
    input_str = input()
    if len(input_str) == 1 and input_str[0] == "0":
        break

    need,budget,aizu,normal,limit = map(int,input_str.split())

    left = 1;right = limit
    mid = (left+right)//2
    num_aizu = 0;num_normal = 0

    while left <= right:
        rest = budget-mid*aizu
        tmp_normal = rest//normal
        if rest >= 0 and mid+tmp_normal >= need:
            num_aizu = mid
            num_normal = tmp_normal
            left = mid+1
        else:
            right = mid-1
        mid = (left+right)//2

    if num_aizu == 0:
        print("NA")
    else:
        print("%d %d"%(num_aizu,num_normal))

Submission status: Accepted

Solution code:
while True:
    n = input()
    if n == '0': break
    q1, b, c1, c2, q2 = map(int, n.split())
    for i in range(q2, 0, -1):
        c = i * c1
        x = (b-c)//c2
        if i+x < q1:
            continue
        elif x >= 0:
            print(i, x)
            break
    else:
        print('NA')

Submission status: Runtime Error

Solution code:
while True:
    N = input()
    if N == "0":
        break

    q1,b,c1,c2,q2 = [int(i) for i in N.split()]

    x = min((b-c2*q1) // (c1-c2), q2, b // c1)
    y = (b-c1*x) // c2

    if x <= 0:
        print("NA")
    else:
        print(x,y)