0186-Aizu Chicken
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0186&lang=jp
コメントが全て。
線型探索よりも二分探索のほうが良いかもしれない。
それはそうとSKKIMEにも慣れてきた。
もしかしたらATOKが不要になるかも。
//買うべき鶏肉の量の下限 q1、予算 b、このお肉屋さんでの会津地鶏100グラムの値段 c1、ふつう の鶏肉100グラムの値段 c2、会津地鶏を一人が買える量の上限 q2 //x=会津地鶏の購入量(100g単位) y=普通の鶏肉の購入量(100g単位) //q1<=x+y・・・? //q2>=x>0・・・? //c1*x+c2*y<=b・・・? //これらを満たすx,yの中でxが最大になり、さらにyもできる限り大きいものを選ぶ //条件?よりy=[(b-c1*x)/c2]となる //そのためxを定めれば、?、?の成立の確認は瞬時に出来る。 int q1,b,c1,c2,q2; //xに対して?・?・?を満たすの確認。 //戻り値が-1なら満たさない。 //それ以外の場合はyを戻り値とする。 int check(int x){ int y=(b-c1*x)/c2; if(b-c1*x<0) return -1; //y>=0でないとおかしい if(q1>(x+y)) return -1; if(q2<x) return -1; if(y<0) return -1; return y; } int main(){ int x,y; while(1){ scanf("%d",&q1);if(q1==0) return 0; scanf("%d %d %d %d",&b,&c1,&c2,&q2); for(x=q2;x>0;x--){ if((y=check(x))!=-1){ printf("%d %d\n",x,y); } } if(x==0)puts("NA"); } return 0; }