N - Polynomial Comparison Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

T 個のケースについて、以下の問題を解いてください。

整数 k と N 次の整数係数多項式 f(x)=a_Nx^N+a_{N-1}x^{N-1}+\ldots+a_0 、 M 次の整数係数多項式 g(x)=b_Mx^M+b_{M-1}x^{M-1}+\ldots+b_0 が与えられます。 f(k) と g(k) の大小関係を求めてください。

制約

  • 1 \le T \le 10^5
  • 0 \le N, M \le 10^5
  • |a_i|, |b_j|, |k| \le 10^5
  • a_N, b_M \neq 0
  • 1 つの入力で与えられる N,M の総和はそれぞれ 10^5 を超えない
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各ケースは以下の形式で与えられる。

f,g の係数が降冪の順に与えられることに注意せよ。

N M k
a_N a_{N-1} \ldots a_0
b_M b_{M-1} \ldots b_0

出力

T 行出力せよ。 i 行目には、 \mathrm{case}_i に対する答えを出力せよ。

各ケースについては、 f(k)>g(k) ならば > 、 f(k)=g(k) ならば = 、 f(k)<g(k) ならば < と出力せよ。

入力例 1

3
2 1 3
2 0 1
4 5
0 0 0
2
2
5 7 -89401
-79604 56304 -25588 -4414 73961 28352
-6628 -12831 6978 373 -36054 82166 30928 50750

出力例 1

>
=
<

1 ケース目について、 f(x)=2x^2+1,g(x)=4x+5 ですから、 f(3)=19,g(3)=17 より f(3)>g(3) です。

原案: turtle0123__