← 返回题目列表

AtCoder · joisc2011_ioi

ioi. 国际信息奥林匹克竞赛 (IOI)

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

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

国際情報オリンピック (IOI) - 原题 PDF 第 1 页
原题PDF第1页
国際情報オリンピック (IOI) - 原题 PDF 第 2 页
原题PDF第2页
国際情報オリンピック (IOI) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2010/2011
                                                                                    Qualifying Trial
                                                             April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                           Contest Day 1 – Banner

                      横断幕(Banner)


  20XX 年,ついにIOI がJOI 国で開催されることになった.JOI 国ではこれを祝い,街中に歓迎の横断幕
(banner) をかけることにした.JOI 国では,図のように,東西方向に走るH 本の道路と,南北方向に走る
W 本の道路が碁盤目状に通っている.東西方向に走る道路と南北方向に走る道路が交わるところを交差点
と呼ぶ.北からa 番目,西からb 番目の交差点を(a, b) で表す.
 各交差点にはそれぞれ柱が1 本ずつ立っている.JOI 国には国を象徴する色が黒色・灰色・白色の3 色あ
り,各柱はこの3 色のうちのどれか1 色で塗られている.

                                              (1, 1)     (1, 2)     (1, 3)     (1, 4)


                                              (2, 1)     (2, 2)     (2, 3)     (2, 4)


                                              (3, 1)     (3, 2)     (3, 3)     (3, 4)
            図: JOI 国の図(H = 3, W = 4 の場合).図の上が北,左が西に対応する.

 横断幕はこれらの柱を支柱としてかけることができる.ただし,横断幕が道路でないところを通ってい
ると邪魔になってしまう.そこで,交差点に立っているこれらの柱のうち,「各辺がいずれかの道路と平行
であるような長方形」の4 頂点となっているような異なる4 本の柱を選び,その周囲に横断幕をかける.さ
らに,このとき選ぶ4 本の柱に黒色の柱・灰色の柱・白色の柱がそれぞれ1 つ以上含まれているようにし
たい.
 このような4 本の柱の選び方は何通りあるだろうか.


課題

  H, W と,JOI 国に立っている柱の色の情報が与えられたとき,4 本の柱の選び方の数を出力するプログ
ラムを作成せよ.


制限

   2 ≦H ≦400 東西に走る道路の本数
   2 ≦W ≦400 南北に走る道路の本数


入力

 標準入力から以下の入力を読み込め.



                        横断幕– 1 / 3

Japanese Olympiad in Informatics 2010/2011
                                                                                    Qualifying Trial
                                                             April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                           Contest Day 1 – Banner


   • 1 行目には整数H, W が空白を区切りとして書かれている.

   • 続くH 行には,JOI 国の交差点に立っている柱の色の情報が書かれている.i + 1 行目(1 ≦i ≦H) に
    は,0, 1, 2 いずれかの整数がW 個空白区切りで書かれている.i + 1 行目のj 番目に書かれている整
   数が0 なら,交差点(i, j) に立っている柱が黒色であることを表し,同様に,書かれている整数が1
   なら灰色,2 なら白色であることを表す.


出力

 標準出力に,4 本の柱の選び方の数を1 行で出力せよ.


採点基準

 採点用データのうち,配点の40%分については,H ≦100 かつW ≦100 を満たす.


入出力の例

 入力例         出力例

 3 4                  12
 0 1 0 2
 1 2 0 1
 0 0 2 1

 この入力例では,4 本の柱の選び方として

   • (1, 1), (2, 1), (2, 2), (1, 2)

   • (1, 1), (2, 1), (2, 4), (1, 4)

   • (1, 2), (2, 2), (2, 3), (1, 3)

   • (1, 3), (2, 3), (2, 4), (1, 4)

   • (1, 1), (3, 1), (3, 4), (1, 4)

   • (1, 2), (3, 2), (3, 3), (1, 3)

   • (1, 2), (3, 2), (3, 4), (1, 4)

   • (1, 3), (3, 3), (3, 4), (1, 4)

   • (2, 1), (3, 1), (3, 2), (2, 2)

   • (2, 1), (3, 1), (3, 3), (2, 3)


                        横断幕– 2 / 3

Japanese Olympiad in Informatics 2010/2011
                                                                                    Qualifying Trial
                                                             April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                           Contest Day 1 – Banner


   • (2, 2), (3, 2), (3, 4), (2, 4)

   • (2, 3), (3, 3), (3, 4), (2, 4)

の12 通りが存在するので12 を出力する.





                        横断幕– 3 / 3