問題一覧 > 通常問題

No.2152 [Cherry Anniversary 2] 19 Petals of Cherry

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 47
作問者 : 👑 KazunKazun / テスター : AngrySadEightAngrySadEight
1 ProblemId : 8838 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-08 19:29:36

注意

この問題の Time Limit は $1000$ ms である.

問題

$19$ 個の整数列 $A_1, \dots, A_{19}$ が与えられる. $i=1,2, \dots, 19$ に対して, $A_i$ は長さ $L_i$ で $A_i=(A_{i,1}, \dots, A_{i,L_i})$ である.

$(1,2, \dots, 19)$ の並び替え $P=(P_1, \dots, P_{19})$ のうち, 以下を満たすような並び替えを 素晴らしい順列 という.

  • $1$ 以上 $19$ 以下の任意の整数 $i$ に対して, $P_i=A_{i,j}$ となるような $1$ 以上 $L_i$ 以下の整数 $j$ が存在する.

また, $(1,2, \dots, 19)$ の並び替え $P$ に対して, $t(P)$ を次のようにして定める.

  • 「$P$ にある隣接する $2$ 要素を選び, 入れ替える」という操作を $P$ から $(1,2, \dots, 19)$ にするのに必要な操作の最小回数.
  • このとき, $t(P)$ が偶数ならば $P$ は 公平な順列, $t(P)$ が奇数ならば $P$ は 奇妙な順列 であるという.

    公平な素晴らしい順列 の数 $X_{{\rm even}}$, 奇妙な素晴らしい順列 の数 $X_{{\rm odd}}$ をそれぞれ求めよ.

    なお, 問題文において, $(1,2, \dots, 19)$ は $(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19)$ のことを意味する.

    制約

    • $0 \leq L_i \leq 19 \quad (1 \leq i \leq 19)$
    • $1 \leq A_{i,1} \lt \dots \lt A_{i,L_i} \leq 19 \quad (1 \leq i \leq 19)$
    • 入力は全て整数である.

    入力

    $L_1$ $A_{1,1}$ $\cdots$ $A_{1,L_1}$
    $\vdots$
    $L_{19}$ $A_{19,1}$ $\cdots$ $A_{19,L_{19}}$

    出力

    $X_{{\rm even}}, X_{{\rm odd}}$ をこの順に空白区切りで出力せよ. つまり, 次のような形式で出力せよ.

    $X_{{\rm even}}$ $X_{{\rm odd}}$

    サンプル

    サンプル1
    入力
    2 1 2
    2 1 2
    1 3
    1 4
    1 5
    1 6
    1 7
    1 8
    1 9
    1 10
    1 11
    1 12
    1 13
    1 14
    1 15
    1 16
    1 17
    1 18
    1 19
    出力
    1 1

    素晴らしい順列 は $(1,2,3,4,5, \dots, 19), (2,1,3,4,5, \dots, 19)$ の $2$ 個である. それぞれについて, 次のようになる.

    • $P=(1,2,3,4,5, \dots, 19)$ のとき, $t(P)=0$ である. よって, $P$ は 公平な素晴らしい順列 である.
    • $P=(2,1,3,4,5, \dots, 19)$ のとき, $t(P)=1$ である. よって, $P$ は 奇妙な素晴らしい順列 である.
    以上から, 公平な素晴らしい順列奇妙な素晴らしい順列 はそれぞれ $1$ 個ずつである.

    サンプル2
    入力
    4 2 3 4 5
    4 1 3 4 5
    4 1 2 4 5
    4 1 2 3 5
    4 1 2 3 4
    7 11 12 13 14 16 17 19
    5 8 9 10 15 18
    5 7 9 10 15 18
    5 7 8 10 15 18
    5 7 8 9 15 18
    7 6 12 13 14 16 17 19
    7 6 11 13 14 16 17 19
    7 6 11 12 14 16 17 19
    7 6 11 12 13 16 17 19
    5 7 8 9 10 18
    7 6 11 12 13 14 17 19
    7 6 11 12 13 14 16 19
    5 7 8 9 10 15
    7 6 11 12 13 14 16 17
    出力
    86476460 86476320

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

    $L_i=0$ となる $i$ が存在する可能性がある.

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