← 返回题目列表

AtCoder · joi2009ho_e

E. 认证级别

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存并染色。

認証レベル - 原题 PDF 第 1 页
原题PDF第12页
認証レベル - 原题 PDF 第 2 页
原始PDF第13号
認証レベル - 原题 PDF 第 3 页
原始PDF第14号
可复制的 PDF 提取文本
5                   認証レベル 


問題
 あなたはJust Odd Inventions 社を知っているだろうか? この会社の業務は「ただ奇
妙な発明(just odd inventions)」をすることである.ここでは略してJOI 社と呼ぶ.
  JOI 社には2 つの事務所があり,それぞれ同じ大きさの正方形の部屋がマス目状に
並んでできている.辺で接しているすべての部屋の間に,身分証による認証機能の
付いた扉がある.JOI 社では様々なレベルの機密情報を扱っているため,部屋ごとに
機密レベルという正の整数が設定されており,身分証の事務所ごとに定められた非
負整数の認証レベルが,機密レベル以上でないとその部屋に入室することができな
い.各事務所の出入り口は唯一あるエレベーターホールのみで,エレベーターホー
ルの部屋の機密レベルは最低の1 である.その事務所についての認証レベルが0 の
ときはエレベーターホールに入ることさえできない.
  JOI 社では,社長の突発的な提案で,一般の人に社内を見学してもらうツアーを実
施することになった.あなたは見学者に渡す身分証の認証レベルの組み合わせを決
める必要がある.見学者は開けられる扉を見つけると必ず開けて中に入る(同じ部屋
を何度も訪れることも可能である).そのため,必要以上に見学者の身分証の認証レ
ベルを高くしたくはない.しかし,ツアーに魅力を持たせるため,ツアーではエレ
ベーターホールの部屋を含め2 つの事務所であわせてR 個以上の部屋を訪れること
ができるようにする必要がある.身分証の認証レベルを低くしすぎると,この条件
を満たすことができないかもしれない.
  JOI 社には事務所が2 個あり,第k 事務所(k = 1, 2) の部屋は東西方向にWk 個,南
北方向にHk 個並んでおり,全部でWk × Hk 個ある.西からi 番目,北からj 番目の
部屋を(i, j)k で表すことにする.
  Wk とHk とR の値,エレベーターホールの位置(Xk, Yk)k ,各部屋の機密レベルが
与えられたとき,見学者が2 つの事務所であわせてR 個以上の部屋を訪れることが
できるための,見学者の身分証の認証レベルの和の最小値を求めるプログラムを作
成せよ.
 なお,JOI 社が「ただ奇妙な発明」をすることでどうやって利益を得ているかは,
社内でも最高機密であり社長以外の誰も知らない.





                       問題5-1

入力

 入力ファイルのファイル名はinput.txt である.
  1 行目には正整数R (1 ≦R ≦100000) が書かれている.2 行目以降には,2 つの事
務所のデータが順に与えられる.
 事務所のデータは,最初の行に正整数Wk, Hk, Xk, Yk (1 ≦Xk ≦Wk ≦500, 1 ≦Yk ≦
Hk ≦500) ,続くHk 行のj 行目のi 番目に,部屋(i, j)k の機密レベルを表す整数Lk,i,j
(1 ≦Lk,i, j < 100000000 = 108) として与えられる.
 また,R ≦W1 × H1 + W2 × H2 を満たす.
 採点用データのうち, 配点の30% 分については, R, Wk, Hk ≦100 を満たす.


出力

 出力ファイルのファイル名はoutput.txt である.
  output.txt は,求める身分証の認証レベルの和の最小値のみを含む1 行からなる.


入出力の例
  例1             例2             例3
   input.txt               input.txt               input.txt

       5                       8                       6
       2 2 1 2                 5 4 1 3                 3 3 2 2
       9 5                     5 5 4 5 5               2 9 2
       1 17                    8 2 1 9 7               9 1 9
       3 2 2 1                 1 1 3 5 1               2 9 2
       6 1 20                  7 2 7 1 3               2 2 1 1
       8 18 3                  6 5 6 2                 1 3
                                2 3 5 8 2 7             5 7
                                1 6 9 4 5 1
   output.txt
                                2 4 5 4 2 2
                                                    output.txt
                                5 4 2 5 3 3       15
                                7 1 5 1 5 6                                                        9


                           output.txt

                                4



                       問題5-2

入出力の例の説明
 例1 では,見学者に渡す身分証の認証レベルを,事務所1 の認証レベルが9,事務
所2 の認証レベルが6 となるように設定すると,見学者は5 個の部屋(事務所1 の部
屋(1, 1)1, (1, 2)1, (2, 1)1 と,事務所2 の部屋(1, 1)2, (2, 1)2) を訪れることができる.こ
のとき,認証レベルの和は15 となる.これが合計5 個以上の部屋を訪れることがで
きるための認証レベルの和の最小値である.

                      9   5                 6   1  20
                      1  17                 8  18  3

            事務所1         事務所2
            (認証レベル9)       (認証レベル6)

 例3 では,見学者に渡す身分証の認証レベルを,事務所1 の認証レベルが9,事務
所2 の認証レベルが0 となるように設定すると,見学者は9 個の部屋(事務所1 の部
屋(1, 1)1, (1, 2)1, (1, 3)1, (2, 1)1, (2, 2)1, (2, 3)1, (3, 1)1, (3, 2)1, (3, 3)1) を訪れることがで
きる.事務所2 の部屋は1 個も訪れることができない.(エレベーターホール(1, 1)2
にすら入ることができない.) このとき,認証レベルの和は9 となる.これが合計6
個以上の部屋を訪れることができるための認証レベルの和の最小値である.

                     2   9   2
                                               1   3
                     9   1   9
                                               5   7
                     2   9   2

            事務所1         事務所2
            (認証レベル9)        (認証レベル0)





                       問題5-3