問題一覧 > 教育的問題

No.2184 A○B Problem

レベル : / AI推定難易度 : 115 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 108
作問者 : 👑 p-adic / テスター : 👑 箱星
お気に入りにしたユーザー ProblemId : 8440 / 自分の提出
問題文最終更新日: 2023-01-13 11:02:37
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
yukicoder contest 373 (順位表) の他の問題:

Problem Statement

Permutations $A,B$ of degree $5$ are given as input.

 

Find the composite permutation $A \circ B$.

 

Below is an explanation for those unfamiliar with permutations and their $1$-line notation. (Click to expand)

 

For a positive integer $n$, a permutation of degree $n$ is, roughly speaking, a function that shuffles the positive integers less than or equal to $n$. More precisely, it is defined as follows:

 

Definition (Permutation)

Let $I_n$ be the set of all positive integers less than or equal to $n$. A permutation of degree $n$ is a bijective map from $I_n$ to $I_n$.

 

For example, the identity map on $I_n$ is a permutation of degree $n$, and it is called the identity permutation.

 

Given permutations $a$ and $b$ of degree $n$, their composition as maps $a \circ b$ is also a permutation of degree $n$, which is called the composite permutation of $a$ and $b$. In other words, the composite permutation $a \circ b$ is the permutation of degree $n$ defined as the map sending each positive integer $i$ less than or equal to $n$ to $a(b(i))$.

 

There are various ways to represent a permutation of degree $n$. For example, the notation that lists the images of the positive integers $i$ in increasing order of $i$ is called $1$-line notation.

Depending on the convention, $1$-line notation may enclose the whole list of numbers in parentheses or separate the listed numbers with commas, but here we do not enclose them in parentheses and separate them with spaces.

For example, consider the case $n = 5$. The map $a$ sending each positive integer $i$ less than or equal to $5$ to the unique positive integer $j$ less than or equal to $5$ satisfying $2i \equiv j \pmod{5}$ is a permutation of degree $5$, and since

$\displaystyle \begin{array}{rcl} \displaystyle a(1) &\displaystyle = &\displaystyle 2 \\ \displaystyle a(2) &\displaystyle = &\displaystyle 4 \\ \displaystyle a(3) &\displaystyle = &\displaystyle 1 \\ \displaystyle a(4) &\displaystyle = &\displaystyle 3 \\ \displaystyle a(5) &\displaystyle = &\displaystyle 5 \end{array} $

holds, in $1$-line notation $a$ is written as

$\displaystyle 2 \ 4 \ 1 \ 3 \ 5 $

. More generally, a permutation $a$ of degree $5$ is written in $1$-line notation as

$\displaystyle a(1) \ a(2) \ a(3) \ a(4) \ a(5) $

.

Input

The input is given from standard input in $2$ lines in the following format:

  • Line $1$ contains $A$ in $1$-line notation.
  • Line $2$ contains $B$ in $1$-line notation.

In the input, the numbers in $1$-line notation are separated by half-width spaces.

Constraints

The input satisfies the following constraints:

  • $A$ is a permutation of degree $5$
  • $B$ is a permutation of degree $5$

Output

Output the string representing $A \circ B$ in $1$-line notation on $1$ line.

As in the input, separate the numbers in $1$-line notation with half-width spaces.

Print a newline at the end.

Sample

Sample 1
Input
1 2 3 4 5
2 4 5 1 3
Output
2 4 5 1 3

Since $A$ is the identity permutation, $A \circ B = B$ holds. Writing this equality in $1$-line notation gives

$\displaystyle 1 \ 2 \ 3 \ 4 \ 5 \circ 2 \ 4 \ 5 \ 1 \ 3 = 2 \ 4 \ 5 \ 1 \ 3 $

.

Sample 2
Input
3 1 5 4 2
1 2 3 4 5
Output
3 1 5 4 2

Since $B$ is the identity permutation, $A \circ B = A$ holds. Writing this equality in $1$-line notation gives

$\displaystyle 3 \ 1 \ 5 \ 4 \ 2 \circ 1 \ 2 \ 3 \ 4 \ 5 = 3 \ 1 \ 5 \ 4 \ 2 $

.

Sample 3
Input
2 1 3 4 5
2 1 3 4 5
Output
1 2 3 4 5

Both $A$ and $B$ are permutations of degree $5$ that only swap $1$ and $2$. Their composite permutation just flips $1$ and $2$ over $2$ times, so it is the identity transformation. That is,

$\displaystyle 2 \ 1 \ 3 \ 4 \ 5 \circ 2 \ 1 \ 3 \ 4 \ 5 = 1 \ 2 \ 3 \ 4 \ 5 $

.

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