A - アルバム

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

高橋君は子供の頃の写真を整理している。

整理している最中に、写真を入れている木箱が出てきたので、木箱内にある写真をアルバムに貼って整理することにした。どの位の大きさのアルバムが必要なのか確認するために、木箱の中にある写真の枚数が知りたくなった。

高橋君はすべての写真に正整数の通し番号を付けており、木箱内には通し番号が S 以上 T 以下であるすべての写真が入っている。

高橋君は、木箱にある写真の枚数が知りたいが、写真を 1 枚ずつ数えるのは大変である。

あなたは高橋くんの代わりに、S と T の値からアルバムに貼られている写真の枚数を計算するプログラムを作成せよ。

入力

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

S T
  • 1 行目には、アルバムに貼られている写真の範囲を表す 2 つの整数 S,T (1 ≦ S ≦ T ≦ 1,000) が与えられる。

出力

木箱内にある写真の枚数を出力せよ。出力の末尾にも改行を入れること。

入力例1

4 7

出力例1

4

通し番号が 4, 5, 6, 7 の合計 4 枚の写真が該当します。

入力例2

1 1

出力例2

1

通し番号が 1 の写真のみが該当します。

B - 投票

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

とある組織で、リーダーを選ぶ選挙が行われた。

組織は N 人の構成員で構成されており、各人は最もリーダーにふさわしい人物の名前を書いた。

リーダーは、得票数が最も多い人物が選ばれることになっている。

得票数が最も多い人物の名前を出力せよ。得票数が最も多い人物が複数いる場合は、そのうちどの名前を出力してもよい。

入力

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

N
S_1
S_2
:
S_N
  • 1 行目には、組織の構成員の人数を表す整数 N (1 ≦ N ≦ 50) が与えられる。
  • 2 行目から N 行では、それぞれの構成員の投票内容を表す。N 行のうち i (1 ≦ i ≦ N) 行目には文字列 S_i が書かれている。S_i は i 番目の人の投票内容を表している。S_i は小文字の半角英字のみで構成されており、長さは 1 文字以上 50 文字以下である。

出力

得票数が最も多い人物の名前を出力せよ。得票数が最も多い人物が複数いる場合は、そのうちどの名前を出力してもよい。出力の末尾にも改行を入れること。

入力例1

4
taro
jiro
taro
saburo

出力例1

taro

taro が 2 票、jiro と saburo が 1 票ずつです。

入力例2

1
takahashikun

出力例2

takahashikun

takahashikun 以外の投票がありません。

入力例3

9
a
b
c
c
b
c
b
d
e

出力例3

b

b が 3 票で最多ですが、c も 3 票で同様に最多なので、c を出力しても正解となります。

C - コイン

実行時間制限: 2 sec / メモリ制限: 256 MB

問題文

高橋君は裏表が区別できる N 枚のコインを持っている。コインの大きさは異なり、それぞれのコインには 1 つずつ正の整数が書かれている。

これらのコインを無作為に (N! 通りの組み合わせがすべて同じ確率で出てくるように) 一列に並べる。その後、以下の手順を実行する。

  1. すべてのコインを表向きにする。
  2. 左端のコインから順に、現在見ているコインよりも右側 (それ自身を除く) にあるコインのうち、現在見ているコインに書かれている整数の倍数が書かれているコインすべての裏表をひっくり返す。

高橋君はこの操作を終了した後に表を向いているコインの枚数の期待値が知りたい。

あなたは高橋くんの代わりに、期待値を計算するプログラムを作成してほしい。

入力

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

N
C_1
C_2
:
C_N
  • 1 行目には、コインの枚数を表す整数 N (1 ≦ N ≦ 100) が与えられる。
  • 2 行目から N 行のうち i (1 ≦ i ≦ N) 行目には、i 番目に大きいコインに書かれている整数 C_i (1 ≦ C_i ≦ 10^9) が書かれている。

部分点

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

  • N ≦ 8 を満たすデータセット 1 に正解した場合は、99 点が与えられる。
  • 追加制約のないデータセット 2 に正解した場合は、さらに 1 点が与えられ、合計で 100 点が得られる。

出力

表を向いているコインの枚数の期待値を出力せよ。絶対誤差または相対誤差が 10^{-6} 以下であれば許容される。出力の末尾にも改行を入れること。

入力例1

3
2
4
8

出力例1

2.166666666667

コインには、サイズの小さい方から順にそれぞれ 2 , 4 , 8 という数が書かれています。例えば、3! 通りの並べ方のうち、コインが大きさの昇順に並んでいる場合は、以下の手順が行われることになります。

  1. 初期状態で、すべてのコインを表に向けるので、コインは左から順に、[表, 表, 表] となっています。
  2. 次に、左から 2 番目以降のコインの中で、2 の倍数が書かれたコインを探します。左から 2 番目のコインと左から 3 番目のコインが該当するので、これらのコインを裏返します。その結果、コインは左から順に [表, 裏, 裏] となります。
  3. 次に、左から 3 番目以降のコインの中で、4 の倍数が書かれたコインを探します。左から 3 番目のコインのみが該当するので、このコインを裏返します。その結果、コインは左から順に [表, 裏, 表] となります。

コインの裏表は下図のように変化します。この図において、白いコインは表向きのコイン、黒いコインは裏向きのコインで表してあります。

このように、3! = 6 通りの並べ方について、それぞれの並べ方での最終状態は下図のようになります。

以上より期待値は 13/6 = 2.16666666666... となります。

入力例2

4
5
5
5
5

出力例2

2.000000000000

どのような順番で並べても、左から順に、[表, 裏, 表, 裏] となります。

入力例3

5
2
3
2
6
12

出力例3

3.100000000000
D - 金塊ゲーム

実行時間制限: 4 sec / メモリ制限: 512 MB

問題文

高橋君はとあるゲームをプレイしている。このゲームでは縦横方向に無限に広がるマス目の上で行われる。各マス目は正方形状で、各辺は東西方向または南北方向に平行である。マス目のうちあるマスには (0,0) という数字の組が割り当てられており、このマスから東方向に x マス (x<0 のときは西方向に -x マス)進み、北方向に y マス (y<0 のときは南方向に -y マス)進んだところにあるマスには (x,y) という数字の組が割り当てられている。

マス目上には W × H 個の金塊がある。これらの金塊は 1 ≦ p ≦ W かつ 1 ≦ q ≦ H を満たすすべてのマス (p,q) に 1 個ずつ置かれている。また、金塊があるマスのうちちょうど N マスには金塊回収装置がある。装置には 1 から N までの番号が付いている。どの 2 つのマス (a,b) , (c,d) に関しても、2 つのマスの両方に装置があるならば、a≠c かつ b≠d である。また、複数の装置が同じマスにあることはない。最初、どの金塊回収装置も作動していない。

金塊回収装置は作動すると、まずは装置のあるマスにある金塊を回収する。その後、東西南北それぞれの方向にクレーンを伸ばすことで更に金塊を回収することができる。クレーンの性質上、クレーンを下ろす場所には金塊がなく、かつ回収する区間では金塊が連続して存在していなければならない。つまり、クレーンのあるマスを (x,y) としたとき、以下に示す条件でのみクレーンを下ろし、金塊を回収することができる。

  • 東方向に回収する処理：次の条件を満たす整数 p を選ぶ。その後、x+1 ≦ i ≦ p-1 を満たすすべてのマス (i,y) の金塊を回収する。

    • 条件：p > x+1 であり、x+1 ≦ i ≦ p-1 を満たすすべてのマス (i,y) に金塊があり、かつマス (p,y) に金塊がない。

  • 西方向に回収する処理：次の条件を満たす整数 p を選ぶ。その後、p+1 ≦ i ≦ x-1 を満たすすべてのマス (i,y) の金塊を回収する。

    • 条件：p < x-1 であり、p+1 ≦ i ≦ x-1 を満たすすべてのマス (i,y) に金塊があり、かつマス (p,y) に金塊がない。

  • 南方向に回収する処理：次の条件を満たす整数 q を選ぶ。その後、q+1 ≦ j ≦ y-1 を満たすすべてのマス (x,j) の金塊を回収する。

    • 条件：q < y-1 であり、q+1 ≦ j ≦ y-1 を満たすすべてのマス (x,j) に金塊があり、かつマス (x,q) に金塊がない。

  • 北方向に回収する処理：次の条件を満たす整数 q を選ぶ。その後、y+1 ≦ j ≦ q-1 を満たすすべてのマス (x,j) の金塊を回収する。

    • 条件：q > y+1 であり、y+1 ≦ j ≦ q-1 を満たすすべてのマス (x,j) に金塊があり、かつマス (x,q) に金塊がない。

それぞれの方向に関して、条件を満たす p または q が存在しない場合は、その方向にクレーンを伸ばすことができない。

また、それぞれの方向に関して、金塊を回収可能ならば、必ず回収しなければならない。下に条件を満たす回収方法の一例を示す。ただし、以降の図において装置を M の記号で表し、回収可能な範囲は太枠で表している。

高橋君はすべての装置を順番を決めて作動させるつもりである。作動の順番によっては、最終的に得られる金塊の個数が変化するかもしれない。金塊が大好きな高橋君は、最終的に得られる金塊の個数をできるだけ多くしようと考えている。

あなたは高橋くんの代わりに、最大値を計算するプログラムを作成してほしい。

入力

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

W H
N
X_1 Y_1
X_2 Y_2
:
X_N Y_N
  • 1 行目には、金塊の個数と配置に関する 2 つの整数 W (1 ≦ W ≦ 10^6) と H (1 ≦ H ≦ 10^6) が空白区切りで与えられる。
  • 2 行目には、金塊回収装置の個数を表す整数 N (1 ≦ N ≦ 30) が与えられる。
  • 3 行目から N 行のうち i (1 ≦ i ≦ N) 行目には、i 番目の装置があるマスに関する 2 つの整数 X_i (1 ≦ X_i ≦ W) と Y_i (1 ≦ Y_i ≦ H) が空白区切りで与えられる。これは、i 番目の装置がマス (X_i , Y_i) にあることを表す。

また、この入力では、さらに以下の条件も満たされる。

  • 任意の 2 つの整数 i,j (1 ≦ i < j ≦ N) について、X_i ≠ X_j かつ Y_i ≠ Y_j である。

部分点

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

  • N ≦ 8 , W ≦ 80 , H ≦ 80 を満たすデータセット 1 に正解した場合は、80 点が与えられる。
  • W ≦ 80 , H ≦ 80 を満たすデータセット 2 に正解した場合は、さらに 19 点が与えられ、合計で 99 点が得られる。
  • 追加制約のないデータセット 3 に正解した場合は、さらに 1 点が与えられ、合計で 100 点が得られる。

出力

回収可能な金塊の個数の最大値を出力せよ。出力の末尾にも改行を入れること。

入力例1

6 4
3
2 4
3 1
4 3

出力例1

19

入力例 1 において、初期状態は以下のようになっています。

以下に示すように、1 番目、2 番目、3 番目の装置という順番で実行することにより、19 個の金塊を回収できます。

入力例2

3 3
3
1 1
2 3
3 2

出力例2

9

うまく稼働させればすべての金塊を回収することができます。

入力例3

15 10
8
7 10
12 8
4 4
5 7
9 9
1 6
6 5
3 2

出力例3

112