No.2227 King Kraken's Attack
タグ : / 解いたユーザー数 85
作問者 : 👑



問題文
行 列のマス目があり, 行 列目のマスをマス と表します.そのマス目内全てのマスに, 体ずつモンスターがいます.
モンスターは,横攻撃と縦攻撃の2種類の攻撃の両方をそれぞれ 回以上当てれば倒すことができます.片方の攻撃を当てるだけでは,倒すことはできません.
さて,これから,モンスターへの攻撃手段として次に示す2種類のパンチをそれぞれ 回以上の好きな回数繰り出すことができます.この2種類のパンチ以外の攻撃手段でモンスターに攻撃することはできません.
- 横パンチ: を満たす整数 をひとつ選ぶ. 行目から 行目までの連続する 行の全てのマスにいるモンスター全てに対して横攻撃を行う.その後,好きなマスを マス選び,選んだ全てのマスにいるモンスター全てに対して横攻撃と縦攻撃の両方を行う.
- 縦パンチ: を満たす整数 をひとつ選ぶ. 列目から 列目までの連続する 列の全てのマスにいるモンスター全てに対して縦攻撃を行う.その後,好きなマスを マス選び,選んだ全てのマスにいるモンスター全てに対して横攻撃と縦攻撃の両方を行う.
マス目内のモンスターを全て倒すために必要なパンチの回数の最小値を求めてください.すなわち,モンスターを全て倒すのに横パンチを 回,縦パンチを 回使ったとするとき, の最小値を求めてください.
制約
- 入力はすべて整数である.
入力
入力は以下の形式で標準入力から与えられる.
出力
答えを出力せよ.
サンプル
サンプル1
入力
2 2 1 1 1 2
出力
2
次のように攻撃することで, 回のパンチで全てのモンスターを倒すことができます.
- 横パンチを行い, 行目のモンスターに対して横攻撃を行う.その後,マス のモンスターに縦攻撃と横攻撃の両方を行う.
- 縦パンチを行い, 列目のモンスターに対して縦攻撃を行う.その後,マス とマス のモンスターに縦攻撃と横攻撃の両方を行う.
回以下のパンチでは全てのモンスターを倒すことはできないため,これが最小回数です.
サンプル2
入力
3 3 1 1 0 0
出力
6
縦パンチ・横パンチをそれぞれ 回ずつ繰り出さないと,全てのモンスターを倒すことができません.
サンプル3
入力
3 3 1 1 9 9
出力
1
縦パンチか横パンチのどちらかを 回繰り出すだけで全てのモンスターを倒すことができます.
サンプル4
入力
1000 9982 4 4 35 3
出力
2742
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。