問題一覧 > 通常問題

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

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 50
作問者 : 👑 Kazun / テスター : 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 8838 / 自分の提出
問題文最終更新日: 2022-12-08 19:29:36
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
Advent Calendar Contest 2022 (順位表) の他の問題:

Note

The Time Limit for this problem is $1000$ ms.

Problem Statement

You are given $19$ integer sequences $A_1, \dots, A_{19}$. For $i=1,2, \dots, 19$, $A_i$ has length $L_i$ and $A_i=(A_{i,1}, \dots, A_{i,L_i})$.

A permutation $P=(P_1, \dots, P_{19})$ of $(1,2, \dots, 19)$ is called a wonderful permutation if it satisfies the following.

  • For every integer $i$ between $1$ and $19$, inclusive, there exists an integer $j$ between $1$ and $L_i$, inclusive, such that $P_i=A_{i,j}$.

Also, for a permutation $P$ of $(1,2, \dots, 19)$, define $t(P)$ as follows.

  • The minimum number of operations "choose $2$ adjacent elements in $P$ and swap them" required to turn $P$ into $(1,2, \dots, 19)$.
  • Then, if $t(P)$ is even, $P$ is called a fair permutation, and if $t(P)$ is odd, $P$ is called a strange permutation.

    Find the number $X_{{\rm even}}$ of fair wonderful permutations and the number $X_{{\rm odd}}$ of strange wonderful permutations.

    Note that, in this problem statement, $(1,2, \dots, 19)$ means $(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19)$.

    Constraints

    • $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)$
    • All input values are integers.

    Input

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

    Output

    Output $X_{{\rm even}}, X_{{\rm odd}}$ in this order, separated by a space. That is, output in the following format.

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

    Sample

    Sample 1
    Input
    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
    Output
    1 1

    The wonderful permutations are $(1,2,3,4,5, \dots, 19), (2,1,3,4,5, \dots, 19)$, which makes $2$ in total. For each of them, we have the following.

    • When $P=(1,2,3,4,5, \dots, 19)$, we have $t(P)=0$. Thus, $P$ is a fair wonderful permutation.
    • When $P=(2,1,3,4,5, \dots, 19)$, we have $t(P)=1$. Thus, $P$ is a strange wonderful permutation.
    From the above, the numbers of fair wonderful permutations and strange wonderful permutations are each $1$.

    Sample 2
    Input
    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
    Output
    86476460 86476320

    Sample 3
    Input
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    0
    Output
    0 0

    There may exist $i$ such that $L_i=0$.

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