世界征服を企む悪の組織、なんてものは、古今東西フィクションノンフィクションを問わず、いろんな所にいるものだが、一体彼らは何のために世界征服をしようとしたのだろうか。そんなことをふと考えてしまうのは、私もまた、世界征服を企てているからであった。私が世界征服を目論む理由はただ一つ、私がロボット工学の分野で世界一優秀であることを世界に示すためである。征服したあとの世界になど興味はない、そこらへんの犬にでもくれてやっても構わないのだ。
誠に遺憾だが、それはつまり、私よりも優秀であるとされている研究者がいる、ということだ。その人物には心当たりがある。誰あろう、私の学生時代の同期 R 博士である。彼の実績は認めるが、しかし私のそれより優れていたとは思わない。ただ彼は、平和のためのロボット利用などという甘っちょろいことを言っていたがために、教授連中の受けが良かったのだ。主席こそ逃したものの、本当は私の方がずっと優秀なのだ。
その優秀さを示す端的な例が、この世界征服のために用意した戦闘ロボットである。戦闘ロボットはその特性に応じた専用の武器を持ち、その武器はチップに収められているが、このチップは強力な互換性を持つ。ただ開発者自身の他の戦闘ロボットと互換性をもつだけではない (その程度のことは、他ならぬ R 博士が既に達成している) 。私のチップのすごいところは、その R 博士の家事手伝いロボットとも互換性があるのだ。その家事手伝いロボットは非売品のワンオフモデルなので、私はそのロボットの設計を知らないで互換チップを開発したのだ。我ながら神業と言わざるを得ない。この仕様を敵が利するだけの無駄な仕様と言う人もいるが、それは愚かな考え方だ。私は私の優秀さを示すために戦闘ロボットを開発しているのだ。ただ勝てばいいというものではないのである。
世界征服計画に話を戻そう。私は n 機の戦闘ロボットを製作し、それぞれに異なる武器チップを 1 つずつインストールした。これを用いて世界の主要施設を奪取するつもりだが、この計画を阻むために R 博士は彼の家事手伝いロボットを送り込んでくることだろう。家事手伝いロボットは自身の武器で私の戦闘ロボットに戦闘を挑んでくるが、1 回の戦闘には 1 単位時間かかり、戦闘の結果どちらか片方のロボットが敗北し破壊される。
戦闘の結果私のロボットが破壊された場合、そのロボットの武器チップは相手に奪われることになる。ある私のロボットの武器チップは他の私のロボットのうちの 1 機の弱点になっていて、またどの私のロボットも弱点となる武器チップをただ 1 つだけ持つ。私は私の各ロボットについて、相手がそのロボットの弱点武器を持っていた場合の敗北確率・持っていなかった場合の敗北確率をそれぞれ見積もることができる。
戦闘の結果相手の家事手伝いロボットが破壊された場合、R 博士はスペアボディ転送システムによって同じ家事手伝いロボットを送り込んでくる。このとき、相手のロボットが既に得ていた武器チップは失われることがない。R 博士は無制限にスペアボディ転送システムを使用してくるが、その隙に私は私の戦闘ロボットを修理することができるので、何度戦っても先に説明した敗北確率は変化することはない。また、スペアボディ転送システムは家事手伝いロボットが破壊されたときに破壊された場所でしか使えないので、家事手伝いロボットは敗北した直後に別の私の戦闘ロボットに挑むことはできない。
R 博士は無制限にスペアボディ転送システムを使えるのだから、悔しいが n 機の戦闘ロボットが全て破壊されるのは時間の問題だ。そこで私は戦闘ロボットを戦わせている裏で、スペアボディ転送システムごと破壊できるようなさらなるロボットの開発に勤しむつもりだ。しかし、私には一体どれだけの時間が残されているのだろうか。R 博士のロボットが最も早く私の n 機のロボットを撃破するような戦略を取ったとき、どれだけの時間がかかるだろうか。まずはそれを計算しなければなるまい。ついでに、そのようなロボットの撃破順序が何通りあるかも確認しておきたい。
入力は複数のケースからなる。 各ケースは以下のフォーマットで与えられる。
n p0 id0 w0 p1 id1 w1 . . . p1 idn-1 wn-1
pi は弱点の武器を相手が持っていない時にi 番目の戦闘ロボットが敗北する確率を表す。
idi はi 番目の戦闘ロボットの弱点となる武器を持っている戦闘ロボットを表す。
wi は弱点の武器を相手が持っている時にi 番目の戦闘ロボットが敗北する確率を表す。
入力の終わりはn = 0によって与えられる。
各値は以下の条件を満たす
2 ≤ n ≤ 100
pi と wiは小数点以下3桁の数で表される。
0.001 ≤ pi < wi ≤ 1.000
idi != i
テストケースの数は500を超えない。
n体の戦闘ロボットが撃破されるまでの時間の期待値と、その撃破順序の組み合わせの数を100000007で割った余りを空白で区切って出力せよ。
期待値の値はジャッジの用意した回答との誤差1e-9までが認められる。
4 0.200 3 0.500 0.100 0 0.400 0.900 1 1.000 0.400 2 0.600 2 0.600 1 0.800 0.500 0 1.000 9 0.200 7 0.600 0.400 0 0.500 0.700 8 1.000 0.100 4 0.400 0.200 2 0.600 0.100 6 0.400 0.100 5 0.400 0.600 3 0.900 0.500 1 0.900 9 0.300 8 0.900 0.700 3 0.800 0.300 0 0.900 0.700 6 0.800 0.200 5 0.700 0.200 2 0.700 0.700 4 0.800 0.700 1 0.800 0.300 7 0.900 0
7.27777777778 1 2.66666666667 1 23.98412698413 72 11.36904761905 4
The University of Aizu Programming Contest 2011 Summer
原案: Tomoya Sakai
問題文: Takashi Tayama