Time Limit: 10 sec / Memory Limit: 256 MB
配点： 100 点
問題
太郎君はよく JOI 雑貨店で買い物をする．JOI 雑貨店には硬貨は 500 円，100 円，50 円，10 円，5 円，1 円が十分な数だけあり，いつも最も枚数が少なくなるようなおつりの支払い方をする．太郎君が JOI 雑貨店で買い物をしてレジで 1\,000 円札を 1 枚出した時，もらうおつりに含まれる硬貨の枚数を求めるプログラムを作成せよ．
例えば入力例 1 の場合は下の図に示すように，4 を出力しなければならない．
入力
入力は 1 行からなり，太郎君が支払う金額（1 以上 1\,000 未満の整数）が 1 つだけ書かれている．
出力
出力は 1 行のみである．おつりに含まれる硬貨の枚数を出力せよ．
入力例 1
380
出力例 1
4
入力例 2
1
出力例 2
15
Time Limit: 10 sec / Memory Limit: 256 MB
配点： 100 点
問題
与えられた文字列内の連続する 3 文字が，JOI または IOI という並びになっている個所がそれぞれ何個所あるのかを数え上げるプログラムを作成せよ．文字列はアルファベットの大文字だけからなる．例えば下図の「JOIOIOI」という文字列には JOI が 1 個所，IOI が 2 個所に含まれている．
入力
入力は 1 行であり，10\,000 文字以下のアルファベットの大文字からなる．
出力
出力は 2 行からなる．1 行目に見つかった JOI の個数，2 行目に見つかった IOI の個数をそれぞれ出力せよ．
入力例 1
JOIJOI
出力例 1
2 0
入力例 2
JOIOIOIOI
出力例 2
1 3
入力例 3
JOIOIJOINXNXJIOIOIOJ
出力例 3
2 3
Time Limit: 10 sec / Memory Limit: 256 MB
配点： 100 点
問題
次のような 2 人で行うカードゲームがある．
- このゲームでは，1 から 2n までの各整数が書かれた全部で 2n 枚のカードを使用する．ここで，n は 1 以上 100 以下の整数である．
- このカードを 2 人に n 枚ずつ配る．
- 次のルールに従って交互にカードを 1 枚ずつ場に出す．
- 場にカードが出ていないならば，好きなカードを出すことができる．
- 場にカードが出ているならば，最後に場に出たカードよりも大きい数の書かれたカードを出すことができる． カードが出せる場合は，必ず場にカードを出す必要がある．
- 出せるカードが無い場合はパスとなり，相手の番になる．このとき，場に出ているカードは無くなる．
- ゲームは場にカードが出ていない状態で始める．
- どちらかの手持ちのカードが無くなった時点でゲームは終了する．
- ゲーム終了時に相手の持っているカードの枚数を得点とする．
太郎と花子は，このゲームで対戦することになった．ゲームは太郎の番から始める．2 人は共に，出すことのできるカードのうち必ず一番小さい数が書かれたカードを出すことにしている．
太郎に配られるカードが入力されたとき，太郎と花子の得点を出力するプログラムを作成せよ．
入力
入力は n + 1 行ある．1 行目には整数 n が書かれている．2 行目から n + 1 行目までの各行には整数が 1 つずつ書かれており，太郎に配られるカードに書かれた整数を表す．
出力
出力は 2 行からなる．1 行目には太郎の得点を，2 行目には花子の得点を出力せよ．
入力例 1
5 1 7 9 6 10
出力例 1
3 0
入力例 2
10 8 7 14 18 4 11 3 17 5 19
出力例 2
2 0
Time Limit: 10 sec / Memory Limit: 256 MB
配点： 100 点
問題
あなたは星空の写真の中から星座を探している．写真には必ず，探したい星座と同じ形・向き・大きさの図形がちょうど一つ含まれている．ただし，写真の中には星座を構成する星以外に余分な星が写っている可能性がある．
例えば，図 1 の星座は図 2 の写真に含まれている（丸で囲んで示した）．与えられた星座の星の座標を x 方向に 2，y 方向に -3 だけ平行移動すると写真の中の位置になる．
探したい星座の形と写真に写っている星の位置が与えられたとき，星座の座標を写真の中の座標に変換するために平行移動するべき量を答えるプログラムを書け．
図 1: 探したい星座
図 2: 星空の写真
入力
入力の 1 行目には探したい星座を構成する星の個数 m が書かれている．続く m 行には探したい星座を構成する m 個の星の x 座標と y 座標を示す整数が空白区切りで書かれている．m + 2 行目には写真に写っている星の個数 n が書かれている．続く n 行には写真に写っている n 個の星の x 座標と y 座標を示す整数が空白区切りで書かれている．
星座を構成する m 個の星の位置はすべて異なる．また，写真に写っている n 個の星の位置はすべて異なる．1 \leqq m \leqq 200，1 \leqq n \leqq 1\,000 である．星の x 座標と y 座標はすべて 0 以上 1\,000\,000 以下である．
出力
出力は 1 行からなり，2 個の整数を空白区切りで書く．これらは探したい星座の座標をどれだけ平行移動すれば写真の中の座標になるかを表す．最初の整数が x 方向に平行移動する量，次の整数が y 方向に平行移動する量である．
入力例 1
5 8 5 6 4 4 3 7 10 0 10 10 10 5 2 7 9 7 8 10 10 2 1 2 8 1 6 7 6 0 0 9
出力例 1
2 -3
入出力例 1 は上の図に対応している．
入力例 2
5 904207 809784 845370 244806 499091 59863 638406 182509 435076 362268 10 757559 866424 114810 239537 519926 989458 461089 424480 674361 448440 81851 150384 459107 795405 299682 6700 254125 362183 50795 541942
出力例 2
-384281 179674
Time Limit: 10 sec / Memory Limit: 256 MB
配点： 100 点
問題
IOI 製菓では，創業以来の伝統の製法で煎餅（せんべい）を焼いている．この伝統の製法は，炭火で一定時間表側を焼き，表側が焼けると裏返して，炭火で一定時間裏側を焼くというものである．この伝統を守りつつ，煎餅を機械で焼いている．この機械は縦 R (1 \leqq R \leqq 10) 行，横 C (1 \leqq C \leqq 10000) 列の長方形状に煎餅を並べて焼く．通常は自動運転で，表側が焼けたら一斉に煎餅を裏返し裏側を焼く．
ある日，煎餅を焼いていると，煎餅を裏返す直前に地震が起こり何枚かの煎餅が裏返ってしまった．幸いなことに炭火の状態は適切なままであったが，これ以上表側を焼くと創業以来の伝統で定められている焼き時間を超えてしまい，煎餅の表側が焼けすぎて商品として出荷できなくなる．そこで，急いで機械をマニュアル操作に変更し，まだ裏返っていない煎餅だけを裏返そうとした．この機械は，横の行を何行か同時に裏返したり縦の列を何列か同時に裏返したりすることはできるが，残念なことに，煎餅を 1 枚ごと裏返すことはできない．
裏返すのに時間がかかると，地震で裏返らなかった煎餅の表側が焼けすぎて商品として出荷できなくなるので，横の何行かを同時に 1 回裏返し，引き続き，縦の何列かを同時に 1 回裏返して，表側を焼きすぎずに両面を焼くことのできる煎餅，つまり，「出荷できる煎餅」の枚数をなるべく多くすることにした．横の行を 1 行も裏返さない，あるいは，縦の列を 1 列も裏返さない場合も考えることにする．出荷できる煎餅の枚数の最大値を出力するプログラムを書きなさい．
地震の直後に，煎餅が次の図のような状態になったとする．黒い丸が表側が焼ける状態を，白い丸が裏側が焼ける状態を表している．
1 行目を裏返すと次の図のような状態になる．
さらに，1 列目と 5 列目を裏返すと次の図のような状態になる．この状態では，出荷できる煎餅は 9 枚である．
ヒント
R の上限 10 は C の上限 10\,000 に比べて小さいことに注意せよ．
入力
入力の 1 行目には 2 つの整数 R, C (1 \leqq R \leqq 10, 1 \leqq C \leqq 10\,000) が空白を区切りとして書かれている．続く R 行は地震直後の煎餅の状態を表す．(i + 1) 行目 (1 \leqq i \leqq R) には，C 個の整数 a_{i,1}, a_{i,2}, \ldots, a_{i,C} が空白を区切りとして書かれており，a_{i,j} は i 行 j 列 の煎餅の状態を表している. a_{i,j} が 1 なら表側が焼けることを，0 なら裏側が焼けることを表す．
出力
出力は，出荷できる煎餅の最大枚数だけを含む 1 行からなる．
入力例 1
2 5 0 1 0 1 0 1 0 0 0 1
出力例 1
9
入力例 2
3 6 1 0 0 0 1 0 1 1 1 0 1 0 1 0 1 1 0 1
出力例 2
15
Time Limit: 10 sec / Memory Limit: 256 MB
配点： 100 点
問題
JOI 国には，n 島の島があり，各島には 1 から n までの番号が付けられている．現在，JOI 国では各島の間を結ぶ航路網の整備が進んでいる．
あなたは，船舶の切符を扱っているチケットセンターに勤務している．JOI 国には船舶を使って，できる限り安価に，島と島の間を旅行したいと考えている人が沢山おり，彼らは，出発地と目的地を注文票に記入して，あなたのところに送ってくる．
あなたの仕事は，客から注文票を受け取ったらすぐに，いくつかの船舶を乗り継いで，出発地と目的地を結ぶ航路の中で，もっとも安価な運賃を計算し，客に伝えることである．
ただし，旅程によっては，船舶を使って旅行することが出来ない場合もある．そのときは『船舶を使って旅行することが出来ない』と客に伝える必要がある．また，JOI 国では，島と島の間を結ぶ新しい船舶が，次々と運航を開始しており，あなたには，その情報が随時伝えられる．客に返事をする際には，最新の情報に留意しなければならない．
入力として，客の注文票や新たに運航を開始した船舶の運航情報が与えられたときに，客への返事を求めるプログラムを作成せよ．
なお，入力例 1 と出力例 1 に対する実行状況を，図 1 として図示している．
入力
入力の 1 行目には 2 つの整数 n, k (1 \leqq n \leqq 100，1 \leqq k \leqq 5\,000) が書かれている．これは，島の数が n 島で，入力が k + 1 行からなることを表す．
i + 1 行目 (1 \leqq i \leqq k) には，3 個または 4 個の整数が空白を区切りとして書かれている．
- 最初の数字が 0 のとき，この行は客の注文票を表す．
この行には 3 個の整数 0, a, b (1 \leqq a \leqq n，1 \leqq b \leqq n，a \neq b) が空白を区切りとして書かれている．
これは，客が，島 a を出発地とし島 b を目的地とするような注文票を送ってきたことを表す． - 最初の数字が 1 のとき，この行は新たに運航を開始した船舶の運航情報を表す．
この行には 4 個の整数 1, c, d, e (1 \leqq c \leqq n，1 \leqq d \leqq n，c \neq d，1 \leqq e \leqq 1\,000\,000) が書かれている．
これは島 c と島 d を往復する船舶が新たに運航を開始し，この船舶の島 c から島 d への運賃と，島 d から島 c への運賃が，共に e であることを表す．
この行以降の注文票に対しては，この船舶も考慮して返事をしなければならない．
最初の段階では，船舶は一隻も運航していないものとする．入力のうち，船舶の運航情報を表す行は 1\,000 行以下である．また，島と島の間に，複数の船舶が運航することがあることに注意せよ．
出力
入力のうち，注文票を表す行の数を m とおく．
出力は m 行からなり，i 行目 (1 \leqq i \leqq m) には，i 番目の注文票に対する返事を表す整数を書く．
すなわち，i 番目の注文票の出発地と目的地の間を，いくつかの船舶を乗り継いで旅行することが可能ならば，その運賃の合計の最小値を書く．旅行することが不可能ならば，-1 を書く．
入力例 1
3 8 1 3 1 10 0 2 3 1 2 3 20 1 1 2 5 0 3 2 1 1 3 7 1 2 1 9 0 2 3
出力例 1
-1 15 12
なお，入力例 1 と出力例 1 の船舶が運航を開始していく模様と客からの注文票に対する返答を，図 1 として以下に図示している．
入力例 2
5 16 1 1 2 343750 1 1 3 3343 1 1 4 347392 1 1 5 5497 1 2 3 123394 1 2 4 545492 1 2 5 458 1 3 4 343983 1 3 5 843468 1 4 5 15934 0 2 1 0 4 1 0 3 2 0 4 2 0 4 3 0 5 3
出力例 2
5955 21431 9298 16392 24774 8840