王国全土で、葡萄酒を量る単位を一つとする。
- 『マグナ・カルタ』(1215 年) 第35条
あなたは王国の度量衡を整備する役人です。王国では誰もがポンドで重さを量りますが、各都市が昔から使ってきたポンドの分銅の重さは互いに異なります。商人たちは使い慣れた分銅を使い続け、都市ごとに取引の慣習も異なるため、度量衡の統一は容易ではありませんでした。
王室はこの違いを調べるため、王室に保管されている小さな基準分銅をもとに定めた単位であるグレーンを使いました。各都市のポンドの分銅をこの基準と比較し、その都市の ポンドが何グレーンに相当するかを確認しました。続いて、都市間の交易で共通して使う新たな重さの単位を定めるため、別の標準分銅を各都市に送り、測定記録を集めました。
各都市は標準分銅が何ポンドかを記録し、 ポンド未満の端数は切り捨てました。ところが、都市を巡っていた標準分銅が運搬中に紛失し、直接確認できなくなりました。さらに、報告された記録の一部には誤記があるようです。王室の基準分銅と各都市のポンドの分銅は残っているので、あなたは確認済みのポンドの重さをもとに記録を照合しようとしています。
個の測定記録が与えられます。都市 の ポンドは グレーンで、その都市では分銅を ポンドと記録しました。分銅の実際の重さは、グレーンで表すと正の整数です。正しい記録には、上記の切り捨て以外に測定誤差がないものとします。
最初の行に測定記録の個数 が与えられます。
続く 行のうち 行目に、 と が空白区切りで与えられます。
除外しなければならない記録の最小個数を出力してください。
最初の例では、分銅が グレーンなら、最初の都市では ポンド、2 番目の都市では ポンドと記録します。3 番目の記録を除外すれば、残りの 2 個の記録はともに正しい可能性があります。3 個の記録がすべて同時に正しい可能性はありません。
2 番目の例では、分銅が グレーンなら、最初の都市では ポンドと記録しなければなりません。2 個の記録がともに正しい可能性はないので、片方を除外する必要があります。
残った記録がすべて同時に正しい可能性があるようにするため、除外しなければならない記録の最小個数を求めてください。必要なら、すべての記録を除外してもかまいません。
3 番目の例では、分銅が グレーンなら、両方の記録が正しくなります。
4 番目の例の記録が正しいのは、分銅の実際の重さが グレーンのときだけです。実際の重さは正の整数でなければならないので、この記録を除外する必要があります。
