CODE FESTIVAL 2014 決勝

A - 50m走

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は、50 メートルを s 秒で走ることが出来ました。

高橋君が走った速度が、平均秒速何メートルだったかを出力しなさい。

入力

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

1 行目には、高橋君が　50 メートル走に掛かった秒数を表す整数 s (1≦s≦20) が与えられる。

出力

高橋君が走った速度が、平均秒速何メートルだったかを 1 行で出力せよ。出力の最後には改行を入れること。

なお、出力は、絶対誤差または相対誤差が 10^{-3} 以下であれば許容される。

入力例1

出力例1

高橋君は、秒速 5 メートルで走ると、 50 メートルを 10 秒で走ることが出来ます。

入力例2

出力例2

7.142857142857

出力が小数になることがあることに注意しなさい。

B - 暗算ゲーム

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は、一桁の暗算が大好きです。数字の列を使って、暗算の練習をしています。

高橋君は、奇数番目の数字が表す数を足し、偶数番目の数字が表す数を引く、という計算を繰り返します。

例えば、13458という数字の列が与えられたら、1-3+4-5+8を計算します。

高橋君のために、この計算の結果を出力するプログラムを作成してください。

入力

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

1 行目には、高橋君が計算に使用する数字の列 S (1≦|S|≦1000) が与えられる。
S に含まれる文字は、0から9までの数字のどれかであることが保障されている。

出力

問題文で指定された計算の結果を一行で出力せよ。出力の最後には改行をいれること。

入力例1

出力例1

1-3+4-5+8 を計算すると、5 になります。

入力例2

出力例2

-6

出力が負の数になることがあることに注意してください。

C - N進数

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

10 以上の整数 N に対し、 N 進数で N と表現できる数字を f(N) とします。

例えば、 f(23) は、2 × 23 + 3 = 49 のように求めることが出来ます。

整数 A が与えられます。この数字が、f(k) のような形で表すことが可能かどうかを調べたいです。

整数 A が、 10 以上の整数 k を用いて、 f(k) の形で表すことが可能であれば、k を出力し、そうでなければ -1 を出力してください。

入力

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

1 行目には、整数 A(1 ≦ A ≦ 10^{16}) が与えられる。

出力

整数 A が 10 以上の整数 k を用いて、 f(k) の形で表すことが可能であれば、k を出力し、そうでなければ -1 を出力せよ。出力の末尾には改行をいれること。

入力例1

出力例1

サンプルで与えられた通りです。

入力例2

999999999999999

出力例2

-1

大きな入力が与えられることもあります。

入力例3

10000000000000000

出力例3

D - パスカルの三角形

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は、パスカルの三角形が大好きです。

パスカルの三角形とは、一つ上の数字の、右上の数と左上の数を足した数を書き連ねていくことにより、表現することが出来る三角形です。

パスカルの三角形のy 段目は y 個の数で構成されており、 y 段目 x 番目の数を f(y,x) とすると、

x = 1、または　x = y の時、f(y,x) = 1
それ以外の時、f(y,x) = f(y-1,x) + f(y-1,x-1)

と定義されます。

高橋君は、ある整数 A が、パスカルの三角形に含まれるかどうかを調べたいと思いました。

もし、パスカルの三角形に A が現れるのであれば、その段数、及び何番目かを出力し、出現しないのであれば、-1 -1と出力しなさい。

入力

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

1 行目には、整数 A(1 ≦ A ≦ 10^9) が与えられる。

出力

もし、パスカルの三角形に A が現れるのであれば、その段数、及び何番目かをスペース区切りで出力せよ。出現しないのであれば、-1 -1と出力せよ。出力の末尾には改行をいれること。

なお、出力は、どちらの数字も 2 × 10^9 以下の整数でなければならない。

入力例1

出力例1

6 3

6 段目、 3 番目の数字は 10 です。他に 6 段目 4 番目なども条件を満たしますが、どの出力をしても問題ありません。

入力例2

出力例2

101 5

ある程度大きな数字が入力されることもあります。

E - 常ならずグラフ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Tさんは，諸行無常をモットーにいろいろなことに挑戦しています． Tさんはあるコンテストに長期的に参加していますが，そのコンテストにはレーティング機能があり，一度参加する毎にレーティングが変動します．それらの変動はグラフにまとめられています．

今，Tさんは彼のレーティング変動がプロットされたグラフを眺めています．彼はふと，グラフから一部の点を取り除いてそれらを結び，常に上下に変動しているような折れ線グラフ，名付けて「常ならずグラフ」を作りたくなりました．さらに，グラフに含まれる点の数が最も多いものに興味があります．

さて，あなたはTさんのために，彼のレーティング変動がプロットされたグラフから作ることのできる「常ならずグラフ」の中での最大の点の数を求めてあげることにしました．

あなたには，Tさんのあるコンテスト参加後でのレーティングが，N 個，時系列で与えられます．その中からいくつかの点を取り除き「常ならずグラフ」を作るとき，ありうる点の最大数を求めなさい．常ならずグラフが作れないときは 0 を出力しなさい．

あるグラフ X=\{x_1,x_2,x_3,..x_n\} が「常ならずグラフ」であるとは， |X| が 3 以上かつ， x_1＜x_2＞x_3＜x_4＞... もしくは x_1＞x_2＜x_3＞x_4<...が成り立つことを意味します．つまり，含まれる頂点数が 3 未満のとき，「常ならずグラフ」ではありません．

入力

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

N
R_1 R_2 … R_N

1 行目には，Tさんのコンテスト参加回数を表す整数 N (1 ≦ N ≦ 3000) が与えられる．
2 行目には, Tさんが i (1 ≦ i ≦ N) 番目のコンテストに参加した直後のレーティング R_i (-10^5 ≦ R_i ≦ 10^5) が空白切りで与えられる．

出力

与えられたグラフからいくつかの点を取り除き「常ならずグラフ」を作るとき，ありうる点の最大数を求め，1 行に出力しなさい．末尾の改行を忘れないこと．

入力例1

4
1 2 5 1

出力例1

入力例2

5
1 2 3 4 5

出力例2

F - 誤情報

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君はスーパーエンジニアです。最近、 2 つの正の整数の最大公約数を教えてくれるロボット「ユークリッド君」を発明しました。

高橋君はユークリッド君の性能をテストするために、N個の正の整数からなる整数列 A (1-indexed)を用意しました。

ユークリッド君には A_i と A_{i+1} の最大公約数を 1 ≦ i ≦ N について求めてもらいます。ただし A_{N+1} = A_1 とします。

ユークリッド君は A_i と A_{i+1} の最大公約数が B_i だと報告してくれました。

高橋君は B に幾つか矛盾があるように見えたので整数列 A を元にして添削しようと思いました。しかし、あいにく整数列 A のデータをなくしてしまいました。

これではユークリッド君の性能を正しく測ることができません。

しかしながら、スーパーエンジニアである高橋くんが作ったユークリッド君が間違った結果を多く報告するとは考えられません。

そこで、高橋君は B に含まれている誤情報の個数として考えられる値の中で最も小さいものを、計測結果とすることにしました。

B が含む誤情報の個数の最小値を求めてください。

入力

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

N
B_1
B_2
B_3
:
B_N

1 行目には A の要素数 N (1 ≦ N ≦ 10^5) が与えられる。
2 行目からの N 行のうち i 行目には B_i (1 ≦ B_i ≦ 10^9) が与えられる。

出力

ユークリッド君の報告した誤情報の個数の最小値を 1 行に出力せよ。出力の最後には改行を入れること。

入力例1

出力例1

B_1, B_3が正しいとすると、A_2 も A_3 も 4 の倍数なので B_2 ≧ 4 になり矛盾します。 B_2 が誤情報だとすると、矛盾がなくなりますので答えは 1 です。

入力例2

出力例2

B_8を取り除くと矛盾がなくなります。考えられるAの一例は [21, 39, 44, 28, 65, 45, 18, 34, 25, 15] です。

入力例3

出力例3

G - 魔方陣

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は魔方陣が大好きです。

魔方陣というのは3マス×3マスの方陣に相異なる正の整数を配置して、タテ・ヨコ・ナナメいずれの列についても、その列の 3 つの整数の和が等しくなっているようなものの事です。

高橋君はふと、 3 つの和が等しいのではなく 3 つの積が等しいような「積バージョンの魔方陣」が作れるのではないかと思いました。

がんばって模索したところ、下図のような積バージョンの魔方陣を1つ作ることが出来ました。

ナナメも含めたすべての列の積が 1000 になっています。

高橋君は今度は中央のマスが N であるような積バージョンの魔方陣は何種類あるのか気になりました。

ここで 90 度回転や左右反転などによって変換できる 2 つの魔方陣は区別しないとします。

高橋君のために、中央のマスが N であるような積バージョンの魔方陣の種類を求めてください。

入力

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

1 行目には積バージョンの魔方陣の中央の値 N (1 ≦ N ≦ 10^{12}) が与えられる。

出力

中央のマスが N であるような積バージョンの魔方陣の種類を 1 行で出力せよ。　出力の末尾には改行をいれること。

入力例1

出力例1

以下の様なパターンは配置されている整数が重複しているので魔方陣ではありません。

以下の様なパターンは全て回転や反転によって同じものに変換することができます。

入力例2

出力例2

入力例3

出力例3

入力例4

出力例4

H - 部屋割り

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君たちは、合宿で、N 人で、K 個の部屋に泊まることになっています。

高橋君たちは、1 から N までの数が書かれたくじを用意し、番号の小さい人から順番に、泊まる部屋を決めることにしました。

高橋君たちのグループは、静かな部屋が好きな人と、賑やかな部屋が好きな人の、2 種類の人がいます。

静かな部屋が好きな人は、出来るだけ人数の少ない部屋を好みます。今までの部屋割りで、最も人数が少ない部屋に泊まることにします。

賑やかな部屋が好きな人は、出来るだけ人数の多い部屋を好みます。今までの部屋割りで、最も人数が多い部屋に泊まることにします。

どちらのタイプの人も、もし条件を満たす部屋が複数ある場合は、条件を満たす部屋の中から、等確率で 1 つの部屋を選んで、その部屋に泊まります。

高橋君は、くじ引きが終わった後、実際に部屋割りを決める前の段階で、それぞれの参加者が、何人の人と同じ部屋で泊まることになるかを予測したいと思っています。

それぞれの参加者に対し、同じ部屋に泊まる人数の期待値を求めなさい。なお、同じ部屋に泊まる人数には、その人自身も含めることとする。

入力

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

N K
S

1 行目には、合宿に参加する人数 N (1 ≦ N ≦ 200,000) と、部屋の数 K (1 ≦ K ≦ 200,000) が、空白区切りで与えられる。
2 行目には、合宿参加者が、どのような人であるかの情報を表す文字列 S(|S| = N) が、 1 行で与えられる。
S は、0、1のどちらかの文字のみで構成され、i 番目の文字 S_i が、くじが i 番目の人の情報を表す。もし S_i が0であれば、i 番目の人が、静かな部屋が好きな人であることを表し、 1であれば、賑やかな部屋が好きな人であることを表す。

出力

それぞれの参加者に対し、同じ部屋に泊まる人数の期待値を、1 行ずつ N 行で出力せよ。

i 行目には、くじが i の人の参加者の、同じ部屋に泊まる人数の期待値を出力せよ。

なお、誤差は、相対誤差または絶対誤差が 10^{-6} まで許容される。

入力例1

7 3
1000011

出力例1

2.33333333333333
2.33333333333333
2.33333333333333
3
3
4
4

1,2,3 番目の人は、1,2,4 人部屋に等確率で泊まることになるため、期待値は 7/3 です。

4,5 番目の人は、 2,4 人部屋に等確率で泊まることになるため、期待値は 3 です。

6,7 番目の人は、 4 人部屋に泊まることになるため、期待値は 4 です。

入力例2

12 5
000000101101

出力例2

I - Shapes

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

二次元平面上で， (x_i,y_i) からのマンハッタン距離がちょうど r_i であるような点の集合から成る図形が n 個ある．どの 2 つの図形についても，それらを構成する点集合同士は共通部分を持たない．

このとき，「座標 (x1,y1) から座標 (x2,y2) に移動するときに通過しなければならない最小の点の数を答えよ」というクエリが m 個与えられるので順番に答えよ．クエリで与えられる 2 つの座標は，どの図形の点集合にも含まれないことが保障されている．

移動の際，任意の実数座標を移動することが出来るとして良い．

入力

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

n
x_1 y_1  r_1
x_2 y_2 r_2
:
x_n y_n r_n
m
x1_1 y1_1 x2_1 y2_1
x1_2 y1_2 x2_2 y2_2
:
x1_m y1_m x2_m y2_m

1 行目には，図形の数を表す整数 n (1 ≦ n ≦ 10^5) が与えられる．
1 行目から n 行，各図形の情報を表す 3 つの整数 x_i,y_i,r_i (-10^8 ≦ x_i,y_i ≦ 10^8, 1 ≦ r_i ≦ 10^8) が与えられる．どの2つの図形についても，それらを構成する点集合同士は共通部分を持たない．
n+1 行目には，クエリの数を表す整数 m (1 ≦ m ≦ 10^5) が与えられる．
n+2 行目から m 行，各クエリの2情報を表す 4 つの整数 x1_i,y1_i,x2_i,y2_i (-10^8 ≦ x1_i,y1_i,x2_i,y2_i ≦ 10^8) が与えられる．この2つの座標は，どの図形の点集合にも含まれないことが保障されている．

出力

1行目から m 行，各クエリについての答えを与えられた順番に改行区切りで出力せよ．最後の行においても改行を行うこと．

入力例1

出力例1

入出力例1を表した図は以下の通りです．

入力例2

出力例2

入出力例2を表した図は以下の通りです．

J - 2つのカップ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

水が A リットル入るカップと、水が B リットル入るカップが 1 つずつあります。

カップが空の状態から始めて、次のいずれかの操作を繰り返し行うことにより、いずれかのカップに水が C リットルたまる状態にしたいです。

一方のカップを水でいっぱいにする。
一方のカップを空にする。
一方のカップ X からもう一方のカップ Y に、 Y がいっぱいになるか X が空になるまで、水をこぼさずにうつす。

A, B, K が与えられるので、 K 回以内の操作で実現できる相異なる C は何通りあるかを求めなさい。

入力

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

A B K

1 行目には，カップの容量を表す整数 A,B (1 ≦ A, B ≦ 10^{10}) と、操作可能な回数を表す整数 K (0 ≦ K ≦ 10^{10}) が与えられる。

出力

実現できる相異なる C は何通りあるかを求めよ。出力の最後には改行を入れること。

入力例1

3 4 2

出力例1

まず、 0 は初期状態で実現されています。

3 および 4 は、それぞれの容量のカップの水を満たす、 1 回の操作で達成可能です。

1 は、容量 4 のカップに入れた水を、空になっている容量 3 のカップに移す、2 回の操作で実現できます。

2 は、2 回の操作で実現することは出来ず、 4 回の操作が必要となります。

入力例2

7 3 0

出力例2

操作不可能なので、空の状態、つまり 0 のみを実現することしかできません。

入力例3

174324 96581 5000