第１０回日本情報オリンピック予選（過去問）

A - 合計時間 (Total Time)

Time Limit: 10 sec / Memory Limit: 256 MB

配点： 100 点

問題

太郎君は 3 カ所の店を訪ねることを日課にしている．家を出発し，決まった順番で 3 カ所の店を回った後，家に帰る．ときどき，ストップウォッチを使って，各区間を移動するのに何秒かかったかを計り，その秒数を記録する．

ある日の計測結果が与えられたとき，この日の移動時間の合計が何分何秒かを求めるプログラムを作成せよ．

入力

入力は 4 行からなり，1 行に 1 つずつ正の整数が書かれている．
1 行目の整数は家から 1 つ目の店までの移動時間を表す秒数である．
2 行目の整数は 1 つ目の店から 2 つ目の店までの移動時間を表す秒数である．
3 行目の整数は 2 つ目の店から 3 つ目の店までの移動時間を表す秒数である．
4 行目の整数は 3 つ目の店から家までの移動時間を表す秒数である．ただし，与えられる入力データにおいては合計移動時間は 1 分 0 秒以上で 59 分 59 秒以下であることが保証されている．

出力

出力は 2 行からなる．x 分 y 秒 (1 \leqq x \leqq 59，0 \leqq y \leqq 59) のとき，1 行目に x を，2 行目に y を出力せよ．

入力例 1

出力例 1

3
43

入出力例 1 では，合計時間が 31 + 34 + 7 + 151 = 223 秒つまり，3 分 43 秒である．

入力例 2

出力例 2

44
2

入出力例 2 では，合計時間が 2\,642 秒つまり，44 分 2 秒である．

入力例 3

出力例 3

1
0

入出力例 3 では，合計時間が 60 秒つまり，1 分 0 秒である．

B - 指輪 (Ring)

Time Limit: 10 sec / Memory Limit: 256 MB

配点： 100 点

問題

あなたは N 個の指輪を持っている．どの指輪にも，アルファベットの大文字 10 文字からなる文字列が刻印されている．指輪には文字列の最初と最後がつながった形で文字が刻印されている．指輪に刻印された文字列を逆順に読む心配はない．

探したい文字列が与えられたとき，その文字列を含む指輪が何個あるかを求めるプログラムを作成せよ．

入力

入力は 2 + N 行からなる．

1 行目には，1 文字以上 10 文字以下のアルファベットの大文字からなる探したい文字列が書かれている．

2 行目には，指輪の個数 N (1 \leqq N \leqq 100) が書かれている．

2+i 行目 (1 \leqq i \leqq N) には，i 個目の指輪に刻印されている 10 文字からなる文字列が書かれている．

出力

探したい文字列を含む指輪の個数を表す整数を 1 行で出力せよ．

入力例 1

ABCD
3
ABCDXXXXXX
YYYYABCDXX
DCBAZZZZZZ

出力例 1

入力例 2

XYZ
1
ZAAAAAAAXY

出力例 2

入力例 2 の指輪には XYZという文字列が 1 つ含まれている．これは，指輪の文字列の最初と最後がつながっているためである．

入力例 3

PQR
3
PQRAAAAPQR
BBPQRBBBBB
CCCCCCCCCC

出力例 3

入力例 3 の 1 個目の指輪には PQR という文字列が 2 つ含まれており，2 個目の指輪には PQR という文字列が 1 個含まれており，3 個目の指輪には PQR という文字列が含まれていない．そのため PQR という文字列が含まれている指輪の数は 2 個となる．

C - タイル (Tile)

Time Limit: 10 sec / Memory Limit: 256 MB

配点： 100 点

問題

JOI 高校では，1 \times 1 の正方形のタイルを使って N \times N の正方形の壁画を作り，文化祭で展示することになった．タイルの色は，赤，青，黄の 3 種類である壁画のデザインは次の通りである．まず，最も外側の周に赤のタイルを貼り，その内側の周に青のタイルを貼る．さらにその内側の周に黄色のタイルを貼る．これを N \times N の正方形が埋め尽くされるまで繰り返す．用いるタイルの色は，一番外側の周から順番に赤，青，黄，赤，青，黄，\ldots である．

文化祭が近づいてきたある日，壁画のうち K 枚のタイルがはがれていることが判明した．そこで，新しいタイルを購入して，はがれた箇所に新しいタイルを貼ることにした．

入力として壁画の一辺の長さ N と，はがれたタイルの枚数 K，K 枚のはがれたタイルの位置が与えられたとき，はがれたタイルの色を求めるプログラムを作成せよ．

例えば，N = 11 の場合，11 \times 11 の壁画のデザインは下図の通りである．

また，N = 16 の場合，16 \times 16 の壁画のデザインは下図の通りである．

入力

入力は全部で 2 + K 行からなる．1 行目には，壁画の一辺の長さ N (1 \leqq N \leqq 1\,000\,000\,000 = 10^9) が，2 行目には，はがれたタイルの枚数 K (1 \leqq K \leqq 1000) が書かれている．2 + i 行目 (1 \leqq i \leqq K) には，2 つの整数 a_i と b_i (1 \leqq a_i \leqq N, 1 \leqq b_i \leqq N) が空白区切りで書かれており，i 枚目のはがれたタイルが，左から a_i 列目，上から b_i 行目のタイルであることを表す．

入力の 3 行目から 2 + K 行目には同じタイルを表す行が重複して現れることはない．また，与えられる入力データの 40 %では，N \leqq 1\,000 をみたしている．

出力

出力は K 行からなる．各行は 1 つの整数からなり，i 行目 (1 \leqq i \leqq K) の整数は，i 枚目のはがれたタイルが赤のときは 1 を，青のときは 2 を，黄色のときは 3 を表す．

入力例 1

出力例 1

入力例 1 において，11 \times 11 の壁画は以下の図の通りである．× は，はがれたタイルを表す．

入力例 2

出力例 2

D - 1 年生 (A First Grader)

Time Limit: 10 sec / Memory Limit: 256 MB

配点： 100 点

問題

JOI 君は小学 1 年生である．JOI君は教わったばかりの足し算，引き算がとても好きで，数字が並んでいるのを見ると最後の 2 つの数字の間に = を入れ，残りの数字の間に必ず + または - を入れて等式を作って遊んでいる．例えば 8 3 2 4 8 7 2 4 0 8 8 から，等式 8+3-2-4+8-7-2-4-0+8=8 を作ることができる．

JOI君は等式を作った後，それが正しい等式になっているかを計算して確かめる．ただし，JOI君はまだ負の数は知らないし，20 を超える数の計算はできない．したがって，正しい等式のうち左辺を左から計算したとき計算の途中で現れる数が全て 0 以上 20 以下の等式だけがJOI君が確かめられる正しい等式である．例えば，8+3-2-4-8-7+2+4+0+8=8 は正しい等式だが，途中に現れる 8+3-2-4-8 が負の数なのでJOI君はこの等式が正しいかどうか確かめることができない．

入力として数字の列が与えられたとき，JOI 君が作り，確かめることができる正しい等式の個数を求めるプログラムを作成せよ．

入力

入力は 2 行からなる．1 行目には並んでいる数字の個数を表す整数 N (3 \leqq N \leqq 100) が書かれている．2 行目には 0 以上 9 以下の整数が N 個，空白を区切りとして書かれている．

与えられる入力データの 60 %では，JOI 君が作り，確かめることができる正しい等式の個数は 2^{31}-1 を超えない．また，与えられる入力データの全てにおいて，JOI 君が作り，確かめることができる正しい等式の個数は 2^{63}-1 を超えない．

出力

JOI 君が作り，確かめることができる正しい等式の個数を表す整数を 1 行で出力せよ．

入力例 1

11
8 3 2 4 8 7 2 4 0 8 8

出力例 1

入力例 1 において，JOI君は 10 個の正しい等式

8+3-2-4+8-7-2-4-0+8=8
8+3-2-4+8-7-2-4+0+8=8
8+3+2+4-8-7+2-4-0+8=8
8+3+2+4-8-7+2-4+0+8=8
8+3+2-4+8-7+2+4-0-8=8
8+3+2-4+8-7+2+4+0-8=8
8-3+2+4-8+7+2+4-0-8=8
8-3+2+4-8+7+2+4+0-8=8
8-3+2-4+8+7+2-4-0-8=8
8-3+2-4+8+7+2-4+0-8=8

を作り，確かめることができるので 10 を出力する．

入力例 2

40
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1

出力例 2

7069052760

入力例 2 において，答えが 32 bit 符号付き整数の範囲に収まらないことに注意せよ．

E - チーズ (Cheese)

Time Limit: 10 sec / Memory Limit: 256 MB

配点： 100 点

問題

今年も JOI 町のチーズ工場がチーズの生産を始め，ねずみが巣から顔を出した．JOI 町は東西南北に区画整理されていて，各区画は巣，チーズ工場，障害物，空き地のいずれかである．ねずみは巣から出発して全てのチーズ工場を訪れチーズを 1 個ずつ食べる．

この町には，N 個のチーズ工場があり，どの工場も １ 種類のチーズだけを生産している．チーズの硬さは工場によって異なっており，硬さ 1 から N までのチーズを生産するチーズ工場がちょうど 1 つずつある．

ねずみの最初の体力は 1 であり，チーズを 1 個食べるごとに体力が 1 増える．ただし，ねずみは自分の体力よりも硬いチーズを食べることはできない．

ねずみは，東西南北に隣り合う区画に 1 分で移動することができるが，障害物の区画には入ることができない．チーズ工場をチーズを食べずに通り過ぎることもできる．すべてのチーズを食べ終えるまでにかかる最短時間を求めるプログラムを書け．ただし，ねずみがチーズを食べるのにかかる時間は無視できる．

入力

入力は H+1 行ある．1 行目には 3 つの整数 H，W，N (1 \leqq H \leqq 1000，1 \leqq W \leqq 1000，1 \leqq N \leqq 9) がこの順に空白で区切られて書かれている．2 行目から H + 1 行目までの各行には，S，1，2，\ldots，9，X，. からなる W 文字の文字列が書かれており，各々が各区画の状態を表している．北から i 番目，西から j 番目の区画を (i, j) と記述することにすると (1 \leqq i \leqq H，1 \leqq j \leqq W)，第 i + 1 行目の j 番目の文字は，区画 (i, j) が巣である場合は S となり，障害物である場合は X となり，空き地である場合は . となり，硬さ 1，2，\ldots，9 のチーズを生産する工場である場合はそれぞれ 1，2，\ldots，9 となる．入力には巣と硬さ 1，2，\ldots，N のチーズを生産する工場がそれぞれ 1 つずつある．他のマスは障害物または空き地であることが保証されている．ねずみは全てのチーズを食べられることが保証されている．

出力

すべてのチーズを食べ終えるまでにかかる最短時間（分）を表す整数を 1 行で出力せよ．

入力例 1

3 3 1
S..
...
..1

出力例 1

入力例 2

4 5 2
.X..1
....X
.XX.S
.2.X.

出力例 2

入力例 3

10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......

出力例 3

F - JOI 旗 (JOI Flag)

Time Limit: 10 sec / Memory Limit: 256 MB

配点： 100 点

問題

情報オリンピック日本委員会では，今年の日本情報オリンピック (JOI) を宣伝するために，JOI のロゴをモチーフにした旗を作ることになった．旗は「良い旗」でなければならない．「良い旗」とは，アルファベットの J，O，I のいずれかの文字を，縦 M 行，横 N 列の長方形状に並べたもので，J，O，I が以下の図のように (すなわち，J の右隣に O が，その J の下隣に I が) 並んでいる箇所が旗の少なくとも 1 か所にあるものである．

以下の図に，「良い旗」の例を 2 つ示す．

以下の図に，「良い旗」ではない例を 2 つ示す．

いま M, N の値，および旗の一部の場所について J，O，I のどの文字にするかが決まっており，入力としてその情報が与えられる．考えられる「良い旗」は何通りあるかを計算し，その数を 100\,000 \ (= 10^5) で割った余りを出力するプログラムを作成せよ．

入力

入力は 1 + M 行からなる．

1 行目には旗の大きさを表す 2 つの整数 M, N (2 \leqq M \leqq 20，2 \leqq N \leqq 20) が空白で区切られて書かれている．

1 + i 行目 (1 \leqq i \leqq M) には，N 文字からなる文字列が書かれている．各文字は J，O，I，? のいずれかであり，j 文字目 (1 \leqq j \leqq N) が J，O，I のいずれかである場合は i 行 j 列の場所の文字がそれぞれ J，O，I に決まっていること，? である場合はまだ決まっていないことを表す．

出力

考えられる「良い旗」の個数を 100\,000 \ (= 10^5) で割った余りを 1 行で出力せよ．

入力例 1

2 3
??O
IIJ

出力例 1

入力例 1 においては，以下の図の 4 通りの「良い旗」が考えられる．

入力例 2

2 2
??
??

出力例 2

入力例 3

3 3
??I
???
O?J

出力例 3

入力例 4

5 4
JOI?
????
????
????
?JOI

出力例 4

入力例 4 においては，「良い旗」は 2\,428\,218 通り考えられるので，それを 100\,000 \ (= 10^5) で割った余りである 28\,218 を出力する．