← 返回题目列表

AtCoder · joisc2012_fortune_telling

fortune_telling. 算命

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

以下是来自日本的官方日本新闻原版PDF,已完整保存并按原样染色。

占い - 原题 PDF 第 1 页
原题PDF第1页
占い - 原题 PDF 第 2 页
原题PDF第2页
占い - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                    Contest Day 3 – Fortune Telling

                     占い(Fortune Telling)



 K 理事長は占いが好きで,いつも様々な占いをしている.今日はカードを使って今年のIOI での日本選
手団の出来を占うことにした.
 占いの方法は次のようなものである.

   • まずカードを縦M 行,横N 列の長方形状に全て表にして並べる.
   •  i = 1, · · · , K について,「上から数えてAi 行目からBi 行目かつ,左から数えてCi 列目からDi 列目に
   ある全てのカードの表裏をひっくり返す」という操作を行う.すなわち,上からa 行目で左からb 列
   目にあるカードを(a, b) と書いたとき,各i について,Ai ≦a ≦Bi かつCi ≦b ≦Di をみたすカード
       (a, b) を全てひっくり返す操作を行う.

   • 操作が終わった後,表になっているカードの枚数によって占いの結果が出る.
 K 理事長は途中でカードをひっくり返す回数があまりに多いことに気付いたので,カードを実際に使っ
て占うのはやめて,操作が終わった後に表になっているカードの枚数だけを求めることにした.


課題

 行の長さM,列の長さN,操作の回数K およびK 回の操作の指示が与えられたとき,操作後に表になっ
ているカードの枚数を求めるプログラムを作成せよ.


制限

   1 ≦M ≦1 000 000 000 (= 109) 行の長さ
   1 ≦N ≦1 000 000 000 (= 109) 列の長さ
   1 ≦K ≦100 000 (= 105)    操作の回数


入力

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

   • 1 行目には整数M, N, K が空白を区切りとして書かれており,カードがM 行N 列に並んでいること
   と,操作を行う回数がK 回であることを表す.

   • 1 + i 行目(1 ≦i ≦K) には4 つの整数Ai, Bi,Ci, Di (1 ≦Ai ≦Bi ≦M, 1 ≦Ci ≦Di ≦N) が書かれており,
         i 回目の操作は上からAi 行目からBi 行目かつ,左からCi 列目からDi 列目のカードを全てひっくり
   返すことを表す.




                         占い– 1 / 3

Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                    Contest Day 3 – Fortune Telling


出力

 標準出力に,K 回の操作後に表になっているカードの枚数を1 行で出力せよ.


採点基準

 採点用データのうち,配点の30%分については,K ≦3 000 を満たす.


入出力例

  入力例1        出力例1
   6 5 3                11
   2 4 1 4
   4 6 3 5
   1 2 3 5

 この例では,K = 3 回の操作は以下のように行われる.
 表のカードを□,裏のカードを■で表すと,


                     初期状態
                     □□□□□
                     □□□□□
                     □□□□□
                     □□□□□
                     □□□□□
                     □□□□□
                       ↓
                     □□□□□
                     ■■■■□
                     ■■■■□
                     ■■■■□
                     □□□□□
                     □□□□□
                       ↓
                     □□□□□
                     ■■■■□
                     ■■■■□
                     ■■□□■
                     □□■■■
                     □□■■■



                         占い– 2 / 3

Japanese Olympiad in Informatics 2011/2012
                                                           Spring Training Camp/Qualifying Trial
                                               March 19–25, 2012, Komaba/Yoyogi, Tokyo

                                                                    Contest Day 3 – Fortune Telling



                       ↓
                     □□■■■
                     ■■□□■
                     ■■■■□
                     ■■□□■
                     □□■■■
                     □□■■■
                     最終状態

最終状態で表になっているカードの枚数11 を出力する.





                         占い– 3 / 3