7

Google Code Jam でブルズアイに関する問題を読みました。（コンテストはもう終わったので、話しても大丈夫です）

ここに画像の説明を入力

マリアは t ミリリットルの黒い絵の具から始めます。これを使って、厚さ 1 cm (1 センチメートル) の輪を描きます。厚さ 1cm のリングは、半径が 1cm 異なる 2 つの同心円の間のスペースです。

Maria は、半径 r cm の白い円の周りに最初の黒いリングを描きます。

半径1cmの円盤の面積はπcm2です。面積 π cm2 を覆うには 1 ミリリットルの塗料が必要です。マリアが描ける黒い輪の最大数は?

紙の上での私の計算では、円周率の倍数として、内側半径 r の n 個のリングでブルズアイを描くためのペイントの領域は次のとおりです。2*n**2 + n*(2*r-1)

t*piしたがって、1 ミリリットルの塗料が与えられた場合、問題は となるような最大の n を見つけることf(n,r) <= tです。

今朝、バイナリ検索で解決しましたhttps://github.com/hickford/codejam/blob/master/2013/1A/bullseye/bu​​llseye.py

私は浮動小数点の不正確さに非常に警戒しているので、二次方程式ではなく二分探索を選択しました — この問題では、t と r は 10**18 の大きさの整数です)。以前の Code Jam で算数の不正確さに悩まされました。

しかし、私は興味があります。二次方程式を補強して、大きな整数係数を持つ方程式の正しい答えを与えることができますか? Sympy や Numpy のような数学ライブラリは私に何か提供してくれますか?

二次方程式が大きな入力に対して間違った答えを与えることのデモ。たとえば、r=308436464205151562とt=1850618785230909388. 解く二次方程式は

2*n**2 + 616872928410303123*n -1850618785230909388 <= 0

すなわち。係数は

a = 2
b = 616872928410303123
c = -1850618785230909388

Python でのコンピューティング

    > int((-b + math.sqrt(b**2 - 4*a*c)) / (2*a))
    0

これは間違った答えです！正解（二分探索で見つけたもの）は 3

>>> n = 3
>>> 2*n**2 + 616872928410303123*n -1850618785230909388 <= 0
True
4

4 に答える 4

2

シンボリックな正確な操作には、sympyがあります。

以下を貼り付けた場合：

a, b, c = 2, 616872928410303123, -1850618785230909388
x = Symbol('x')
int(max(solve(a*x**2 + b*x + c, x)))

ここでは、3 を取得します。

[次のOPコメントを編集]。

于 2013-04-27T14:15:38.190 に答える
1

丸め精度はこの問題で私を殺しました...しかし、すべてを64ビットの整数精度に保ち、結果の二次方程式で二分探索を行うことができました。ここで私のアプローチの概要を説明しました。

于 2013-04-27T19:28:11.283 に答える
0

(t / r^2) > 10000経由で計算する場合sqrt。0 から開始して 1 ずつ増加するたびに試行する
場合。(t / r^2) < 10000n

于 2013-04-27T14:22:21.730 に答える