[ZJ][Greedy] a646. 小民買糖果＠Morris' Blog

2013-03-16 19:06:52| 人氣720| 回應0 | 上一篇 | 下一篇

[ZJ][Greedy] a646. 小民買糖果

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

某天某糖果店舉辦活動：集滿 n 張糖果包裝紙即可再多得一顆糖果。而 n 卻是由顧客由抽獎決定，這樣無良的老闆所設計出來的活動實在是讓店員很困擾，不知道該給客人幾顆糖果。希望你們寫個程式幫店員小姐解決這個問題。

原題如上描述

額外補充

然而這已經換成匯率問題，小民每次拿 n 張去兌換時，只能兌換 n * p (無條件捨去取整數) 個糖果，而此時換到的糖果也有包裝紙，又可以再次兌換，問一開始給小民 c 個糖果，根據匯率 p，小民最多能換到幾顆糖果。

輸入說明：

正整數 c 代表顧客買幾顆糖果。

浮點數 p 介於 0 ~ 1，代表一張包裝紙可以換幾顆糖果。

0 < c < 1000, p 至多小數點三位

輸出說明：

顧客最多能獲得幾顆糖果。

範例輸入：

15 0.2
15 0.3

範例輸出：

18
20

提示：

出處：

中央助教 (管理：morris1028)

/********************************************************/
/* Problem: a646 "小民買糖果" from 中央助教               */
/* Language: C (500 Bytes)                             */
/* Result: AC(8ms, 304KB) judge by this@ZeroJudge      */
/* Author: morris1028 at 2013-03-16 18:56:03           */
/********************************************************/

#include <stdio.h>
int a, b, n, i, j;
char s[9];
int sol(int n) {
    int r, mn = 0xffff;
    for(i = n; i >= 1; i--) {
        r = i*a/b;
        if(i*a%b < mn)
            mn = i*a%b, j = i;
    }
    if(mn == 0xffff)
        return 0;
    r = j*a/b;
    return sol(n-j+r) + r;
}
int main() {
    while(scanf("%d %s", &n, &s) == 2) {
        for(i = 2, a = 0, b = 1; s[i]; i++)
            b *= 10, a = a*10 + s[i]-'0';
        printf("%d\n", sol(n)+n);
    }
    return 0;
}

我要檢舉

#小民買糖果#a646#Greedy

台長： Morris

您可能對以下文章有興趣

[ZJ][規律] a568. ISSC 2012- problem B

[ZJ][heap] a605. 交錯和

[ZJ][LCA][online] d767. 血緣關係

a064. SPOJ 4580.ABCDEF

人氣(720) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][塊狀鏈表] a063. SGU 187. Twist and whirl - want to cheat
此分類上一篇:[ZJ][DP] a646. 小民買糖果

回應(0)