yukicoder No.169, 170, 171
ボーナスステージだった
問題はこちら。
No.169 何分かかるの!?
あるデータのコピーがK%まで進んでいて残り時間がS分である。全体のコピーにかかる時間を小数切り捨てで答えよ。
解法
小数が出てくると誤差の問題が出てくるので整数の範囲で計算を終わらせる。分母分子を100倍して計算を行っていけばいい。
K = int(raw_input()) S = int(raw_input()) print 100*S/(100-K)
No.170, 171 スワップ文字列(Easy), (Med)
英大文字からなる文字列Sが与えられる。となりあう文字通しをスワップしていったとき、S以外の文字列を何種類作ることができるか答えよ。(Easy N ≦ 8, Med N ≦ 1000)。
解法
となりあう文字をスワップできるなら任意の文字列を作ることができる。
長さLの文字列があり、各アルファベットがそれぞれN1,N2,N3,...個あった時、作ることのできる文字列の種類はL!/(N1! N2! N3! ... )である。 多倍長に対応してるならそのまま計算してしまえばいい(No.170なら最後の%573を取り除く)。
def fact(n): res = 1 while n > 0: res *= n n -= 1 return res S = raw_input() hist = [0]*26 pfor s in S: hist[ord(s)-ord("A")] += 1 ans = fact(len(S)) for i in hist: ans /= fact(i) print (ans-1)%573