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


題目描述

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

原題網址

https://www.hackerrank.com/challenges/chocolate-feast

輸入格式

第一行輸入一個整數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),就可以算出所有免費獲得的巧克力數量。

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章