題目連結:
題目大意:
給定一部分以下之程式碼:
printf("These knockoff Flags cost 900 each, enter desired quantity\n");
int account_balance = 1100;
int number_flags = 0;
scanf("%d", &number_flags);
if(number_flags > 0){
int total_cost = 0;
total_cost = 900*number_flags;
printf("\nThe final cost is: %d\n", total_cost);
if(total_cost <= account_balance){
account_balance = account_balance - total_cost;
printf("\nYour current balance after transaction: %d\n\n", account_balance);
}
else{
printf("Not enough funds to complete purchase\n");
}
}
請輸出任意一個 number_flags 之值,其可使 account_balance 之值大於等於 100000。
範例輸入:
(無)
範例輸出:
(無)
解題思維:
可以看到題目給定的程式有檢查 number_flags 是否為正整數。所以我們不能藉由輸入負的 number_flags 來付負的金額(也就是賺得正的金額)。
但是「付負的金額」這個想法是可行的,因為給定的程式沒有檢查 total_cost 是否大於 0。只是我們不能藉由上面的方式來達成。不過我們可以藉由溢位(Overflow)來將 total_cost 之值變成負的:
可以看到 total_cost 來自於 900*number_flags。而 total_cost 的型態為 32 位元有號整數(int),因此其正值上界為 2 ^ 31 - 1(即 2,147,483,647,這邊用逗點「,」來方便判別數字位數長,但是本題答案不能包含逗點)。
當 number_flags 之值為 2,386,092 時,total_cost 之值將會是 2,147,482,800,非常接近上限。當 number_flags = 2,386,093 時,total_cost 理應為 2,147,483,700,但是其超出了 int 之上限將會溢位成 -2,147,483,595(此值恰好與下界 -2 ^ 31 = -2,147,483,648 之差 53,該差值為理論值與上界之差)。不過因為現在 account_balance 初始值為 1100,所以更新後的 account_balance 理應為 2,147,484,695,此值超出了整數上界所以又會溢位回負數。
不過我們將 number_flags 設為 2,386,095 時,最後的 account_balance 之值是 2,147,482,895。此值有在 int 範圍中且也遠大於題目要求的 100,000。所以「2386095 」是一組符合題目要求的輸出。
而當然這不代表所有大於或等於 2,386,095 之值都是可行的,因為 total_cost 會隨著 number_flags 之值變大而變大,但是會因為溢位而變為負數然後再從負數變大回到正數並循環此過程。
因此像是 2400000 是可行的(這邊就不細算了)、4800000 「不」可行、4772075 可行 、2147483500 也可行等等諸多可能的答案以及錯誤輸出值,族繁不及備載。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。