No.620 ぐるぐるぐるりん
タグ : / 解いたユーザー数 12
作問者 :
はむこ
/ テスター :
uwi
問題文
あなたは今、渦巻く海の中で漂流しています。
ちょうど時刻$T$で救助船が座標$(g_x, g_y)$に現れることを知っているので、そこまでなんとか泳ごうとしています。
時刻$t=T$以外の時刻では、座標$(g_x, g_y)$に自分がいたとしても救助船はそこにいないので、救助船に乗ることはできません。
今、あなたは時刻$t=0$で座標$(1, 0)$にいます。
時刻$t$で位置$(x_t, y_t)$にいるときに、そこから$1$秒間力$(u_{x, t}, u_{y, t})$で泳ぐことによって、位置$(x_{t+1}, y_{t+1})$に移動することができます。
渦の回転速度$\omega$と、渦の中心座標$(0, 0)$から外に流される速度$v$は事前にわかっています。
これらの速度によって、時刻$t+1$での座標は以下のように計算できます。
$x_{t+1} = x_t - y_t \omega + x_t v + u_{x, t}$
$y_{t+1} = y_t + x_t \omega + y_t v + u_{y, t}$
以下の動画は、$\omega = 0.3, v = 0.01$の海で全く力をかけなかった（つまり$u_{x, t} = u_{y, t}=0$）時に流される様子です。
あなたは体力が$p$しか残っていないので、あまり多くの力を出し続けることができません。
具体的には、$\displaystyle \sum_{0\le t < T}(u_{x, t}^2 + u_{y, t}^2) < p$を満たさなければ、救助船にたどり着く前に力尽きてしまいます。
$n$種類の、様々な渦の強さ・救助船の出現時刻・救助船の出現位置について、
力尽きずに救助船まで移動できるような、力のかけかたを1例ずつ、計算してください。
入力
n T p omega v g_x g_y ... T p omega v g_x g_y
$1 \le n \le 1000$
$1 \le T \le 15$, 整数
$0 \le p \le 10^9$, 小数
$-3 \le \omega, v \le 3$, 小数
$-100 \le g_x, g_y \le 100$, 小数
小数入力は小数点以下第4位まで与えられる（小数点以下第5位以降は入力されない）。
力尽きずに救助船に移動できることが保証される。
各ケースについて$p$は、Writerが見つけた$u_{x, t}, u_{y, t}$の二乗和の$101$ %以上である。
出力
各ケースで、そのケースにおける$u_{x, t}, u_{y, t}$を$T$行ずつ出力してください。
$t$行目（$0\le t < T$）には、$t\sim t+1$秒の間にかける力$u_{x, t}, u_{y, t}$をスペース区切りで出力してください。
$(x_T, y_T)$と$(g_x, g_y)$とのユークリッド距離が$10^{-4}$以下である必要がある。
$\displaystyle \sum_{0\le t < T} (u_{x, t}^2 + u_{y, t}^2) < p$である必要がある。
最後に改行してください。
サンプル
サンプル1
入力
1 5 5.5 0.5 -0.5 -1.125 2.125
出力
1 0 1 0 1 0 0 1 0 1
初め、$(x_0, y_0) = (1, 0)$です。
$x_1 = x_0 - y_0 \cdot 0.5 + x_0 \cdot (-0.5) + 1 = 1.5$
$y_1 = y_0 + x_0 \cdot 0.5 + y_0 \cdot (-0.5) + 0 = 0.5$
$x_2 = x_1 - y_1 \cdot 0.5 + x_1 \cdot (-0.5) + 1 = 1.5$
$y_2 = y_1 + x_1 \cdot 0.5 + y_1 \cdot (-0.5) + 0 = 1$
$x_3 = x_2 - y_2 \cdot 0.5 + x_2 \cdot (-0.5) + 1 = 1.25$
$y_3 = y_2 + x_2 \cdot 0.5 + y_2 \cdot (-0.5) + 0 = 1.25$
$x_4 = x_3 - y_3 \cdot 0.5 + x_3 \cdot (-0.5) + 0 = 0$
$y_4 = y_3 + x_3 \cdot 0.5 + y_3 \cdot (-0.5) + 1 = 2.25$
$x_5 = x_4 - y_4 \cdot 0.5 + x_4 \cdot (-0.5) + 0 = -1.125$
$y_5 = y_4 + x_4 \cdot 0.5 + y_4 \cdot (-0.5) + 1 = 2.125$
力$\sum_{0\le t < T} (u_{x, t}^2 + u_{y, t}^2) = 5 < 5.5$なので、力尽きずに、ちょうど時刻$T=5$で$(-1.125, 2.125)$に移動できました。
ここで、ちょうど時刻$T$であることに注意してください。
つまり、たとえ時刻$t < T$で救助船に着いたとしても、ちょうど時刻$t=T$で別の場所に移動していたら救助されません。
サンプル2
入力
1 15 10 0.9 0.1 1 0
出力
-0.5590832663553096838087753950308211869924 -0.4538251666614241209630250389883698858284 -0.1022519519779994767825093832103178215220 -0.4962290213105669546263341157521509217077 0.1654103821800548689447286215825627664344 -0.3157815248622887024281327694730236999021 0.2307696993931288061689026738787511305873 -0.0982625412804297967609258937504712605460 0.1694470081608061894849455789047176779150 0.0493088782402688876135453052707013910094 0.0703038210696261387682489546469000174511 0.1023475610935749273856364832679943788207 -0.0073161395087270862120910853640398663345 0.0870573050324732387750411265192607146446 -0.0427719445489236518612402408734407543989 0.0441477772167654059713281372578919103944 -0.0429614547024281751287882839818177416191 0.0049840618041635591964723991237340428029 -0.0256154731665434461238743755334690277436 -0.0164271491324782774210512591508970281495 -0.0066299931999826736638264240708551255921 -0.0203583118295128558297550375871809436035 0.0054601426369248197322989711588459016411 -0.0140401667784384298875424365582453845036 0.0092288648520925917442445617078217168228 -0.0052128985559520393583323588648781310440 0.0073481980384297593332336429039486347392 0.0012731633443131396118876835776845268811 0.0034342430857618008364050277148038503583 0.0039672563676555400234528814262802143276
力$\sum_{0\le t < T} (u_{x, t}^2 + u_{y, t}^2) = 1.0268684859$なので、余力$10.0$より小さい力で救助船にちょうどたどり着くことができます。
ぐるぐるぐるりん。
サンプル3
入力
4 6 9770 0.1359 -0.1674 -3.4238 90.2458 8 4359 -2.9435 -2.7331 -33.5567 72.6887 1 8317 1.4861 -1.0168 72.7476 -5.3280 7 4249 1.0773 2.4532 4.1420 -4.4472
出力
8.8610640622215729803046180279579857597128 9.1624287318977981637441176943070786364842 8.6168617587290694441806704340081068949075 12.4110740390427459851549474301179998292355 7.7108320088957468634027758724869272555225 16.1649965278016668635691077682281502347905 5.9340532901000440243154121500168685088283 20.3836588637009756136420079997151333373040 3.0498513981872338589503013128734210113180 24.9797425758913909030201061511888838140294 -1.2019824014747570554983990831487972172908 29.8059009880592431125656549539826301042922 1.5774550919225495036963061168400201950135 2.6797588212359079336537942550577895417518 0.4417259778202559507916287462325755086567 -0.7959946947792882938096763190127802545248 -0.2664219693281557105779717986582255662142 0.0067980082291050485892578748598619187149 0.0412883921536529575847460082904660794156 0.0662018199037403666051913170287335219655 0.0105682176601090039463372305394983641236 -0.0202494208188849568767417319570256495354 -0.0066781880176901074579187689295167729142 0.0003416850665363352444053868239848270605 0.0010781542029716321279275703659550345037 0.0016339864000407908900536213536724972073 0.0002520679471596301568503406542731681839 -0.0005146947256041561891137803286255802959 72.7643999272356000740380466140777571126819 -6.8140999931859000064010567498939963115845 -3.1914891398354974239026660143281333148479 -0.9961849458246479833869839459747907994824 -0.7602242579764328366540362957870513582748 -0.5256499881103495447451541544570119413038 -0.1573479273710753174257259007218223700875 -0.2013091944478191229884848911790840020331 -0.0249506562886531407013317000742613771536 -0.0660803128887944921782387347475307137756 -0.0011441418288945185628463670213239566920 -0.0194929042282700865605649109824071274488 0.0013029071067033701106056831076074331577 -0.0052384114450990508244504484380854592018 0.0007751175941197825311479441268147638766 -0.0012751587134330459073761065980079365545
それぞれのケースについて$6, 8, 1, 7$行出力するので、合計で$22$行出力することになる。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。