n回以下の試行でPd%の勝率、それを含めて全体でPg%の勝率となるような場合はあり得るか判定せよ的な問題。
D回の試行でDw回勝ち、Dl=D-Dw回負け、全体G回でGw回勝ち、Gl=G-Gw回負けるとする。
n回以下の制約より、Dを最小化したい。
Dw/D = Pd/100なので、約分すればよく、D=100/GCD(100,Pd)、Dw=Pd/GCD(100,Pd)とすればよい。
この時点でD>nとなっていたらBroken確定。
次に、全体を考えると、G>=D, Gw>=Dw, Gl>=Dlであればよい。
G,Gw,Glの最小値をPdと同様に求めれば、それをk倍しても全体の割合は一致する。
しかし、これらは全て左辺に登場し、">="なのでG,Gw,Glが0で無ければ充分大きいkを取り、G>=D, Gw>=Dw, Gl>=Dlを満たす事が出来る。
また、G!=0や、Gw=0⇔Pd=0、Gl=0⇔Pd=100を用いれば、解になる。
上記のD>nまでは開始10分でたどり着き、Gはk倍すればいいとまで解った物の条件の一行でバグを生みB問題へ逃げるという情けなさ。
ACしたコードは以下
n,pd,pg=getia d = 100 / pd.gcd(100) dw = pd / pd.gcd(100) dl = d - dw g = 100 / pg.gcd(100) gw = pg / pg.gcd(100) gl = g - gw if d > n "Broken" else if (gw == 0 && dw != 0)||(gl == 0 && dl != 0) "Broken" else "Possible" end end
最後の変形に気付きながらも、どうせ計算量余裕ってレベルじゃないのでほうっておいた。