[HackerRank]巧克力盛宴(Chocolate Feast)

題目描述

小鲍比喜歡巧克力，他口袋放著N元的錢去商店買巧克力。每個巧克力的購買金額是C元，這個商店還有另外提供一個折扣，那就是從這個商店每拿到M個巧克力，都可以再免費獲得一個巧克力。小鲍比可以拿到多少個巧克力來吃？

原題網址

輸入格式

第一行輸入一個整數T，表示測試資料的數量，範圍在1到1000之間(包含1和1000)。

接下來的T行，每行有三個整數，N、C、和M。N的範圍在2到10⁵之間(包含2和10⁵)，C的範圍在1到N之間(包含1和N)，M的範圍在2到N之間(包含2和N)。

輸出格式

各別計算每組測試資料，輸出小鲍比能吃到多少個巧克力。

範例輸入

範例輸出

額外解釋

第1組測試資料中，小鲍比可以用他的10元買到5個巧克力，當他獲得第5個巧克力的時候他還可以免費再拿到1個，所以他總共可以拿到6個巧克力。

第2組測試資料中，小鲍比可以用他的12元買到3個巧克力。

第3組測試資料中，小鲍比可以用他的6元買到3個巧克力。當他獲得第2個巧克力的時候他還可以免費再拿到1個，當他又再獲得一個巧克力的時候他又可以免費再拿到1個，所以他總共可以拿到5個巧克力。

解題概念

如果用一般買一送一、買二送一、買三送一的概念來想，假設巧克力是買三送一，若買了N個，則N/3的整數部份及為贈送的巧克力數量。

但由於在這個題目中，免費獲得的巧克力數量也可以再計入免費巧克力的獲得條件中，因此需要別的方式來計算免費巧克力的數量。

一開始一樣先算出小鮑比可以用錢買到的巧克力的數量，即為N/C的整數部份，用F₀來表示。接著計算F₀/M的整數部份，即為一開始免費獲得巧克力的數量，用F₁來表示。再計算F₁加上F₀/M的餘數再除以M的整數部份，即為接下來可以免費獲得巧克力的數量，用F₂來表示。再計算F₂加上F₁/M的餘數再除以M的整數部份，即為接下來可以免費獲得巧克力的數量，用F₃來表示......一直這樣重複計算，直到F_i為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);
        }
    }
}