No.2811 Calculation Within Sequence
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 106
作問者 :
tfltkpc
/ テスター :
hirayuu_yc
highlighter
Magentor
Yoyoyo8128
zeta7532
タグ : / 解いたユーザー数 106
作問者 :
tfltkpc
/ テスター :
hirayuu_yc
highlighter
Magentor
Yoyoyo8128
zeta7532
問題文最終更新日: 2024-07-19 21:19:23
問題文
$10^{100}$ 項からなる整数列 $T,S$ があります。入力では数列 $T$ の先頭 $a$ 項と数列 $S$ の先頭 $b$ 項が与えられます。与えられる項以外はすべて $0$ です。
以下の操作を $0$ 回以上好きな回数行うことで、$T$ と $S$ を一致させられるか判定してください。
- 以下のどちらかを行う。
- 相異なる $1$ 以上 $10^{100}$ 以下の整数の組 $p,q,r$ を選び、$T_{r}$ を $T_{p}+T_{q}$ で置き換える。
- 相異なる $1$ 以上 $10^{100}$ 以下の整数の組 $p,q,r$ を選び、$T_{r}$ を $T_{p}-T_{q}$ で置き換える。
制約
- $1 \leq a,b \leq 2 \times 10^{5}$
- $1 \leq T_i,S_i \leq 10^{9}$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
$a~~~b$
$T_{1} ~~~ T_{2} ~ \ldots ~ T_{a}$
$S_{1} ~~~ S_{2} ~ \ldots ~ S_{b}$
出力
操作によって $T$ と $S$ を一致させられるならば Yes 、そうでなければ No と出力し、最後に改行してください。
サンプル
サンプル1
入力
3 2 3 7 5 2 8
出力
Yes
例えば、次のような操作で $T=S$ にすることができます。
1. $T_{2}$ を $T_{1}+T_{3}$ で置き換える。 $T=(3,8,5,0,0,0...)$ となる。
2. $T_{4}$ を $T_{3}-T_{1}$ で置き換える。 $T=(3,8,5,2,0,0...)$ となる。
3. $T_{1}$ を $T_{4}+T_{5}$ で置き換える。 $T=(2,8,5,2,0,0...)$ となる。
4. $T_{3}$ を $T_{5}+T_{6}$ で置き換える。 $T=(2,8,0,2,0,0...)$ となる。
5. $T_{4}$ を $T_{5}+T_{6}$ で置き換える。 $T=(2,8,0,0,0,0...)$ となり、$S$ と一致する。
よって、答えはYesです。
サンプル2
入力
2 3 2 8 3 7 5
出力
No
どのように操作を行っても、 $T$ を $S$ と一致させることはできません。
サンプル3
入力
5 1 3 3 3 3 3 777
出力
Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。