No.2104 Multiply-Add
タグ : / 解いたユーザー数 61
作問者 :
Sumitacchan
/ テスター :
hitonanode
ygussany
問題文
$2$ つの変数 $x,y$ があり、最初は $(x,y)=(a,b)$ です。
あなたは以下のいずれかの操作を、好きな順番で合計 $1000$ 回まで行うことができます（$0$ 回でもよい）。
- 操作 $1$ : 整数 $k\ (-10^9 \le k \le 10^9)$ を選択して、$x$ に $k \times y$ を加算する。
- 操作 $2$ : 整数 $k\ (-10^9 \le k \le 10^9)$ を選択して、$y$ に $k \times x$ を加算する。
上記操作により $(x,y)=(c,d)$ にすることが可能かを判定し、可能であればそのような操作列を一つ示してください。
制約
- $-10^8 \le a,b,c,d \le 10^8$
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられます。
$a\ \ b\ \ c\ \ d$
出力
$(x,y)=(c,d)$ にすることが不可能であれば $-1$ を出力してください。
$(x,y)=(c,d)$ にすることが可能であれば、そのような操作列を次の形式で出力してください（条件を満たす操作列が複数存在する場合はいずれを出力しても構いません）。
$N$ $t_1\ \ k_1$ $t_2\ \ k_2$ $\vdots$ $t_N\ \ k_N$ここで、$N$ は操作回数であり、$t_i,k_i\ (1\le i\le N)$ はそれぞれ $i$ 回目の操作における操作の種類と選択した $k$ の値です。
それぞれ、次の条件を満たす整数である必要があります。
- $0 \le N\le 1000$
- $t_i=1$ または $t_i=2$
- $-10^9\le k_i \le 10^9$
サンプル
サンプル1
入力
5 1 -10 19
出力
4 1 3 2 1 1 -2 2 -1
$4$ 回の操作により $(x,y)$ は次のように変化します。
$(5,1) \rightarrow (8,1) \rightarrow (8,9) \rightarrow (-10,9) \rightarrow (-10,19)$
サンプル2
入力
0 0 1 -1
出力
-1
何回操作しても $(x,y)=(0,0)$ のままです。
サンプル3
入力
123 456 123 456
出力
0
最初から $(x,y)=(c,d)$ を満たしています。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。