題目描述
小鲍比喜歡巧克力,他口袋放著N元的錢去商店買巧克力。每個巧克力的購買金額是C元,這個商店還有另外提供一個折扣,那就是從這個商店每拿到M個巧克力,都可以再免費獲得一個巧克力。小鲍比可以拿到多少個巧克力來吃?
原題網址
輸入格式
第一行輸入一個整數T,表示測試資料的數量,範圍在1到1000之間(包含1和1000)。
接下來的T行,每行有三個整數,N、C、和M。N的範圍在2到105之間(包含2和105),C的範圍在1到N之間(包含1和N),M的範圍在2到N之間(包含2和N)。
輸出格式
各別計算每組測試資料,輸出小鲍比能吃到多少個巧克力。
範例輸入
10 2 5
12 4 4
6 2 2
範例輸出
3
5
額外解釋
第1組測試資料中,小鲍比可以用他的10元買到5個巧克力,當他獲得第5個巧克力的時候他還可以免費再拿到1個,所以他總共可以拿到6個巧克力。
第2組測試資料中,小鲍比可以用他的12元買到3個巧克力。
第3組測試資料中,小鲍比可以用他的6元買到3個巧克力。當他獲得第2個巧克力的時候他還可以免費再拿到1個,當他又再獲得一個巧克力的時候他又可以免費再拿到1個,所以他總共可以拿到5個巧克力。
解題概念
如果用一般買一送一、買二送一、買三送一的概念來想,假設巧克力是買三送一,若買了N個,則N/3的整數部份及為贈送的巧克力數量。
但由於在這個題目中,免費獲得的巧克力數量也可以再計入免費巧克力的獲得條件中,因此需要別的方式來計算免費巧克力的數量。
一開始一樣先算出小鮑比可以用錢買到的巧克力的數量,即為N/C的整數部份,用F0來表示。接著計算F0/M的整數部份,即為一開始免費獲得巧克力的數量,用F1來表示。再計算F1加上F0/M的餘數再除以M的整數部份,即為接下來可以免費獲得巧克力的數量,用F2來表示。再計算F2加上F1/M的餘數再除以M的整數部份,即為接下來可以免費獲得巧克力的數量,用F3來表示......一直這樣重複計算,直到Fi為0(i>0),就可以算出所有免費獲得的巧克力數量。
參考答案
import java.util.Scanner;
public class Solution {
public static void main(final String[] args) throws Exception {
final Scanner sc = new Scanner(System.in);
int testCase = sc.nextInt();
while (testCase-- > 0) {
final int n = sc.nextInt();
final int c = sc.nextInt();
final int m = sc.nextInt();
int getNum = n / c;
int totalNum = getNum;
while (true) {
final int freeNum = getNum / m;
if (freeNum == 0) {
break;
}
totalNum += freeNum;
getNum = getNum % m + freeNum;
}
System.out.println(totalNum);
}
}
}