問題一覧 > 通常問題

No.1401 全自動マクロの作り方

レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 15
作問者 : CuriousFairy315CuriousFairy315 / テスター : hotmanwwhotmanww
1 ProblemId : 4319 / 出題時の順位表
問題文最終更新日: 2021-02-18 13:50:28

問題文

315さんの仕事は、指定された通りにExcelに画像を貼り付けたりバッチファイルを実行することです。
この仕事は単調で面倒な作業であり、315さんは常々もっと高度な仕事をやりたいと思っていました。
ある日、315さんはこの仕事が高々 $N$ 個の操作列 $S$ で表せることに気付いてしまいました。
操作列 $S_i$ は長さ $d_i$ の数列であり、この数列の各項とキーなどの入力装置の操作が一対一に対応しています。
315さんは競技プログラミングを嗜んでいるので、どんな仕事が割り振られても自動で仕事をこなしてくれるマクロを作成することにしました。

マクロは、数列 $A$ として定義されます。
まず、初めに長さ $N$ で全ての項が $0$ の数列 $M$ を定義します。
次に、 $n=0, 1, 2, \dots, $ に対して、次のような操作を順に行っていきます。

  • $A_{(n \mod |A|) + 1} = S_{j, (M_j \mod |S_j|) + 1}$ となる $j$ を全て求める。
  • その後、それら全ての $j$ に対して $M_j$ に $1$ を加算する。
ここで、 $M_i$ が $|S_i|$ の正の整数倍で表されるとき、 $S_i$ の仕事は達成できたと定義されます。
315さんは、仕事を全自動で終わらせるマクロ $A$ は次の条件を満たしてほしいと考えています。
  • $n$ が $|A|$の倍数$-1$ である、すなわちちょうどマクロの最後を読んだ時、全ての仕事が達成できた状態になるような $n$ が存在する。
このようなマクロを一つ求めてください。

入力

$N$
$d_1 \ S_{1,1} \ \cdots \ S_{1, d_1}$
$\vdots$
$d_N \ S_{N, 1} \ \cdots \ S_{N, d_N}$
  • $1 \leq N \leq 2000$
  • $1 \leq d_i \leq 2000$
  • $0 \leq S_{i, j} < \sum_{i=1}^{N} d_i \leq 2000$
  • 入力は全て整数である

出力

条件を満たすマクロ $A$ が存在しない場合、0を一行目に出力します。
そうでない場合、まず一行目にはマクロの長さ $|A| \leq 2000$ を出力します。
次に、二行目には $A$ の各項を空白区切りで出力します。
いずれの場合も、最後に改行してください。

サンプル

サンプル1
入力
1
3 1 2 1
出力
3
1 2 1

マクロ1 2 1は、マクロが1回実行された時にちょうど仕事を1回達成できるので、有効なマクロです。
マクロ1 2 1 1 2 1なども正答として扱われますが、11 2 1 1は正答として扱われないことに注意してください。

サンプル2
入力
3
3 1 1 2
1 1
5 3 1 1 1 2
出力
4
3 1 1 2

マクロ3 1 1 2は、マクロが2回実行された時に仕事1を2回、仕事2を4回、仕事3を1回達成できるので、有効なマクロです。

サンプル3
入力
2
2 1 2
2 2 1
出力
0

この仕事全てを達成できるマクロは存在しません。
大人しく人力で作業を続けましょう。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。