BoB004-C: Alchemist 1

2 secs 1024 MB
kyaneko999's icon kyaneko999

解説

錬金術を行う順序は,以下の 33 通りしか有り得ないことが分かります.

  • A,BA,B に対して錬金術を試す.もし錬金術が行われたならば,新たに生成された A+B2\frac{A+B}2CC に対して錬金術を試す.
  • B,CB,C に対して錬金術を試す.もし錬金術が行われたならば,新たに生成された B+C2\frac{B+C}2AA に対して錬金術を試す.
  • C,AC,A に対して錬金術を試す.もし錬金術が行われたならば,新たに生成された C+A2\frac{C+A}2BB に対して錬金術を試す.

これら 33 通りの順序で行った時の錬金術の最大回数を求めれば良いです.

解答例(Python)

なお,偶奇に着目して問題を解くこともできます.
A,B,CA,B,C がすべて偶数または奇数の時,11 回目は 44 で割った余りが等しい数に対して錬金術を行うことで,22 回目の錬金術を行うことができます.
鳩の巣原理より A,B,CA,B,C のうち少なくとも 22 つは 44 で割った余りが等しいので,答えは必ず 22 になります.
A,B,CA,B,C の中に偶数と奇数がともに存在する時,11 回目は偶奇が等しい数に対してのみ錬金術を行うことができるので,対象となる数は一意に定まります.
22 回目に関しては,11 回目の錬金術で生成された数と残った数について錬金術が可能であるかを調べれば良いです.

解答例(Python)