#P1012. 【挑战题】文具采购

【挑战题】文具采购

题目描述

禾木的班上共有 nn 元班费,同学们准备使用班费集体购买 33 种物品:

  1. 圆规,每个 77 元。
  2. 笔,每支 44 元。
  3. 笔记本,每本 33 元。

禾木负责订购文具,设圆规,笔,笔记本的订购数量分别为 a,b,ca,b,c,他订购的原则依次如下:

  1. nn 元钱必须正好用光,即 7a+4b+3c=n7a+4b+3c=n
  2. 在满足以上条件情况下,成套的数量尽可能大,即 a,b,ca,b,c 中的最小值尽可能大。
  3. 在满足以上条件情况下,物品的总数尽可能大,即 a+b+ca+b+c 尽可能大。

请你帮助禾木求出满足条件的最优方案。可以证明若存在方案,则最优方案唯一。

输入格式

输入仅一行一个整数,代表班费数量 nn

输出格式

如果问题无解,请输出 1-1

否则输出一行三个用空格隔开的整数 a,b,ca, b, c,分别代表圆规、笔、笔记本的个数。

样例 #1

样例输入 #1

1

样例输出 #1

-1

样例 #2

样例输入 #2

14

样例输出 #2

1 1 1

样例 #3

样例输入 #3

33

样例输出 #3

1 2 6

提示

样例输入输出 3 解释

a=2,b=4,c=1a=2,b=4,c=1 也是满足条件 1,21,2 的方案,但对于条件 33,该方案只买了 77 个物品,不如 a=1,b=2,c=6a=1,b=2,c=6 的方案。

数据规模与约定

  • 对于测试点 161 \sim 6,保证 n14n \leq 14
  • 对于测试点 7127 \sim 12,保证 nn1414 的倍数。
  • 对于测试点 131813 \sim 18,保证 n100n \leq 100
  • 对于全部的测试点,保证 0n1050 \leq n \leq 10^5