問題一覧 > 通常問題

No.265 数学のテスト

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 95
作問者 : btkbtk
5 ProblemId : 605 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:49:20

問題文

高校生の田中君は、数学のテストを受けています。
しかし田中君はある問題が解けず、このままでは赤点になってしまいます。
ある問題とは、微分を含む一変数多項式を解く問題です。

田中君の脳はインターネットに接続しており、テスト中でも式をコンピュータに送信し答えを受け取ることができます。
田中君のために、与えられた式を計算して解くプログラムを組んであげてください。

式に現れる演算子は足し算を表す'+',かけ算を表す'*'だけとなっています。
式に現れる値は定数と変数'x'、式$f(x)$の導関数"d{$f(x)$}"です。
($f(x)$の導関数は一般的なライプニッツの記法で$\frac{d}{dx}\{f(x)\}$ですが式を簡単化するため"d{$f(x)$}"としています。)

演算子が限られているため,$x^n=x*x*x*...*x*x$と$x$のn乗がn個の$x$同士のかけ算で表されることに注意してください。
演算子の優先順序は、現実の世界と同様の '+' < '*' です。

(追記)$\frac{d}{dx}\{x^n\}=n*x^{n-1}$であることが一般的に知られています。
$\frac{d}{dx}\{x^n +\frac{d}{dx}{x^n}\}=\frac{d}{dx}\{x^n\}+\frac{d^2}{dx^2}\{x^n\}= n*x^{n-1}+n*(n-1)*x^{n-2}$ (線形性)であることが一般的に知られています。

入力

$N$
$d$
$S$

$N$は式を表す文字列$S$の文字数を表します。
$d$は,(微分前の)式に現れる変数xの最大の次数を表します。
$S$は式を表す長さ$N$の文字列です。$S$に空白は含まれません。

$1 \le N=|S| \le 50000$
$0 \le d \le 10$

式$S$は演算子'+','*' 、定数,変数'x',導関数"d{$T$}"が含まれます。$T$も式を表す文字列で$1\le|T|$が保証されています。
また、式中に現れる定数は1以上9以下の整数です。

一つの項に二つ以上の定数が現れることはありません。
つまり、"2*2*x"のような定数が2回以上現れる項が含まれる入力は存在しません。
"x*2"のように定数が先頭にあるとは限りません。

導関数に隣接しうる演算子は'+'のみです。
つまり、"x*d{x}"のような入力は存在しません

出力

$A_{0} \: A_{1} \: A_{2} \: ... \: A_{d-1} \: A_{d}$

式に含まれる微分を全て計算した結果$A_{0}*x^{0}+A_{1}*x^{1}+...+A_{d}*x^{d}$を求めてください。
$x_{0},x_{1},x_{2},... ,x_{d-1},x_{d}$の係数$A_{0},A_{1},A_{2},... ,A_{d-1},A_{d}$を出力してください。
計算結果の係数の値に気をつけましょう。
最後に改行してください。

サンプル

サンプル1
入力
8
2
d{x*x+x}
出力
1 2 0

$\frac{d}{dx}\{x^2+x\}=2x+1$なので、$x^0$の係数(すなわち定数)は1、$x^1$の係数は2,$x^2$の係数は0です。

サンプル2
入力
19
3
d{2*x+d{3*x*x*x}}+x
出力
2 19 0 0

微分する式の中に微分が含まれることもあります。

サンプル3
入力
1
1
x
出力
0 1

演算子が無い単項式の入力も存在します。

サンプル4
入力
59
3
x*x*x+d{x*x*x}+d{d{x*x*x}}+d{d{d{x*x*x}}}+d{d{d{d{x*x*x}}}}
出力
6 6 3 1

I hate math

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