题目描述:
中秋节公司分月饼,m个员工,买了n个月饼,m<=n,每个员工至少分1个月饼,但可以分多个,单人份到最多月饼的个数为Max1,单人分到第二多月饼的个数是Max2,Max1-Max2<=3。
同理,单人分到第n-1多月饼的个数是Max(n-1),单人分到第n多月饼的个数是Max(n),Max(n-1)-Max(n)<=3。
请问有多少种分月饼的方法?
输入描述:
第一行输入m n,表示m个员工,n个月饼,m<=n
输出描述:
输出有多少种月饼分法
示例1:
输入:
2 4
输出:
2
说明:
4 = 1+3 ?和3+1算一种分法
4 = 2+2 ?共两种方案
可以通过递归不断缩小问题规模,将大问题拆分为更小的子问题,并通过递归调用来解决子问题。同时,为了避免重复计算相同的参数组合,使用了装饰器来添加了缓存功能,提高了代码的执行效率。
# -*- coding: utf-8 -*-
'''
@File : 2023-B-分月饼.py
@Time : 2023/12/19 14:02:56
@Author : mgc
@Version : 1.0
@Desc : None
'''
# import os
# import re
# import sys
# import copy
# import math
# import queue
# import functools
# from queue import Queue
# from collections import Counter, defaultdict
import functools
@functools.lru_cache
def calc_count(n, m, last_max):
"""
计算分月饼的方法数
Args:
n (int): 剩余月饼数量
m (int): 剩余员工数量
last_max (int): 上一个员工分到的月饼的最大数量
Returns:
int: 分月饼的方法数
"""
if m == 0 and n == 0:
return 1
if n < 0 or m < 0:
return 0
comb_count = 0
moon_cakes = [last_max + i for i in range(4)]
for mc in moon_cakes:
if mc * m > n:
break
comb_count += calc_count(n - mc, m - 1, mc)
return comb_count
def cal(m, n):
"""
计算分月饼的方法数
Args:
m (int): 员工数量
n (int): 月饼数量
Returns:
int: 分月饼的方法数
"""
if m == n:
return 1
else:
comb_count = 0
for i in range(1, n - m + 2):
if m * i > n:
break
comb_count += calc_count(n - i, m - 1, i)
return comb_count
m, n = map(int, input().split()) # 输入m个员工和n个月饼
print(cal(m, n)) # 输出分月饼方法数