推 hikaru4:INTMAX可以換成D嗎?還有後面的break if是確保程式沒亂跑嗎 10/24 09:38
推 greenoyster:換成 D 是好方法. :) break 只是想省時間 10/24 11:43
→ greenoyster:找到一組答案後就不再找下去了而已 10/24 11:43
以下提供另外一個想法
#include <stdio.h>
#define INTMAX 2147483647
int min(int a, int b){ return (a<b) ? a : b;}
int main()
{
int D, a, b, c, A, B, C;
int ncase;
int i, j, k, ba, bb, bc, find;
for( scanf("%d", &ncase); ncase>0; --ncase){
scanf("%d%d%d%d%d%d%d", &D, &a, &b, &c, &A, &B, &C);
find = 0;
ba = A>0 ? min(INTMAX/A, a) : a;
for(i=0; i<=ba; ++i){
bb = B>0 ? min((INTMAX-i*A) / B, b) : b;
for(j=0; j<=bb; ++j){
bc = C>0 ? min((INTMAX-i*A-j*B) / C, c) : c;
for(k=0; k<=bc; ++k){
if(i*A + j*B + k*C == D){
find = 1;
break;
}
}
if(find == 1)
break;
}
if(find == 1)
break;
}
printf(find ? "yes\n" : "no\n");
}
return 0;
}
chhsiao 助教提供的版本是一個一個數字往上加 再檢查有沒有加到溢位
這個版本之中則是直接先求出最多 A B C 可放幾個而不溢位 事先避免溢位發生
其中 ba bb bc 指的就是 A B C 使用個數的上限
INTMAX 定義的是 int 的上界
所以 INTMAX/A 即為最多可以放幾個 A 而不溢位 (注意這裡是整數除法！)
(INTMAX-i*A)/B 即為放了 i 個 A 之後 還能放幾個 B 而不溢位
(INTMAX-i*A-j*B)/C 即為放了 i 個 A 和 j 個 B 之後 還能放幾個 C 而不溢位
其中用到的三元運算子 ?: 在助教課的時候有說 是一種很像 if 的運算子
(cond) ? (expr1) : (expr2) ;
的意思是指
(cond) 成立的時候回傳 expr1
否則回傳 expr2
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.53