問題一覧 > 通常問題

No.2104 Multiply-Add

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 57
作問者 : SumitacchanSumitacchan / テスター : 👑 hitonanodehitonanode 👑 ygussanyygussany
2 ProblemId : 8327 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-08 11:11:47

問題文

$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|\le 10^9,|y|\le 10^9$ が満たされている必要があります。

上記操作により $(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もしくは右上の雲マークをクリックしてアカウントを作成してください。