G - 三つの条件 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

僕は，寿司が好きです．

ところで，整数 X は n 桁の a 進数です．最も上の桁が 0 となることもあり得ます．
また，F(X) は X の a 進数表記での桁和を 10 進数で表したものとします．例えば，a = 7, X = 562 の場合，F(X) = 13 です．

さて，次の 3 つの条件を同時に満たすような X として考えられる整数を，小さい順から K 個出力してください．

  • F(X) = m．
  • X' \ mod \ p = t．(ただし，X' は X を 10 進数に直した整数)
  • s_i = 0 であるような全ての整数 i (1 \leq i \leq n) について，整数 X の a^{n-i} の位は 0 である．
    • 例えば，n = 7，a = 10，s = 1110110 の場合，X の 1000 の位と 1 の位は 0 でなければならない．

ただし，そのような整数が K 個未満しか存在しない場合，条件を満たす整数を小さい順にすべて出力した後，最後に -1 と出力してください．

出力形式について，詳しくは「出力」の項をご覧ください．

制約

  • 1 \leq n \leq 100．
  • 2 \leq a \leq 1 \ 000 \ 000．
  • 0 \leq m \leq 600．
  • 2 \leq p \leq 600．
  • 0 \leq t < p．
  • 1 \leq K \leq 2 \ 000．
  • s_i は 0 または 1．
  • n, a, m, p, t, K は 10 進数で表記された整数である．

部分点

この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます．
提出したソースコードの得点は，正解した小課題の点数の合計となります．

  1. (7 点) m = 1．
  2. (8 点) n \leq 6，a \leq 10．
  3. (24 点) n \leq 32，a = 2．
  4. (29 点) n \leq 50，a \leq 10，m \leq 50，p \leq 50．
  5. (23 点) a \geq m．
  6. (9 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられます． 

n a m p t K
s_1s_2s_3s_4...s_n

出力

条件を満たす整数が K 個以上ある場合は，以下の形式で出力してください．

(小さい方から 1 番目の整数の情報)
(小さい方から 2 番目の整数の情報)
(小さい方から 3 番目の整数の情報)
:
(小さい方から K 番目の整数の情報)

また，条件を満たす整数が K 個に満たない場合は，以下の形式で出力してください．（ここでは，条件を満たす整数の個数を K' としています．）

(小さい方から 1 番目の整数の情報)
(小さい方から 2 番目の整数の情報)
(小さい方から 3 番目の整数の情報)
:
(小さい方から K' 番目の整数の情報)
-1

ただし，整数の情報は，出力するべき整数が g_{n-1}a^{n-1}+g_{n-2}a^{n-2}+...+g_0a^0 (0 \leq g_i \leq a-1) で表されるとき，以下の形式で一行に出力して下さい．

g_{n-1} g_{n-2} g_{n-3} ... g_{0}

入力例 1

3 10 1 5 0 2
111

出力例 1

0 1 0
1 0 0

条件を満たす整数は，10, 100 しかありません．
10 は 2 桁の整数ですが，最も上の桁が 0 となってもよいので，010 と見なせば条件を満たします． なお，この入力例は小課題 1 の制約を満たします．

入力例 2

6 10 26 241 74 25
111110

出力例 2

0 6 6 5 9 0
0 8 8 2 8 0
1 0 9 9 7 0
1 9 6 7 3 0
2 8 3 4 9 0
3 2 6 8 7 0
3 4 8 5 6 0
3 9 1 9 4 0
4 7 8 7 0 0
5 4 3 7 7 0
5 6 5 4 6 0
5 8 7 1 5 0
6 0 8 8 4 0
6 7 3 9 1 0
6 9 5 6 0 0
7 1 7 2 9 0
7 6 0 6 7 0
7 8 2 3 6 0
8 2 5 7 4 0
8 4 7 4 3 0
8 6 9 1 2 0
8 9 0 8 1 0
9 3 4 1 9 0
-1

この入力例において，条件を満たす整数は 23 個しか存在しません．
K=25 個より少ないので，最後の行に -1 を出力すると正解になります．

入力例 3

3 2 3 7 0 2000
111

出力例 3

1 1 1
-1

入力例 4

40 23 166 240 130 1117
1000000000100000000010000000001000000000

出力例 4

-1

条件を満たす整数が 0 通りの場合もあります．