24h購物| | PChome| 登入
2011-10-29 07:03:56| 人氣618| 回應0 | 上一篇 | 下一篇

a279. 分糖果囉

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

a279. 分糖果囉

內容 :

來分糖果吧!
你一開始有 n 顆糖果,想要公平的分給 m 個人
不幸的是,n 未必可以恰好被 m 整除
幸運的是,你有兩台神奇的機器以及 e 的能量,每次操作要消耗一單位的能量
若當前有 x 顆糖果,則兩台機器分別可以將糖果數變成 4x+3 以及 8x+7 顆糖果
給你 n, m, e ,請問你至少要消耗多少能量才可以平分糖果呢?

輸入說明 :

多組輸入,以EOF作為結束
每組輸入為一有三個整數n,m,e
0<=n<=20111021
1<=m<=20111021
0<=e<=314159

輸出說明 :

對於每組輸入輸出一行,包含一個整數代表最小能量消耗
如果把所有能量用完都沒辦法平分請輸出 -1

範例輸入 :

5 5 0
1 2 514
1 9 3

範例輸出 :

0
-1
2

提示 :

第一組範例:不需要動用機器就可以平分
第二組範例:消耗所有能量依然無法公平分給兩個人
第三組範例:1 => 4*1+3=7 => 8*7+7=63,63顆糖果可以公平分給9個人

出處 :

(管理:VacationClub)



作法 : 數學
你會發現,從 n 出發的話,
所有可能是 4x+3 8x+7 16x+15 32x+31 64x+63 ... 2^i x+2^i-1
然而最少次數是這樣子排的
1次 : 4 8
2次 : 16 32 64
3次 : 128 256 512
4次 : 1024 2048 4096 ...
除了 1 次以外,都是3個一循環

/**********************************************************************************/
/*  Problem: a279 "分糖果囉" from                                             */
/*  Language: C (425 Bytes)                                                       */
/*  Result: AC(108ms, 300KB) judge by this@ZeroJudge                              */
/*  Author: morris1028 at 2011-10-28 20:23:32                                     */
/**********************************************************************************/


#include<stdio.h>
int main() {
    int n, m, e, tmp;
    int i, j;
    while(scanf("%d %d %d", &n, &m, &e) == 3) {
        if(n%m == 0) {puts("0");continue;}
        int t2 = 4;
        for(i = 1; i <= e; i++) {
            for(j = 1; j <= 3; j++) {
                if(i == 1 && j == 1)    continue;
                t2 %= m;
                tmp = (t2*(n+1)-1)%m;
                t2 *= 2;
                if(!tmp)    break;
            }
            if(j != 4)    break;
        }
        printf("%d\n", i == e+1 ? -1 : i);
    }
    return 0;
}

台長: Morris
人氣(618) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:a280. 小朋友上樓梯
此分類上一篇:a276. 又分糖果囉

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文