英文原题 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 16450 Accepted: 8286 Description
Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc. All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite.
Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post. Input
Input is a sequence of lines, each containing two positive integers s and d. Output
For each line of input, output one line containing either a single integer giving the amount of surplus for the entire year, or output Deficit if it is impossible. Sample Input
59 237 375 743 200000 849694 2500000 8000000 Sample Output
116 28 300612 Deficit Source
Waterloo local 2000.01.29
时间限制：1000MS内存限制：65536K 提交总数：16452接受：8287 描述
计算机机械师（ACM）的会计受到了千年虫问题的困扰，并失去了一些准备MS公司年度报告的重要数据。 所有他们记得的是，MS Inc.在1999年每个月发布了盈余或赤字，MS Inc.发布盈余的每个月都有盈余，盈余的数量为s，MS Inc.每月发布赤字的时候，赤字为d。他们不记得发布了多少个月或多少个月的盈余或亏空。与其他公司不同，MS Inc.每年连续5个月发布其收益。 ACM知道这8个帖子中的每一个都报告了赤字，但他们不知道有多少。总会计师几乎可以肯定，MS Inc.将在1999年全年发布盈余。几乎不是。
编写一个程序，决定MS公司是否在1999年遭遇赤字，或者如果1999年有盈余，他们可以发布的最大剩余金额是多少。 输入
输入是一系列行，每行包含两个正整数s和d。 产量
对于每一行输入，输出一行，其中包含一个给出整年盈余量的整数，如果不可能，则输出“Deficit”。 示例输入
59 237 375 743 200000 849694 2500000 8000000 示例输出
116 28 300612 Deficit 资源
滑铁卢当地2000.01.29
这题的意思有点难懂，大概是每个月，不是亏钱就是盈利，然而，对于一年 12 个月中的任何连续的 5 个月，它们总是亏钱，问你这一年最多能盈利多少。
注意： 0 元也算是亏钱。
很明显，12 个月，枚举一下每个月的状态，再判断当前状态下这个月为结尾的连续 5 个月是否亏钱，如果满足，那么继续枚举下一个月。一趟 DFS 就下来了。当然，由于题目没有明确的数据范围，我们要尽量快地求的答案，而这并不是最快的方式。
我们设开始的 5 个月里，有 x 个月亏钱，有 5-x 个月盈利，那么 x 的取值正好满足最小且 x*d ≥ 5*s - x*s。由于不是亏 d 元就是挣 s 元，那么任意 5 个月只要包括了 x 个 d 就可以满足条件。
我们为了使得 d 的总数最少，肯定要使得每个 d 被多个区间包括，那么对于前 5 个月，我们肯定把 d 放在 s 后面。例如 x=2 时，前五个月应该是 sssdd 最佳。接下来很明显又是连续 3 个月的 s ……
经过观察我们会发现，最优方式往往是这样形成的：{连续 5-x 个 s } + {连续 x 个 d }＋ {连续 5-x 个 s } + {连续 x 个 d }……直到第 12 个。 也就是如下的 5 中情况：
ssssdssssdss sssddsssddss ssdddssdddss sddddsddddsd dddddddddddd
只要求出 x 值，特判就可以了。
