No.3245 Payment with 8-rep Currency
タグ : / 解いたユーザー数 33
作問者 : 👑
hamamu
Problem Statement
Using coins of $8$ yuki dollars, $88$ yuki dollars, $888$ yuki dollars, and $8888$ yuki dollars, can you pay an exact amount without the numbers of coins being unbalanced?
In the country of yuki, the "yuki dollar" is used as the unit of currency (hereafter, "$x$ yuki dollars" is written as "Y $x$", with "Y" placed before $x$). There are $4$ types of coins: Y $8$, Y $88$, Y $888$, and Y $8888$.
Alice, who lives in the country of yuki, went shopping at a certain store, and the bill came to Y $N$.
Alice has $10^{100}$ coins of each of Y $8$, Y $88$, Y $888$, and Y $8888$ on hand.
Alice is particular about how she pays money, and she wants to pay so that the following conditions are satisfied.
- She pays the exact amount.
- That is, letting $A, B, C, D$ be the numbers of Y $8$, Y $88$, Y $888$, and Y $8888$ coins paid, respectively, $8A + 88B + 888C + 8888D = N$ holds.
- For every type of coin, the number of coins of that type paid is less than half of the total number of coins used in the payment.
- That is, $A, B, C, D < \dfrac{S}{2}$ holds (where $S = A + B + C + D$).
Determine whether there exists a way to pay Y $N$ satisfying the above conditions, and if one exists, find $1$ such way.
You are given $T$ test cases; solve each of them.
Constraints
- All input values are integers.
- $1 \leq T \leq 8.88 \times 10^4$
- $1 \leq N \leq 8.88 \times 10^{17}$
Input
The input is given from Standard Input in the following format, where $\mathrm{case}_i$ represents the $i$-th test case.
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each case is given in the following format.
$N$
Output
Print $T$ lines. On the $i$-th line, for the $i$-th test case, print $-1$ if there is no way to pay Y $N$ satisfying the conditions; otherwise, print the numbers $A, B, C, D$ of Y $8$, Y $88$, Y $888$, and Y $8888$ coins paid, separated by spaces, in this order. If there are multiple answers, any of them will be accepted.
Sample
Sample 1
Input
4 8 984 80574336 878787878787878787
Output
-1 1 1 1 0 888 8888 888 8888 -1
For the $1$st test case, the payment $(A, B, C, D) = (1, 0, 0, 0)$ is the only payment satisfying the $1$st condition, but it does not satisfy the $2$nd condition. Therefore, no payment satisfying the conditions exists.
For the $2$nd test case, the payment $(A, B, C, D) = (1, 1, 1, 0)$ satisfies the $1$st condition since $888 \times 1 + 88 \times 1 + 8 \times 1 = 984$, and it also satisfies the $2$nd condition since the number of coins used of each type is less than half of the total of $3$ coins. Therefore, this output is correct.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。