CODE FESTIVAL 2014チーム対抗早解きリレー

A - haruki、気になります！

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ある日、haruki さんは学校で素数について習いました。素数とは、1 とその数自身でしか割り切れない 1 より大きい整数のことです。

とても好奇心旺盛な haruki さんは以下のような疑問を持ちました。

「n 以下の素数の中に偶数はいくつ存在するんだろう。haruki、気になります！」

そこで、haruki さんのために、n 以下の素数の中に偶数がいくつあるかを求めるプログラムを作成してください。

入力

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

整数 n (1 \leq n \leq 100) が 1 行に与えられる。

出力

n 以下の素数の中に偶数がいくつあるかを 1 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。

入力例1

出力例1

B - もう1年遊べるドン？

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

amylase 伯爵さんは今年卒業を控えた大学生です。

今度行われる期末試験において s 点以上の点数を得ることができれば無事に卒業できますが、そうでなければ留年してしまいます。

さて、来たる期末試験当日、amylase 伯爵さんは a 点を獲得しました。数値の比較が苦手な amylase 伯爵さんに代わって、彼が卒業できるかどうか判定してください。

入力

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

a s

1 行目には、amylase 伯爵さんの試験の点数を表す整数 a (0 \leq a \leq 100) と、卒業のために必要な点数を表す整数 s (0 \leq s \leq 100) が与えられる。

出力

amylase 伯爵さんが卒業できるなら Congratulations! を、そうでなければ Enjoy another semester... を、1 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。

入力例1

100 40

出力例1

Congratulations!

amylase 伯爵さんの期末試験の点数が 100 点、卒業に必要な点数が 40 点なので、卒業することができます。

入力例2

0 100

出力例2

Enjoy another semester...

amylase 伯爵さんの期末試験の点数が 0 点、卒業に必要な点数が 100 点なので、卒業することができません。

入力例3

60 60

出力例3

Congratulations!

C - amylasemania IIDX

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

kawatea さんは空から降ってくる複数の amylase 伯爵さんを順番に一度ずつ、音楽に合わせて叩くゲームにはまっています。

このゲームにはコンボというシステムが存在し、amylase 伯爵さんを音楽に合わせて叩くことに成功するとコンボの数が 1 増え、叩くことに失敗してしまうとコンボの数が 0 に戻ってしまいます。

合計で n 個の amylase 伯爵さんを叩き終わったとき、最大のコンボの数が m となりました。

このときに考えられる最小の失敗の回数を求めるプログラムを作成してください。

入力

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

n m

1 行目には、amylase 伯爵さんの数を表す整数 n (1 \leq n \leq 1{,}000{,}000{,}000) と、最大のコンボの数を表す整数 m (1 \leq m \leq n) が与えられる。

出力

考えられる最小の失敗の回数を 1 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。

入力例1

10 5

出力例1

入力例2

100 9

出力例2

D - FU

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

X さんとY さんはFUという名前のゲームで遊んでいます。

このゲームは、縦横ともに長さ n で n \times n 個の正方形のマスに区切られた盤面とFUという駒を用いて行われ、X さんは盤面の最上行の各マスに 1 つずつ自分のFUを下向きに、Y さんは盤面の最下行の各マスに 1 つずつ自分のFUを上向きに置いたところから始まります。

プレイヤーは以下のルールに従い、交互に自分のFUをひとつ選んで移動させるということを繰り返します。

X さんのFUは、現在置かれているマスの下に隣接するマスへしか移動できません
Y さんのFUは、現在置かれているマスの上に隣接するマスへしか移動できません
自分のFUを相手のFUと同一マスに置くことで、相手のFUを取ります

このゲームでは、自分の手番をパスすることや、二度続けて自分のFUを動かすことはできません。相手のFUをすべて取ったプレイヤーが勝ちです。

ぬまくんさんは X さんと Y さんの試合を途中から観戦したのですが、どちらが先手か聞いても、X さんと Y さんは試合に深く集中しているため、答えてくれません。幸い、試合は始まったばかりでどちらも相手のFUを取っていないので、盤面の状態からどちらが先手かわかるかもしれません。

そこで、現在の盤面の状態を入力に受け取って、どちらが先手かを求めるプログラムを作成してください。

入力

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

n
B_{1,1}B_{1,2}...B_{1, n}
B_{2,1}B_{2,2}...B_{2, n}
...
B_{n,1}B_{n,2}...B_{n, n}

1 行目には、盤面の一辺あたりの大きさを表す整数 n (2 \leq n \leq 100) が与えられる。
続く n 行には、盤面の各行の情報が最上行から最下行にかけて順に与えられる。
B の各要素はマスの状態を表しており、.、X、Yのいずれかの文字からなる。
.はそのマスに何も駒が置かれていないことを意味し、XとYはそれぞれ X さん、Y さんのFUがそのマスにあることを意味する。
各列において、必ずXとYが一つずつ存在しており、また、必ずXがYよりも上の行に位置することが保証される。
入力として与えられる盤面は、ゲームのルールと矛盾しないことが保証される。

出力

X さんが先手の場合はXを、Y さんが先手の場合はYを 1 行で出力せよ。

また、どちらが先手か決められない場合はImpossibleと 1 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。

入力例1

4
X..X
.XX.
.YYY
Y...

出力例1

入力例2

3
XXX
...
YYY

出力例2

Impossible

E - 変な足し算

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

縦 h、横 w で hw 個の正方形のマスに区切られたボードを考えます。各マスには0から9の 1 桁の数字か、もしくは.（ドット）が書かれています。また、ボードには、左上のマスが (1, 1)、右上が (1, w)、左下が (h, 1)、右下が (h, w) となるように、それぞれのマスに対して順に座標が振られています。

ボード内に書かれた整数が 1 つになるまで以下の手順を繰り返します。

整数が書かれたマスの組で、マンハッタン距離が最大になるような組の中から 1 つをランダムに選びます。（マンハッタン距離とは、2 つのマスの座標がそれぞれ (a, b)、(c, d) であるとき、|a - c| + |b - d| で計算される距離のことです）
1. で選んだ組において、マスに書かれた整数の和を元の数が大きいほうのマスに上書きし、小さいほうのマスには.を上書きします。もし元の数が等しい場合は、好きなほうに整数の和を上書きし、他方を.で上書きします。

上記手順が終了した後、ボード内に残る可能性のある整数のうち、最大のものを求めてください。

入力

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

h w
b_1
...
b_h

1 行目には、ボードの縦と横の長さを表す整数 h, w (1 \leq h, w \leq 100) が与えられる。
続く h 行には、ボードの情報が与えられる。
b_i はボードの上から i 行目の情報を表し、0から9の 1 桁の整数もしくは.を含む長さ w の文字列である。
ボードは少なくとも 1 つの整数を含むことが保証される。

出力

ボードに残る可能性のある整数のうち最大のものを 1 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。

入力例1

2 3
12.
.5.

出力例1

入力例2

5 5
..3.9
.1..6
2.3.4
7..11
....8

出力例2

F - ループを探せ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

頂点数および辺数がともに n であるような連結な無向グラフは、ループをちょうど 1 つだけ含むことが知られています。

このようなグラフが与えられるので、グラフに含まれるループの長さを求めて下さい。

入力

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

n
x_1 y_1
...
x_n y_n

1 行目には、グラフの頂点数を表す整数 n (3 \leq n \leq 100{,}000) が与えられる。
続く n 行には、グラフの辺の情報が与えられる。
それぞれの頂点には 1 から n までの番号が振られており、x_i, y_i (1 \leq x_i,y_i \leq n) は、i 番目の辺によって 2 つの頂点 x_i と y_i がつながっていることを表す。
与えられるグラフは連結であり、自己辺や多重辺は含まれないことが保証される。

出力

グラフに含まれるループの長さを 1 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。

入力例1

出力例1

入力例2

出力例2

G - haruki の覚醒め

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

haruki さんは朝に弱いことで有名です。haruki さんの家には目覚まし時計が n 個あり、i 番目の目覚まし時計の音量は a_i です。

haruki さんは鳴っている目覚まし時計の音量の合計が m 以上にならない限り、目を覚ますことはありません。しかしながら、必要以上に目覚まし時計をセットすると、うるさくて近所迷惑になってしまいます。

そこで、合計の音量が m 以上でかつ最小となるように目覚まし時計を選んだとき、その合計の音量を求めてください。

入力

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

n m
a_1
a_2
...
a_n

1 行目には、目覚まし時計の数を表す整数 n (1 \leq n \leq 50) と、目を覚ます最小の音量を表す整数 m (1 \leq m \leq 10{,}000) が与えられる。
続く n 行には、それぞれの目覚まし時計の音量を表す整数 a_i (1 \leq a_i \leq 10{,}000) が与えられる。

出力

合計の音量が m 以上でかつ最小となるときの合計の音量を 1 行で出力せよ。

また、合計の音量が m に達しない場合は、-1 を 1 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。

入力例1

出力例1

入力例2

出力例2

-1

H - アクセス頻度

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

サーバー管理者であるあなたは、サーバーへのアクセス時間をすべて記録しています。

今、サーバーへの負荷を調べるため、ある整数 n が与えられたとき、連続した n 秒間で行われたアクセス数の最大値を調べようと思いました。

そこで、m 個のアクセス時間のログが与えられるので、連続した n 秒間に行われたアクセス数の最大値を求めるプログラムを作成してください。

入力

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

n m
a_1
...
a_m

1 行目には、求めるアクセスの区間の長さを表す整数 n (1 \leq n \leq 1{,}000{,}000{,}000) と、アクセスの総数を表す整数 m (1 \leq m \leq 100{,}000) が与えられる。
続く m 行には、各アクセスの時間が与えられる。
a_i は i 番目のアクセスがちょうど a_i 秒目に行われたことを意味する。
0 \leq a_1 \leq a_2 \leq ... \leq a_m \leq 1{,}000{,}000{,}000 であることが保証される。

出力

n 秒間で行われたアクセス数のうち、最大のものを 1 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。

入力例1

出力例1

入力例2

出力例2

I - 信号待ち

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

陸運企業陸道社の社員である amylase 伯爵さんは、荷物を届けるためにとある街を訪れました。この街は、n 個の交差点と、交差点同士を結ぶ m 本の道路でできており、交差点には 1 から n までの番号がつけられています。

それぞれの交差点には信号機が 1 つずつ存在し、各信号機は青または赤の 2 つの状態を持ちます。時刻 t = 0, 1, 2, ... における交差点 i の信号機の状態は、パラメータ a_i, b_i, c_i によって次のように定まります。

最初の c_i 秒、すなわち t = 0, 1, ..., c_{i}-1 は、赤である
その後、 a_i 秒の青と b_i 秒の赤が繰り返される

青から赤に変わる時刻 (たとえば t = c_i + a_i の時) は信号は赤であり、赤から青に変わる時刻 (たとえば t = c_i の時) は信号は青であることに注意してください。

各交差点は、信号機の状態に関係なく到着することができますが、その交差点を出発できるのは信号機の状態が青のときのみに限られます。また、信号機による待ち時間を除いて、交差点は 0 秒で通過することができます。

さて、amylase 伯爵さんが時刻 0 で交差点 s にいるとき、そこから交差点 d へ移動するために必要な最小の所要時間を求めてください。

入力

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

n m s d
a_1 b_1 c_1
...
a_n b_n c_n
x_1 y_1 t_1
...
x_m y_m t_m

1 行目には、交差点の個数を表す整数 n (2 \leq n \leq 100{,}000)、道路の本数を表す整数 m (1 \leq m \leq min(n(n-1)/2, 10^5))、出発地点の交差点を表す整数 s (1 \leq s \leq n) と目的地点の交差点を表す整数 d (1 \leq d \leq n) が与えられる。
s \neq d であることが保証される。
続く n 行には、各交差点にある信号機の情報が与えられる。
a_i, b_i, c_i (1 \leq a_i, b_i, c_i \leq 1{,}000{,}000{,}000) は、i 番目の交差点にある信号機が最初の c_i 秒は赤であり、その後 a_i 秒の青と b_i 秒の赤を繰り返すことを意味する。
続く m 行には、各道路に関する情報が与えられる。
x_i, y_i (1 \leq x_i, y_i\leq n) と t_i (0 \leq t_i \leq 1{,}000{,}000{,}000) は、i 番目の道によって交差点 x_i と y_i の間を移動するのに t_i 秒かかることを意味する。
与えられるグラフは連結であり、自己辺や多重辺は含まれないことが保証される。

出力

交差点 s から交差点 d に移動するための最小の所要時間を 1 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。

入力例1

出力例1

出発地点である交差点 1 の信号機は時刻 4 にはじめて青になり、そこから 4 秒かけて 2 に移動すればよい。

入力例2

出力例2

J - Color Game

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

n 個の白い石が等間隔で直線上に並んでいます。隣接する石同士の距離は 1 です。

2 人のプレイヤーが、この石でゲームを行います。それぞれのプレイヤーは、自分のターンに、白い石を一つ選んで黒くするという操作を行います。ただし、直前のターンに黒くなった石から距離が k 以内の石を選ぶことはできません。

先に白い石を選べなくなったプレイヤーが負けとなります。

このゲームにおいて、互いに最善を尽くしたとき、先手と後手のどちらが勝つかを求めて下さい。

入力

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

n k

1 行目には、石の数を表す整数 n (1 \leq n \leq 50) と、選ぶことのできない距離を表す整数 k (0 \leq k \leq n) が与えられる。

出力

先手が勝つならばfirst、後手が勝つならばsecondを 1 行で出力せよ。

最後は改行し、余計な文字、空行を含まないこと。

入力例1

2 1

出力例1

first

どちらの石を選んでも、次のターンにもう一方の石を選ぶことはできないため、先手が勝ちます。

入力例2

3 0

出力例2

first

どのような順番で石を選んでも、3 つの石が黒くなるため、先手が勝ちます。