#P4921. 买笔

买笔

买笔

题目描述

班费共 xx 元,商店里有三种钢笔,单价分别为 66 元、55 元、44 元。要求把钱恰好花完,并且购买尽量多的笔。

在笔数最多的方案中,优先选择 66 元笔更多的方案;如果仍有多种,再选择 55 元笔更多的方案。请输出三种笔的支数。

输入格式

一个整数 xx,表示剩余的班费。

输出格式

一行三个整数,依次为 66 元、55 元、44 元笔的支数,相邻两数之间用一个空格分隔。

数据范围与约定

  • 8≤x≤1098 \le x \le 10^9。
  • 课程数据保证 x≥8x\ge8,此时一定存在恰好把钱花完的方案。

样例输入

10

样例输出

1 0 1

样例说明

先假设每支笔都是 44 元,最多买 k=⌊x/4⌋k=\lfloor x/4\rfloor 支,余钱 r=x−4kr=x-4k,其中 0≤r≤30\le r\le3。

把一支 44 元笔换成 55 元笔要多花 11 元,换成 66 元笔要多花 22 元。为了让笔数保持 kk,应先用余钱做 66 元升级,再做 55 元升级。

于是 66 元笔有 ⌊r/2⌋\lfloor r/2\rfloor 支;若 rr 为奇数,还有 11 支 55 元笔;其余为 44 元笔。例如 x=10x=10 时 k=2,r=2k=2,r=2,得到 (1,0,1)(1,0,1)。