AT_pakencamp_2019_day4_g 三つの条件

[problemUrl]: https://atcoder.jp/contests/pakencamp-2019-day4/tasks/pakencamp_2019_day4_g 僕は，寿司が好きです． ところで，整数 $ 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` と出力してください． 出力形式について，詳しくは「出力」の項をご覧ください．

入力は以下の形式で標準入力から与えられます． > $ n $ $ a $ $ m $ $ p $ $ t $ $ K $ $ s_1 $$ s_2 $$ s_3 $$ s_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\ \leq\ n\ \leq\ 100 $． - $ 2\ \leq\ a\ \leq\ 1\ 000\ 000 $． - $ 0\ \leq\ m\ \leq\ 600 $． - $ 2\ \leq\ p\ \leq\ 600 $． - $ 0\ \leq\ t\ ． $ - $ 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 点) 追加の制約はない． ### Sample Explanation 1 条件を満たす整数は，$ 10,\ 100 $ しかありません． $ 10 $ は $ 2 $ 桁の整数ですが，最も上の桁が $ 0 $ となってもよいので，$ 010 $ と見なせば条件を満たします． なお，この入力例は小課題 $ 1 $ の制約を満たします． ### Sample Explanation 2 この入力例において，条件を満たす整数は $ 23 $ 個しか存在しません． $ K=25 $ 個より少ないので，最後の行に `-1` を出力すると正解になります． ### Sample Explanation 4 条件を満たす整数が $ 0 $ 通りの場合もあります．