计划第191题:出勤奖励"/>
欧拉计划第191题:出勤奖励
本题难度系数为35%(5%最易,100%最难)。
某所学校给有出勤和守时表现良好的孩子发放现金奖励。如果孩子连续三天缺席,或是有多于一次迟到,则拿不到这份奖励。
根据n天的实际出勤情况,我们可以生成L(迟到)、O(准时)和A(缺席)这三个字母组成的字符串。
根据4天的出勤情况,能够生成的字符串一共有81种可能,其中恰好有43个串可以获得奖励:
OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA
LAOO LAOA LAAO
根据30天的出勤情况生成的字符串中,有多少个是可以获得奖励的串?
解:
假设第n天的时候,根据字符串的结尾以及有无L,分为以下几种情况:
第n+1天的时候,可能会分别追加A、L或O三个字母,去掉无法得到奖励的串,列出这些可能性:
合并为6种情况,则有:
第1天的初始状态是:
代码实现非常简单:
a, b, c, d, e, f = 0, 0, 1, 0, 1, 1
for i in range(2, 31):a, b, c, d, e, f = c, d, e, f, a+c+e, a+b+c+d+e+f
print(sum([a, b, c, d, e, f]))
更多推荐
欧拉计划第191题:出勤奖励
发布评论