2011-10-29 07:03:56Morris
a279. 分糖果囉
a279. 分糖果囉
/**********************************************************************************/
/* 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;
}
內容 ：
來分糖果吧！
你一開始有 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個一循環
作法 : 數學
你會發現，從 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;
}
上一篇：a276. 又分糖果囉
下一篇：a280. 小朋友上樓梯