AtCoder Regular Contest 032

A - ホリドッグ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

とても賢い犬であるホリドッグ(Holidog)くんは、足し算と素数判定をすることができます。ホリドッグくんはある正整数についてそれが素数であるか尋ねられたとき、それが素数であるなら WANWAN、そうでなければ BOWWOW と吠えます。

あなたは、ホリドッグくんに 1 から n までの総和 1 + 2 + 3 + … + n が素数であるかどうかを尋ねました。ホリドッグくんがどう吠えたかを出力するプログラムを書いて下さい。

素数とは、1 とその数自身以外の正整数で割り切ることが出来ない 2 以上の正整数のことを言います。例えば 2 や 3 や 17 は素数です。1 や 10 は素数ではありません。

入力

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

1 行目には、1 つの整数 n (1 ≦ n ≦ 1000) が与えられる.

出力

1 行目には、1 + 2 + 3 + … + n が素数ならば WANWAN、そうでなければ BOWWOW を出力せよ。

末尾の改行を忘れないこと。

入力例1

出力例1

WANWAN

1 + 2 = 3 であり、3 は素数なので WANWAN と出力します。

入力例2

出力例2

BOWWOW

1 + 2 + 3 + 4 + 5 = 15 であり、15 = 3 × 5 なので、 BOWWOW と出力します。

入力例3

出力例3

BOWWOW

1 は素数ではありません。

入力例4

出力例4

BOWWOW

1 + 2 + ... + 999 は素数ではありません。

B - 道路工事

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

大工のチョーさん(Daiku Cho)の町では道路の建設が進んでいます。チョーさんの町には N 個の交差点と M 個の道路があり、道路は異なる2つの交差点を双方向に結んでいます。不便なことに、ある交差点から別の交差点まで道路を使って行き来できるとは限りません。

チョーさんの建設会社は、異なる交差点を結ぶいくつかの道路を作って、N 個のどの交差点からも道路を使って他のどの交差点へも行けるようにしたいと思っています。

どの交差点からも道路を使って別のどの交差点にも行けるようにするには最小で何本の道路を建設する必要があるかを答えてください。ただし、すでにある道路でどの交差点からも別のどの交差点へ行けるとき、0 を出力してください。

入力

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

N M
a_1 b_1
a_2 b_2
:
a_M b_M

1 行目には、チョーさんの町の交差点の数と、既にある道路の数を表す 2 つの整数 N (1 ≦ N ≦ 100,000) と M (0 ≦ M ≦ 100,000) がスペース区切りで与えられる。
2 行目から M 行には、既にある道路の情報が与えられる。そのうち i 行目には、i 番目の道路がつなぐ 2 つの交差点を表す 2 つの整数 a_i, b_i (1 ≦ a_i < b_i ≦ N がスペース区切りで与えられる。
同じ交差点をつなぐ道路が与えられることはない。すなわち、i,j (1≦i,j≦M) に対し、i≠j ならば a_i≠a_j または b_i≠b_j が成り立つ。

出力

新たに建設する道路の最小の本数を1行目に出力せよ。

末尾の改行を忘れないこと。

入力例1

4 2
1 2
1 3

出力例1

交差点 1、2、3 は互いに道路でつながっているが、交差点 4 はつながっていない。例えば、交差点 1 と 4 を結ぶ道路を作れば十分である。

入力例2

出力例1

C - 仕事計画

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

大工のチョーさん(Daiku Cho)は N 個の仕事を頼まれています。i 番目の仕事は時刻 a_i に始まり、b_i に終わります。

チョーさんは一度に複数の仕事をこなすことはできないので、これらの仕事のうち、仕事を行う時刻が重ならないようになるべく多くの仕事を選びたいです。ただし、終了と同時に別の仕事に取り掛かることはできます。

最も多く選ぶ方法が複数あるときは、選んだ仕事の番号を開始時刻の順に並べた列が辞書順最小となるように選ぼうと思っています。

大工のチョーさんは仕事上手ですが、スケジュールを管理するのは上手くないようです。チョーさんが引き受ける最適な仕事の組み合わせを求めてください。

ただし、長さ L の列 A=\{a_1,a_2,…,a_L\} と B=\{b_1,b_2,…,b_L\} に対し、辞書順で A が B より小さいとは、

i<k で a_i=b_i
i=k で a_i<b_i

となるような k(1≦k≦L) が存在するということです。

入力

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

N
a_1 b_1
a_2 b_2
:
a_N b_N

1 行目には、チョーさんが頼まれた仕事の数を表す整数 N (1 ≦ N ≦ 100,000) が与えられる。
2 行目から N 行には、チョーさんが頼まれた仕事の情報が与えられる。そのうち i 行目には、i 番目の仕事の開始時刻と終了時刻を表す 2 つの整数 a_i, b_i(0 ≦ a_i < b_i ≦ 1,000,000) がスペース区切りで与えられる。

出力

1 行目には、チョーさんが引き受ける仕事の数を出力せよ。

2 行目には、チョーさんが引き受ける仕事を、時刻が早いものから順に 1 つの空白で区切って出力せよ。

末尾の改行を忘れないこと。また、末尾に余計な空白を付け加えないこと。

入力例1

出力例1

2
1 4

チョーさんは最大で 2 つの仕事を選ぶことができます。その選び方は 3 通りあり、チョーさんは仕事 1 と 4、または仕事 2 と 3、または仕事 2 と 4 を選ぶことができます。この内、辞書順で小さくなる選び方は仕事 1 と 4 を選んだときです。なぜならば、それらの仕事番号を 仕事の開始時刻順 に並べたときに \{1,4\} となり、それが辞書順最小となるからです(21:12修正)。

入力例2

出力例2

3
2 3 5

入力例3

出力例3

4
4 3 5 8

D - アットコーダーモンスターズ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

アットコーダーモンスターズと言うゲームは、モンスターのチームを編成してバトルするゲームです。

あなたはモンスターを売っているお店にいます。このお店では、N 匹のモンスターが横一列に並べられています。そして、各モンスター A_i (1 ≦ i ≦N) には以下に示す 2 つの能力値が存在しています。

モンスター M_i のこうげきの能力を表す値 {M_i}_{ATK}
モンスター M_i のぼうぎょの能力を表す値 {M_i}_{DEF}

いま、N 匹のモンスターの中から異なるちょうど K 匹のモンスターを選んで購入し、それらでチームを編成しようとしています。しかし、ある能力値について、それらがかけ離れたモンスター同士がいるとチームとして安定しないことが分かっているので、できるだけ安定したチームを作りたいと思っています。

より厳密に、チームに含まれる 2 匹のモンスター X と Y についてその不安定度 S_{X,Y} を、

S_{X,Y} = max{ |X_{ATK} - Y_{ATK}|, |X_{DEF} - Y_{DEF}| }

と定義したとき、チームの不安定度は、チームに含まれる全てのモンスターのペアについて計算して得られる不安定度の最大値です。チームに含まれるモンスターが 1 匹の時、チームの不安定度は 0 です。

あなたは、チームの不安定度を最小化するような異なる K 匹のモンスターを購入しようと思っています。さらに、チームの不安定度を最小とするようなモンスターの選び方の総数も求めたいと思っています。

あなたは、達成できるチームの不安定度の最小値と、それを達成するモンスターの選び方の総数を 1,000,000,007 で割った余りを出力しなければなりません。

入力

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

N K
{M_1}_{ATK} {M_1}_{DEF}
{M_2}_{ATK} {M_2}_{DEF}
:
{M_N}_{ATK} {M_N}_{DEF}

1 行目には、お店に並んでいるモンスターの数と購入したいモンスターの数を表す 2 つの整数 N (1 ≦ N ≦ 100,000) と K (1 ≦ K ≦ N) がスペース区切りで与えられる.
2 行目から N 行には、お店に並んでいるモンスターの能力値の情報が与えられる。そのうち i 行目には、i 番目のモンスターの能力値を表す 2 つの整数 {M_i}_{ATK}, {M_i}_{DEF} (0 ≦ {M_i}_{ATK}, {M_i}_{DEF} ≦ 3000) がスペース区切りで与えられる。

部分点

この問題には部分点が設定されている。

10 点分のテストケースにおいて、1≦N≦20 を満たす。

出力

1 行目には、達成できるチームの不安定度の最小値を出力せよ。

2 行目には、チームの不安定度を最小化するようなモンスターの選び方の総数を 1000000007 で割った余りを出力せよ。

末尾の改行を忘れないこと。

入力例1

出力例1

2
2

モンスターは以下のように並んでおり、3 匹を選ぶときの不安定度の最小値は 2 である。また、選び方は 2 通りある。

入力例2

出力例2

90
1

入力例3

出力例3

0
3

入力例4

出力例4

0
75135237