纪念券面额都是 233 乘以 10 的幂,因此 x 能被凑出当且仅当 x 能被 233 整除。令 y=x/233,问题变成:用尽量少个形如 10i 的数(即各位上的数字)凑出 y。
十进制下 y 的每一位数字 d 表示在该数位上使用 d 个 1,也就是使用 d 张对应面额的纪念券。各位数字之和就是最少张数。若 x 不能被 233 整除,输出 −1。
文创店发行一批纪念券,面额被规定为形如 233×10i(i 为非负整数)的数,例如 233、2330、23300。顾客每次给出应付金额 x,可以用任意张纪念券(面额可重复)恰好凑出 x,并希望张数尽量少;若无法恰好凑出,则记为 -1。共有 t 组询问。
约束:1≤t≤102,0≤x≤100000000000000。
第一行一个整数 t,表示询问组数。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册