Content

小明想用 $n$ 块钱购买 $3$ 个物品：
- 圆规，每个7块。
- 笔，每支4块。
- 笔记本，每本3块。

同时，他还有3个要求：
设圆规、笔、笔记本购买的数量分别是 $(a,b,c)$，则：
1. $n$块钱必须全部花完，即 $7a+4b+3c=n$。
2. 在满足第一个要求的前提下，成套的数目最大，即满足 $\min{(a,b,c)}$ 为最大值。
3. 在满足第二个要求的前提下，总数量最大，即满足 $a+b+c$ 尽量大。

此时的最优解仅有一个，请求出这个最优解。

数据范围：$0\leqslant n\leqslant 10^5$。

Solution

来个更暴力的。

设 $x=n\div 14,y=n\bmod 14$，最优解为 $(a_0,b_0,c_0)$。（这里的 $\div$ 指整除）

我们直接可以根据$y$进行分类讨论：

1. $y=0$，此时正好成套，此时 $(a_0,b_0,c_0)=(x,x,x)$。
2. $y=1$，那这样子怎么办？没法再买了。没关系，腾出一个 $14$ 元不行吗？当然，如果恰好只有 $1$ 块钱，那就真的无解了。否则，腾出一个 $14$ 元来，套数减 $1$，这时剩下的钱数变成了 $15$ 元。因为这已经是成套数目最大的情况了，所以此时我们设法将总数量最大化，即尽量买花钱少的物品。我们欣喜地发现，在这个情况中，剩下 $15$ 块钱正好可以买 $5$ 个笔记本，所以此时 $(a_0,b_0,c_0)=(x-1,x-1,x+4)$。
3. $y=2$，跟 $y=1$ 时的做法类似，也是腾出 $14$ 块钱。此时剩下 $16$ 块钱，我们发现，最优方案此时是再购买 $4$ 个笔记本，$1$ 支笔。所以此时 $(a_0,b_0,c_0)=(x-1,x,x+3)$。当然如果正好只有 $2$ 块钱的话就真的无解了。
4. $y=3$，正好可以买 $1$ 本笔记本，此时 $(a_0,b_0,c_0)=(x,x,x+1)$。
5. $y=4$，正好可以买 $1$ 支笔，此时 $(a_0,b_0,c_0)=(x,x+1,x)$。
6. $y=5$，跟 $y=1$ 和 $y=2$ 时的做法类似，腾出 $14$ 元后就有了 $19$ 元，此时正好可以买 $5$ 本笔记本，$1$ 支笔，所以 $(a_0,b_0,c_0)=(x-1,x,x+4)$。当然如果正好只有 $5$ 块钱的话就真的无解了。
7. $y=6$，正好可以买 $2$ 本笔记本，此时 $(a_0,b_0,c_0)=(x,x,x+2)$。
8. $y=7$，正好可以买 $1$ 支笔，$1$ 本笔记本，此时 $(a_0,b_0,c_0)=(x,x+1,x+1)$。
9. $y=8$，正好可以买 $2$ 支笔，此时 $(a_0,b_0,c_0)=(x,x+2,x)$。
10. $y=9$，正好可以买 $3$ 本笔记本，此时 $(a_0,b_0,c_0)=(x,x,x+3)$。
11. $y=10$，正好可以买 $1$ 支笔，$2$ 本笔记本，此时 $(a_0,b_0,c_0)=(x,x+1,x+2)$。
12. $y=11$，正好可以买 $2$ 支笔，$1$ 本笔记本，此时 $(a_0,b_0,c_0)=(x,x+2,x+1)$。
13. $y=12$，正好可以买 $4$ 本笔记本，此时 $(a_0,b_0,c_0)=(x,x,x+4)$。
14. $y=13$，正好可以买 $1$ 支笔，$3$ 本笔记本，此时 $(a_0,b_0,c_0)=(x,x+1,x+3)$。

所有情况都讨论完了。
没错，完了。
接下来奉上最暴力的代码。

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
using namespace std;

int n, a, b, c;
//成套的数目尽量大，所以尽量多买14元 

int main() {
    scanf("%d", &n);
    int p = n / 14;
    switch(n % 14) {
        case 0: {
//          if(!p)  printf("-1");
            printf("%d %d %d", p, p, p);
            break;
        }
        case 1: {
            if(n < 14)  printf("-1");
            else    printf("%d %d %d", p - 1, p - 1, p + 4);
            break;
        }
        case 2: {
            if(n < 14)  printf("-1");
            else    printf("%d %d %d", p - 1, p, p + 3);
            break;
        }
        case 3: {
            printf("%d %d %d", p, p, p + 1);
            break;
        }
        case 4: {
            printf("%d %d %d", p, p + 1, p);
            break;
        }
        case 5: {
            if(n < 14)  printf("-1");
            else    printf("%d %d %d", p - 1, p, p + 4);
            break;
        }
        case 6: {
            printf("%d %d %d", p, p, p + 2);
            break;
        }
        case 7: {
            printf("%d %d %d", p, p + 1, p + 1);
            break;
        }
        case 8: {
            printf("%d %d %d", p, p + 2, p);
            break;
        }
        case 9: {
            printf("%d %d %d", p, p, p + 3);
            break;
        }
        case 10: {
            printf("%d %d %d", p, p + 1, p + 2);
            break;
        }
        case 11: {
            printf("%d %d %d", p, p + 2, p + 1);
            break;
        }
        case 12: {
            printf("%d %d %d", p, p, p + 4);
            break;
        }
        case 13: {
            printf("%d %d %d", p, p + 1, p + 3);
            break;
        }
    }
    return 0;
}