題目描述

小鲍比喜歡巧克力,他口袋放著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)。

輸出格式

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

範例輸入

3
10 2 5
12 4 4
6 2 2

範例輸出

6
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);
        }
    }
}