1/30 PKU
2724 Purifying Machine
2^N個のチーズを持っている人がいて、チーズにウイルスが感染したのを取り除く機械がある。この機械では、1つのチーズもしくは、チーズの番号の2進数表記において異なる桁が1つしかないような2つのチーズをきれいにできる。今、機械が感染していたせいで、いくつかのチーズが感染してしまった。感染したチーズに対して操作を行うときれいになるが、きれいなチーズに対して操作を行うと逆に感染してしまう。最短の操作回数を求めよ。
二部グラフの最大マッチングやるだけ
2728 Desert King
砂漠にいくつかの町があり、それらを結ぶ全域木を作ろうとしている。辺のコストは、町の標高差である。全域木において、(コストの合計)/(水平距離の合計)を最小にしたい。この最小値を求めよ。