最適戦略を一つ適当にとり，その性質を考察します．

最適戦略において，クイズ \(a,b\) をこの順に連続して回答していたとします． この戦略が最適であることから，この \(2\) 問の順番を入れ替えても得しないはずです．

これを式で書いてみます．この \(2\) 問より前，及び後ろで得る得点の期待値は変わらないので，この \(2\) 問だけを考えることができ，次のような式を得ます．（ここで，\(p_i\) は \(P_i/100\) を意味します．）

\(p_a \times (S_a + p_b \times S_b) \geq p_b \times (S_b + p_a \times S_a)\\ \iff (p_a \times S_a) \times (1-p_b) \geq (p_b \times S_b) \times (1-p_a)\)

ところで，\(p_i=1\) となるクイズは必ず正解できるため，これは最初に全て行っても損しないことが明らかです． 残りのクイズの並べ方について考えてみると，\(p_i < 1\) であることから，上の式を更に変形し，

\((p_a \times S_a) / (1-p_a) \geq (p_b \times S_b) /(1-p_b)\)

とできます． つまり，\((p_i \times S_i) / (1-p_i)\) が広義単調減少になるように並べる必要があるとわかります． このような方法は一意とは限りませんが，\((p_a \times S_a) / (1-p_a) = (p_b \times S_b) /(1-p_b)\) であるならば \(a,b\) を入れ替えても得点の期待値は変化しないため，どのような並べ方でも問題ないとわかります．

よって，上の式を元に比較関数を書いてソートを行えばこの問題を解くことができます． なお，\(p_i=1\) の場合を個別に処理せず，まとめてソートしても問題ないことも確認できます．（ただし \(S_i>0\) であることが必要です．writer は一度 \(S_i=0\) を許容することでひっかけ問題を作ろうかと思いましたが，思いとどまりました．）

計算量は \(O(N \log N)\) になります．

解答例(C++)