Time Limit: 2 sec / Memory Limit: 256 MB
問題文
縦 H マス、横 W マスの白いマス目があります。高橋君は、上下または左右に隣り合う 2 マスを選び、それら 2 マスを黒く塗ります。高橋君が 2 マスを黒く塗る方法は何通りか求めてください。
制約
- 1≦H,W≦100
入力
入力は以下の形式で標準入力から与えられる。
H W
出力
高橋君が 2 マスを黒く塗る方法は何通りか出力せよ。
入力例1
2 3
出力例1
7
図の 7 通りです。
入力例2
4 1
出力例2
3
図の 3 通りです。
入力例3
1 1
出力例3
0
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は文字列 S を持っています。S は英小文字のみからなります。
まず、高橋君は S の文字を任意の順番に並べ替え、文字列 S' を作ります。
次に、高橋君は S' を任意の位置で分割し、何個かの文字列 s_1,s_2,...,s_N を作ります(N は任意)。ただし、各 s_i は回文でなければなりません。
各 s_i の長さの最小値を X とします。高橋君は X をできるだけ大きくしようとしています。X の最大値を求めてください。
制約
- 1≦|S|≦10^5
- S は英小文字のみからなる。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
X の最大値を出力せよ。
入力例1
rokovoko
出力例1
3
例えば、krk
,oovoo
とすればよいです。
入力例2
tomtom
出力例2
6
例えば、mottom
とすればよいです。
入力例3
vwxyz
出力例3
1
例えば、v
,w
,x
,y
,z
とすればよいです。
入力例4
succeeded
出力例4
3
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は N 個の魔法を覚えています。魔法は 1 から N まで番号が振られています。
最初、気温は 0 度です。高橋君が i 番目の魔法を唱えると、気温が a_i 度だけ上がった後 b_i 度だけ下がります。
高橋君はすべての魔法をちょうど 1 回ずつ唱えます。この間の気温の最大値を X 度とします。高橋君は魔法を唱える順番を工夫して、X をできるだけ小さくしようとしています。X の最小値を求めてください。
制約
- 1≦N≦10^5
- a_i,b_i は整数である。
- 1≦a_i,b_i≦10^9
入力
入力は以下の形式で標準入力から与えられる。
N a_1 b_1 : a_N b_N
出力
X の最小値を出力せよ。
入力例1
1 10 20
出力例1
10
唯一の魔法を唱えると、気温は 0 → 10 → -10 度と変化します。
入力例2
2 30 20 10 20
出力例2
20
2 番目の魔法、1 番目の魔法の順に唱えると、気温は 0 → 10 → -10 → 20 → 0 度と変化します。
入力例3
5 5 10 10 5 10 15 15 10 20 20
出力例3
10
例えば、1,3,5,2,4 番目の魔法の順に唱えればよいです。
Time Limit: 5 sec / Memory Limit: 256 MB
問題文
それぞれ N 枚のカードからなる山が 2 つあります。これらを山 A, B とします。
山 A の上から i 番目のカードには、整数 a_i が書かれています。ただし、(a_1,...,a_N) は 1 から N までの順列です。
山 B の上から i 番目のカードには、整数 b_i が書かれています。ただし、(b_1,...,b_N) は 1 から N までの順列です。
高橋君は次の一連の操作を 2N-2 回行い、長さ 2N-2 の数列を作ります。
- 山 A, B のうちカードが 2 枚以上残っている方を好きに選ぶ。
- 選んだ方の山の一番上のカードを取り除く。
- 選ばなかった方の山の一番上のカードに書かれた数を、数列の末尾に追加する。
高橋君が作ることのできる数列は何通りか、10^9+7 で割った余りを求めてください。
制約
- 2≦N≦1,000
- (a_1,...,a_N) は 1 から N までの順列である。
- (b_1,...,b_N) は 1 から N までの順列である。
入力
入力は以下の形式で標準入力から与えられる。
N a_1 ... a_N b_1 ... b_N
出力
高橋君が作ることのできる数列は何通りか、10^9+7 で割った余りを出力せよ。
入力例1
2 1 2 2 1
出力例1
2
山 A,B の順に選ぶと数列 (2,2) が得られ、山 B,A の順に選ぶと数列 (1,1) が得られます。
入力例2
3 1 2 3 2 3 1
出力例2
5
次の 5 通りの数列を作ることができます。
- (1,1,1,1)
- (1,3,2,1)
- (1,3,3,3)
- (2,2,2,1)
- (2,2,3,3)
入力例3
5 3 1 4 2 5 3 2 4 1 5
出力例3
58