V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个专门讨论 idea 的地方。

每个人的时间，资源是有限的，有的时候你或许能够想到很多 idea，但是由于现实的限制，却并不是所有的 idea 都能够成为现实。

那这个时候，不妨可以把那些 idea 分享出来，启发别人。

这是一个创建于 1628 天前的主题，其中的信息可能已经有所发展或是发生改变。

问题

会员卡每次只能充值 6000 商家项目有： 2880 （每次） 2380 （每次） 目前会员卡余额为 1720 请问要如何充值、如何消费才能把会员卡余额变为 0 ？

问题来源于生活，纯属娱乐，开拓思维

会员卡

充值

余额

Cmd

10 条回复 • 2020-06-18 21:16:38 +08:00

linhuoqi

2020-06-16 14:29:35 +08:00

1720 + x * 6000 == y * 2880 + z * 2380
是想找到最小的 x 吧

miyazaki

2020-06-16 14:48:11 +08:00

@linhuoqi
是的呀

winmer

2020-06-16 15:09:37 +08:00

假设第一种消费 x 次第二种消费 y 次充值 n 次
有 6000n=2880x+2380y-1720 (x>-1 y>-1 n>1 x,y,n 为整数)
化简得 300n=144x+119y-860(x>-1 y>-1 n>1 x,y,n 为整数)
取 x=0 则问题转化为求解 y 使得 119y-860 能够整除 300 y 为整数
令 k=119y-860 若 k 满足 k=300n 则 k 个位为 0 乘 9 得 0 的整数只有 0 所以 y 个位为 0
k 十位也为 0 则 y 的十位上数字与 9 的乘积是 6 y 的十位为 4
令 y=40 时 k=119*40-860=3900 已经满足是 300 倍数的条件接下来考虑 y 取更大值的可能
y=m*100+40 （ m 为非负整数）时需满足 119*m 被 3 整除已知 119 不是 3 的倍数因此 m 是三的倍数
于是当 x=0 时，y 为 300M+40 即可满足上述条件
同理令 y=0 发现无法找到一个整数值 x 使得题目成立，因此 y=0 时 x>0
然后就可以在二维坐标轴上划出一个区域（令 m=x ）在这个区域里随便搜搜或者暴力枚举...?

gzfrankie

2020-06-16 15:14:51 +08:00

python 简单写了个 BFS 搜索

import queue

q = queue.Queue()
visited = set()
def f(x,y,z):
return 1720+6000*x-2880*y-2380*z

def enqueueIfNotExist(try_solution):
if try_solution not in visited:
q.put(try_solution)
visited.add(try_solution)

def main():
q.put((0,0,0))
visited.add((0,0,0))
while not q.empty():
try_solution = q.get()
x = try_solution[0]
y = try_solution[1]
z = try_solution[2]
remain = f(x,y,z)
print("x,y,z=",x,",",y,",",z," remain ",remain)
if remain == 0:
return try_solution
elif remain > 0:
try_solution = (x,y+1,z)
enqueueIfNotExist(try_solution)

try_solution = (x,y,z+1)
enqueueIfNotExist(try_solution)
elif remain < 0:
try_solution = (x+1,y,z)
enqueueIfNotExist(try_solution)

if __name__=="__main__":
main()

最后答案是 8，9，10，即 1720+6000*8-2880*9-2380*10=0

gzfrankie

2020-06-16 15:22:44 +08:00