AOJ 0186 - Aizu Chicken

会津鶏肉の量で二分探索する．

#include<iostream>
#include<cstdio>

const int INF = 1 << 24;
int q_chicken, b, p_chicken, p_aizu, q_aizu;

bool C(int x){//x: 買う会津鶏肉の量
	if(x * p_aizu > b || x > q_aizu){//資金超えるか用意された量より多い
		return false;
	}
	return x + (b-x*p_aizu) / p_chicken >= q_chicken;
}

int main(){
	while(std::cin >> q_chicken >> b >> p_aizu >> p_chicken >> q_aizu, !std::cin.eof()){
		int ub = INF, lb = 0;
		for(int i=0;i<100;i++){
			int mid = (lb + ub) / 2;
			if(C(mid))lb = mid;
			else ub = mid;
		}

		if(lb == 0){//会津鶏肉が買えない，残念
			puts("NA");
		}else{
			printf("%d %d\n", lb, (b-lb*p_aizu)/p_chicken);
		}
	}
}