A - スペース高橋君

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

スペース高橋君は今日も銀河の平和を守っています。

スペース高橋君は銀河の治安を悪化させているスペース青木君と踊りで勝負することにしました。

具体的な方法を説明します。

スペース青木君は Left、Right、AtCoder、の三種類の単語からなる言葉を発します。

スペース高橋君は Left と聞いたら <、Right と聞いたら >、AtCoder と聞いたら A と答えます。

あなたの仕事は、スペース高橋君をサポートするためのプログラムを書くことです。

スペース青木君の発した言葉が与えられるので、スペース高橋君の発する言葉を表示するプログラムを作ってください。

入力

入力は以下の形式で標準入力から与えられる。

S
  • 1 行目には文字列 S が与えられる。S には半角スペースが含まれることもあることに注意せよ。
  • S の長さは 1 文字以上 100 文字以下である。
  • S は、3 種類の単語 (Left、Right、AtCoder) いくつかを半角スペース 1 つでつないだものである。

出力

出力は標準出力に行い、末尾に改行を入れること。

S について、Left を <、Rightを>、AtCoder を A に置換したものを一行に出力せよ。行の最後に余分な空白を入れないように注意すること。

入力例1

Left Right AtCoder

出力例1

< > A

入力例2

Left Left Right Right AtCoder

出力例2

< < > > A

入力例3

Right Right AtCoder Left Left AtCoder

出力例3

> > A < < A
B - ドキドキデート大作戦高橋君

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君の通っている学校で大掃除が行われることになりました．学校には N 個の教室があり，各教室は 1 から N まで順番に番号付けられており，左から右に並んでいます．

高橋君の学校には高橋君を含め M 人の生徒がおり，掃除すべき連続した教室の区間(掃除区間と呼ぶ)は M 個既に決まっています．しかし，それらの掃除区間を誰が担当するかは決まっていません． 異なる生徒には異なる掃除区間が割り当てられ，割り当てられた生徒はそれに含まれる全ての教室を掃除しなければなりません．1 つの教室が複数の掃除区間に含まれることがあります．

高橋君は大掃除の日に女の子とのデートの約束をしていることに気づきました．デートをサボってしまうと何が起こるか分からないので大掃除をサボることに決めました． 前述の通りいくつかの教室については複数の掃除区間に含まれていることがあるので，高橋君の担当分をサボっても全ての教室を誰かが掃除してくれさえすれば，サボったことがバレないことに気づきました． 掃除されていない教室があった場合には，サボったことがバレます．

あなたの仕事は高橋君のために，サボってもバレない掃除区間を全て教えてあげることです．

なお，この学校の生徒は高橋君を除きみんな真面目なので，高橋君以外がサボることは無いと仮定してください．

入力

入力は以下の形式で標準入力から与えられる．

N M
s_1 t_1
s_2 t_2
:
s_M t_M
  • 1 行目には，学校の教室の数を表す整数 N (1 ≦ N ≦ 300,000) と生徒の数を表す整数 M(1 ≦ M ≦ 100,000) が与えられる．
  • 続く M 行には，M 個の掃除区間が与えられる．このうち i(1≦i≦M) 行目には，i番目の掃除区間を表す整数 s_i,t_i(1≦s_i≦t_i≦N) が与えられる．これは，もしある生徒がその掃除区間を割り当てられた時，s_i≦x≦t_i を満たす全ての教室 x について掃除を行わなければならないことを表す．
  • 全く同じ区間が複数個与えられることもありえる．
  • 任意の教室は少なくとも 1 つの掃除区間に含まれることが保証される．

出力

出力は標準出力に行うこと．

1 行目に，サボってもバレない掃除区間の数 k を出力せよ．

続く k 行に，サボってもバレない掃除区間の番号を昇順に改行区切りで出力せよ．最後の行の末尾にも改行を入れること．

部分点

上記の制約に加え，以下の制約を追加で満たすデータセットに正解した場合は 30 点が与えられる。

  • 任意の教室 i (1≦i≦N) について，その教室を含む掃除区間の数は高々 2 つである．

入力例1

10 5
1 4
5 5
6 8
9 10
5 6

出力例1

2
2
5

高橋君が 2,5 番目の掃除区間に割り当てられた場合には，サボってもバレない．具体的には，

  • 2 番目の掃除区間を割り当てられても，5 番目の掃除区間が教室 5 を含んでいるためバレない．
  • 5 番目の掃除区間を割り当てられても，2 番目の掃除区間が教室 5 を含んでおり，かつ 3 番目の掃除区間が教室 6 を含んでいるためバレない．

一方，高橋君が，1,3,4 番目の掃除区間に割り当てられた場合，サボるとバレる．具体的には，

  • 1 番目の掃除区間を割り当てられた場合，教室 1,2,3,4 が掃除されていないのでバレる．
  • 3 番目の掃除区間を割り当てられた場合，教室 7,8 が掃除されていないのでバレる．
  • 4 番目の掃除区間を割り当てられた場合，教室 9,10 が掃除されていないのでバレる．

入力例2

3 6
1 1
1 1
2 2
2 2
3 3
3 3

出力例2

6
1
2
3
4
5
6

どんな掃除区間を選んでもサボることができる．

入力例3

10 3
1 4
2 6
6 10

出力例3

0

高橋君がサボれる掃除区間が一つも無いということもありえる．

C - エックスオア多橋君

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

多橋君は橋が大好きです。したがって、全ての辺が橋(グラフ理論用語)となる木と呼ばれるグラフが大好きです。また、多橋君は最近学校でXORについて学びました。そこで、次のような問題について考えています。

N 頂点と N-1 本の辺からなる連結な無向グラフ、つまり木が与えられます。各頂点は、それぞれ頂点 1、頂点 2、…、頂点 N と呼ばれます。各辺にはそれぞれ非負整数のコストが割り振られています。

整数 X が与えられるので、頂点 a と頂点 b を結ぶ単純パス(同じ辺を二度通らないパス、木においては必ず 1 つだけ存在する)上の辺のコストの\rm{xor}和が X になるような組 (a,b) (1≦a＜b≦N)の総数を求めてください。 ただし\rm{xor}和とは、いくつかの整数 A_1,A_2,… があったとき、それらの2進表現のビット毎の排他的論理和 A_1 \rm{xor} A_2 \rm{xor}… により得られる値のことを表します。 例えば、1 \rm{xor} 2 \rm{xor} 5 は 6 です。

あなたの仕事は、多橋君の代わりにこの問題を解くことです。

入力

入力は以下の形式で標準入力から与えられる。

N X
x_1 y_1 c_1
x_2 y_2 c_2
:
x_{N-1} y_{N-1} c_{N-1}
  • 1 行目には、グラフの頂点数を表す整数 N (1 ≦ N ≦ 100,000) と問題文中の整数 X (0≦X≦10^9) が与えられる。
  • 続く N-1 行には、グラフの N-1 本の辺の情報が与えられる。このうち i(1≦i≦N-1) 行目には、i 番目の辺が結ぶ 2 つの頂点 x_i,y_i(1≦x_i,y_i≦N) とコスト c_i (0≦c_i≦10^9) が与えられる。
  • 与えられるグラフは連結であることが保証される。

出力

1 行目に問題文中で求められている答えを出力せよ。末尾に改行を入れること。

入力例1

6 7
1 2 5
2 3 3
3 4 6
2 5 2
5 6 7

出力例1

3

(a,b)=(1,5),(4,5),(5,6) のとき、パス上の辺のコストの\rm{xor}和が 7(2進表記で111) となるので答えは 3 となる。

この入力例に対するグラフは下図のようになる。コストについては、その10進表記と2進表記を表示している。

サンプル1説明

入力例2

6 3
1 2 1
2 3 3
3 4 2
4 5 3
4 6 1

出力例2

4

入力例3

10 1
9 10 1
6 10 1
5 2 1
8 6 1
4 5 1
7 6 0
3 8 0
3 1 1
8 2 0

出力例3

25
D - みんな仲良し高橋君

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

二次元座標平面上に、座標の異なる 2N+1 個の点が与えられます。

高橋君はこの点の中からたくさんの仲良しペアを作ります。

以下の条件を満たす点同士は仲良しペアになれます。

  • 2 つの点の x 座標と y 座標のどちらかが等しい。

ただしどの点も 2 つ以上の点と仲良しペアになることはできません。

高橋君は、全ての点を仲良しペアにしたかったのですが、点の数が奇数なので不可能なことに気がつきました。

なのでどれか 1 個だけ点を削除し、そのあと N 組の仲良しペアを作れば全ての点を仲良しペアにできると考えました。

すべての点について、その点を削除すると残りの 2N 個の点から N 組の仲良しペアが作れるかどうかを判定してください。

入力

入力は以下の形式で標準入力から与えられる。

N
X_1 Y_1
X_2 Y_2
:
X_{2N+1} Y_{2N+1}
  • 1 行目には点の数を表す整数 N(1 ≦ N ≦ 100,000) が与えられる。
  • そのあと 2N+1 行には、点の位置の情報が与えられる。このうち i 行目には整数 X_i(1 ≦ X_i ≦ 2N+1),\ Y_i(1 ≦ Y_i ≦ 2N+1) が空白区切りで与えられ、これは i 番目の点の座標が (X_i,\ Y_i) であることを表す。
  • i ≠ j ならば、X_i ≠ X_j または Y_i ≠ Y_j を満たす。

出力

出力は標準出力に行い、末尾に改行を入れること。

出力は 2N+1 行からなる。

i 行目には、i 番目の点を削除したとき、残りの 2N 個の点から N 組の仲良しペアを作れるならばOK、作れないならばNGと出力すること。

部分点

以下の制約を追加で満たすデータセットに正解した場合は 30 点が与えられる。

  • すべての i(1 ≦ i ≦ 2N) について、X_i = X_{i+1} または Y_i = Y_{i+1} のどちらかを満たす。

入力例1

1
1 1
1 2
2 1

出力例1

NG
OK
OK

入力例2

2
1 1
1 2
2 2
2 3
3 3

出力例2

OK
NG
OK
NG
OK

この入出力例は部分点の制約を満たします。

入力例3

2
1 1
1 2
3 3
4 4
4 5

出力例3

NG
NG
OK
NG
NG