問題一覧 > 通常問題

No.3245 Payment with 8-rep Currency

レベル : / AI推定難易度 : 1575 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 33
作問者 : 👑 AngrySadEight / テスター : 👑 hamamu ygussany
お気に入りにしたユーザー ProblemId : 12486 / 自分の提出
問題文最終更新日: 2025-08-19 01:41:11
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 479 AngrySadEightお誕生日コンテスト2025 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。