Time Limit: 2 sec / Memory Limit: 256 MB
問題文
表向きのコインが x 枚、裏向きのコインが y 枚ある。 高橋君はちょうど k 枚のコインを選び、それらすべてをひっくり返す。 その結果、表向きのコインは最大で何枚になるか？
入力
入力は以下の形式で標準入力から与えられる。
x y k
- 1 行目には、表向きのコインの枚数 x (1≦x≦10^6) 、裏向きのコインの枚数 y (1≦y≦10^6) が空白区切りで与えられる。
- 2 行目には、ひっくり返すコインの枚数 k (1≦k≦x+y) が与えられる。
出力
コインをひっくり返した結果、表向きのコインは最大で何枚になるか 1 行に出力せよ。 出力の末尾に改行を入れること。
入力例1
3 2 1
出力例1
4
裏向きのコインを 1 枚ひっくり返せばよい。
入力例2
3 2 4
出力例2
3
表向きのコインを 2 枚、裏向きのコインを 2 枚ひっくり返せばよい。
入力例3
3 2 5
出力例3
2
すべてのコインをひっくり返すしかない。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
縦 N マス、横 M マスの盤面がある。 上から i (1≦i≦N) マス目、左から j (1≦j≦M) マス目の位置を (i,j) と表す。
はじめ、マス (i,j) には a_{ij} 匹のアメーバがいた。 ただし、盤面の端にアメーバはいなかった。 すなわち、i=1,N または j=1,M ならば a_{ij}=0 である。
高橋君が大声を出すと、アメーバたちは驚いてそれぞれ次の行動をとった。
- 1 匹のアメーバが 4 匹に分裂し、上下左右のマスへ 1 匹ずつ移動した。
その結果、マス (i,j) には b_{ij} 匹のアメーバがいることになった。
今のアメーバの配置 (b_{ij}) が与えられるので、はじめのアメーバの配置 (a_{ij}) を 1 つ求めよ。 ただし、(a_{ij}) は少なくとも 1 つ存在する。
入力
入力は以下の形式で標準入力から与えられる。
N M
b_{11}b_{12}..b_{1M}
b_{21}b_{22}..b_{2M}
:
b_{N1}b_{N2}..b_{NM}
- 1 行目には、盤面の縦のマス数 N (3≦N≦500) と横のマス数 M (3≦M≦500) が空白区切りで与えられる。
- 2 行目からの N 行には、今のアメーバの配置が与えられる。このうち i 行目の j 文字目の数字が b_{ij} (0≦b_{ij}≦9) を表す。
出力
はじめのアメーバの配置を 1 つ、以下の形式で N 行に出力せよ。 ただし、i 行目の j 文字目の数字が a_{ij} を表す。 出力の末尾に改行を入れること。
a_{11}a_{12}..a_{1M}
a_{21}a_{22}..a_{2M}
:
a_{N1}a_{N2}..a_{NM}
入力例1
3 3 010 101 010
出力例1
000 010 000
入力例2
3 4 0230 2323 0230
出力例2
0000 0230 0000
入力例3
5 5 00100 03040 20903 05060 00300
出力例3
00000 00100 02030 00300 00000
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
L 個のマスが横一列に並んでいる。 マスの上には N 匹のウサギがいる。 i (1≦i≦N) 番目のウサギは、左から x_i 番目のマスにいる。 ただし、1≦x_1<x_2<..<x_N≦L を満たす。 また、ウサギはそれぞれ左向きまたは右向きである。
それぞれのウサギは、自分の 1 つ前にマスが存在し、そこに他のウサギがいなければ、ジャンプして自分の 1 つ前のマスへ移動できる。
ウサギがジャンプする順番を自由に選べるとき、ジャンプの総回数の最大値を求めよ。
入力
入力は以下の形式で標準入力から与えられる。
N L x_1 d_1 x_2 d_2 : x_N d_N
- 1 行目には、ウサギの匹数 N (1≦N≦10^5) とマスの個数 L (N≦L≦10^9) が空白区切りで与えられる。
- 2 行目からの N 行には、ウサギの情報が与えられる。このうち i 行目には、i 番目のウサギの位置 x_i と向き d_i が空白区切りで与えられる。ただし、d_i は
L（左向き）またはR（右向き）である。 - 1≦x_1<x_2<..<x_N≦L を満たす。
出力
ウサギがジャンプする順番を自由に選べるとき、ジャンプの総回数の最大値を 1 行に出力せよ。 出力の末尾に改行を入れること。
入力例1
1 5 1 R
出力例1
4
図のようにジャンプすればよい。
入力例2
4 5 1 R 3 L 4 L 5 L
出力例2
3
図のようにジャンプすればよい。
入力例3
4 10 1 L 5 R 6 L 10 R
出力例3
0
どのウサギもジャンプできない。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
N 個の頂点と M 本の辺からなる無向グラフが与えられる。 グラフは連結で、自己ループや多重辺を含まない。 辺は 1 から M まで番号が振られている。
はじめ、辺には色が塗られていない。
高橋君は i (1≦i≦M) 番目の辺に色 c_i が塗られているようにしたい。
ただし、c_i は r（赤）または b（青）である。
高橋君は次のようにして辺に色を塗る。
- まず、好きな頂点を始点に選ぶ。以降、「隣接する頂点へ移動する」というステップを好きなだけ繰り返す。
- 各ステップごとに使われた辺に色を塗る。このとき、奇数回目のステップでは赤を塗り、偶数回目のステップでは青を塗る。
- 既に色が塗られている辺に色を塗ると、新しい色で上書きされる。
すべての辺に目標の色が塗られているようにできるか判定せよ。
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 c_1 a_2 b_2 c_2 : a_M b_M c_M
- 1 行目には、頂点の個数 N (2≦N≦2,000) と辺の本数 M (1≦M≦2,000) が空白区切りで与えられる。
-
2 行目からの M 行には、辺の情報が与えられる。このうち i 行目には、整数 a_i，b_i (1≦a_i<b_i≦N) と色 c_i が空白区切りで与えられる。これは次のことを表す。
- i 番目の辺が頂点 a_i と頂点 b_i を結んでいる。ただし、i≠j ならば a_i≠a_j または b_i≠b_j を満たす。
- i 番目の辺に色 c_i が塗られているようにしたい。ただし、c_i は
r（赤）またはb（青）である。
- グラフは連結である。
出力
すべての辺に目標の色が塗られているようにできるならば Yes を、できないならば No を 1 行に出力せよ。
出力の末尾に改行を入れること。
入力例1
6 5 1 2 r 2 3 b 3 4 r 4 5 b 5 6 r
出力例1
Yes
例えば、頂点 1 を始点に選び、図のようにして辺に色を塗ればよい。
入力例2
4 3 1 2 r 1 3 r 1 4 r
出力例2
Yes
例えば、頂点 2 を始点に選び、図のようにして辺に色を塗ればよい。上書きされる色は破線で示している。
入力例3
3 3 1 2 b 1 3 b 2 3 b
出力例3
No