問題

JOI 商事では社員の在社時間をタイムカードで管理している．社員は，出社すると専用の装置を使ってタイムカードに出社時刻を刻印する．勤務を終え退社するときにも，タイムカードに退社時刻を刻印する．時刻は 24 時間制で扱われる．

防犯上の理由から，社員の出社時刻は 7 時以降である．また，全ての社員は 23 時より前に退社する．社員の退社時刻は常に出社時刻より後である．

入力として JOI 商事の 3 人の社員 A さん，B さん，C さんの出社時刻と退社時刻が与えられたとき，それぞれの社員の在社時間を計算するプログラムを作成せよ．

入力例 1

9 0 0 18 0 0
9 0 1 18 0 0
12 14 52 12 15 30

出力例 1

9 0 0
8 59 59
0 0 38

問題

先日，オンラインでのプログラミングコンテストが行われた．W 大学と K 大学のコンピュータクラブは以前からライバル関係にあり，このコンテストを利用して両者の優劣を決めようということになった．

今回，この2つの大学からはともに 10 人ずつがこのコンテストに参加した．長い議論の末，参加した 10 人のうち，得点の高い方から 3 人の得点を合計し，大学の得点とすることにした．

W 大学および K 大学の参加者の得点のデータが与えられる．このとき，おのおのの大学の得点を計算するプログラムを作成せよ．

入力例 1

23
23
20
15
15
14
13
9
7
6
25
19
17
17
16
13
12
11
9
5

出力例 1

66 61

入力例 2

17
25
23
25
79
29
1
61
59
100
44
74
94
57
13
54
82
0
42
45

出力例 2

240 250

問題

次のようなゲームがある．

あるキャラクターが縦 1 列に N 個並んでいる．これらのキャラクターの色は赤，青，黄のいずれかであり，初期状態で同じ色のキャラクターが 4 つ以上連続して並んでいることはない．プレーヤーは，ある位置のキャラクターを選び他の色に変更することができる．この操作により同じ色のキャラクターが 4 つ以上連続して並ぶとそれらのキャラクターは消滅する．キャラクターが消滅することにより新たに同じ色のキャラクターが 4 つ以上連続して並ぶとそれらのキャラクターも消滅し，同じ色のキャラクターが4つ以上連続して並んでいる箇所がなくなるまでこの連鎖は続く．このゲームの目的は，消滅しないで残っているキャラクター数をなるべく少なくすることである．

例えば，下図の左端の状態で，上から 6 番目のキャラクターの色を黄色から青に変更すると，青のキャラクターが 5 つ連続するので消滅し，最終的に 3 つのキャラクターが消滅せずに残る．

初期状態における N 個のキャラクターの色の並びが与えられたとき，1 箇所だけキャラクターの色を変更した場合の，消滅しないで残っているキャラクター数の最小値 M を求めるプログラムを作成せよ．

入力例 1

12
3
2
1
1
2
3
2
2
2
1
1
3

出力例 1

3

入力例 2

12
3
2
1
1
2
3
2
1
3
2
1
3

出力例 2

12

問題

冬の寒いある日，JOI 太郎君は広場にはった薄氷を割って遊ぶことにした．広場は長方形で，東西方向に m 個，南北方向に n 個，つまり，m \times n の区画に区切られている．また，薄氷が有る区画と無い区画がある．JOI 太郎君は，次のルールにしたがって，薄氷を割りながら区画を移動することにした．

• 薄氷があるどの区画からも薄氷を割り始めることができる．
• 東西南北のいずれかの方向に隣接し，まだ割られていない薄氷のある区画に移動できる．
• 移動した先の区画の薄氷をかならず割る．

JOI 太郎君が薄氷を割りながら移動できる区画数の最大値を求めるプログラムを作成せよ．ただし，1 \leqq m \leqq 90，1 \leqq n \leqq 90 である．与えられる入力データでは，移動方法は 20 万通りを超えない．

入力例 1

3
3
1 1 0
1 0 1
1 1 0

出力例 1

5

入力例 1 に対して，最大値を与える移動方法の例

入力例 2

5
3
1 1 1 0 1
1 1 0 0 0
1 0 0 0 1

出力例 2

5

入力例 2 に対して，最大値を与える移動方法の例

入力例 2 に対して，最大値を与えない移動方法の例

問題

1 から n までの番号が書かれた n 枚のカードがある．まず，一番上が番号 1 のカード，上から 2 枚目が番号 2 のカード，\ldots，一番下が番号 n のカードとなるように順番に重ねて，カードの山を作る．

カードの山に対して，「シャッフル (x, y) 」と呼ばれる次のような操作を行うことで，カードを並び替える（x, y は 1 \leqq x < y < n をみたす整数）．

シャッフル (x, y)

n 枚のカードを，一番上から x 枚目までのカードからなる山 A，x + 1 枚目から y 枚目のカードからなる山 B，y + 1 枚目から n 枚目のカードからなる山 C の 3 つの山に分ける．そして，山 A の上に山 B を重ね，さらにその上に山 C を重ねる．

例えば，順番に並んでいる 9 枚のカードに対して「シャッフル (3, 5)」を行うと，9 枚のカードに書かれた番号は，上から順番に 6, 7, 8, 9, 4, 5, 1, 2, 3 となる．

最初の山の状態から m 回のシャッフル「シャッフル (x_1, y_1)」「シャッフル (x_2, y_2)」\cdots「シャッフル (x_m, y_m)」を順番に行った後のカードの山において，上から数えて p 枚目から q 枚目のカードの中に番号が r 以下のカードが何枚含まれているかを求めるプログラムを作成せよ．

入力例 1

9
1
3 7 4
3 5

出力例 1

2

入力例 1 の山に対して, 「シャッフル (3, 5)」を行うと，カードは上から順番に 6, 7, 8, 9, 4, 5, 1, 2, 3 となる．上から数えて 3 枚目から 7 枚目に含まれる番号が 4 以下のカードは，番号 4 と番号 1 の 2 枚である．

入力例 2

12
3
3 8 5
3 8
2 5
6 10

出力例 2

3

入力例 2 の山に対して, 「シャッフル (3, 8)」「シャッフル (2, 5)」「シャッフル (6, 10)」を順番に行うと，カードは上から順番に 9, 10, 3, 11, 12, 4, 5, 6, 7, 8, 1, 2 となる．上から数えて 3 枚目から 8 枚目に含まれる番号が 5 以下のカードは 3 枚である．

問題

あるプログラミングコンテストでは，競技後の懇親会でビンゴゲームをする習わしがある．しかし，このビンゴゲームで使うビンゴカードは少々特殊で，以下の条件に従って作成される．

• ビンゴカードは N 行 N 列のマス目に区切られており，各マス目には正整数が 1 つずつ書かれている．それらの整数は全て異なる．
• マス目に書かれている整数は 1 以上 M 以下である．
• ビンゴカードに書かれている N \times N 個の整数の合計は S である．
• どの列を見たときも，上から下に向かって整数は昇順に並んでいる．
• どのマス目の整数も，そのマス目より左の列のどの整数よりも大きい．

以下は，N = 5，M = 50，S = 685 のときのビンゴカードの例である．

懇親会のために上の条件を満たすビンゴカードをできるだけたくさん作りたい．ただし，同一のカードを 2 枚以上作ってはならない．作ることができるビンゴカードの枚数の最大値を 100\,000 で割った余りを出力するプログラムを作成せよ．

入力例 1

3 9 45

出力例 1

1

入力例 2

3 100 50

出力例 2

7

入力例 3

5 50 685

出力例 3

74501

入力例 3 に対して，作ることができるビンゴカードの枚数の最大値は 642\,499\,974\,501 であるので，100\,000 で割った余りの 74\,501 を出力する．