2013-03-16 19:06:52Morris
[ZJ][Greedy] a646. 小民買糖果
內容 ：
某天某糖果店舉辦活動：集滿 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;
}
/********************************************************/
/* 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;
}