A - 与えられた数より小さい素数の個数について

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

問題文

素数とは、1 と自分自身以外に正の約数を持たない、1 以外の自然数のことをいいます。

自然数 n が与えられるので、 n よりも小さい素数の数は何個存在するかを求めてください。

入力

入力は以下の形式で標準入力から与えられる。 
n
  • 自然数 n ( 1 \leq n \leq 10,000 ) が 1 行で与えられる。

出力

n よりも小さい素数の個数を標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。

入力例 1

11

出力例 1

4
  • 11 よりも小さい素数は、 2 , 3 , 5 , 7 の 4 つです。
  • ※ 「11 よりも小さい」なので、11 は含みません。

入力例 2

100

出力例 2

25

入力例 3

10000

出力例 3

1229
B - ロイヤルストレートフラッシュ

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

問題文

シャッフルされたトランプの山札が与えられる。
ここからロイヤルストレートフラッシュを作りたい。
山札からカードを 1 枚ずつめくり、手札に入れるか捨てるという操作を繰り返す。
最短でロイヤルストレートフラッシュが完成したときの捨て札を、カードを捨てた順に出力せよ。
なお、初期状態で手札は空とし、ロイヤルストレートフラッシュが完成したとき、手札に余分なカードが存在してはならない。


与えられる山札を表す文字列は、以下のBNFに従う。 

<山札>   ::= <カード> | <山札> <カード>
<カード> ::= <マーク> <番号>
<マーク> ::= "S" | "H" | "D" | "C"
<番号>   ::= "A" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "10" | "J" | "Q" | "K"

ロイヤルストレートフラッシュとは、同じマークの「10、J、Q、K、A」の組み合わせのことを言う。
すなわち、「S10, SJ, SQ, SK, SA」、「H10, HJ, HQ, HK, HA」、「D10, DJ, DQ, DK, DA」、「C10, CJ, CQ, CK, CA」のカードの組み合わせ 4 種類がロイヤルストレートフラッシュである。

入力

入力は以下の形式で標準入力から与えられる。 
s
  • 山札のカードを表す文字列 s が 1 行で与えられる。
  • 山札にはマークと番号の両方が等しいカードの組は存在しない。
  • ロイヤルストレートフラッシュを作ることが可能であることが保証される。

出力

ロイヤルストレートフラッシュを最短で作ったときの捨て札を表す文字列を 1 行で出力せよ。
捨て札はカードを捨てた順に記述する必要がある。
捨て札が無い場合は、 0 (数字のゼロ) を出力せよ。
なお、行の終端には改行が必要である。

入力例 1

CQSAS10SQH10SKSJD3

出力例 1

CQH10
  • 「CQ」 と 「H10」 を手札に入れずに捨てると、 7 枚めくった時点で、手札が「SA, S10, SQ, SK, SJ」 の 5 枚となり、ロイヤルストレートフラッシュが完成する。

入力例 2

S10SJSQSKSAC2

出力例 2

0
C - 席替え

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

問題文

急成長中のK社は、ハイペースで採用しすぎて席が足りなくなってしまいました。
次のオフィスの移転先は決まっていたのですが、大人の事情により現在のオフィスを拡張することになりました。
オフィスが広くなったので、席替えが必要です。
K社は非常に忙しいので、席替えにできるだけ時間を使いたくありません。


席替えにはカートを使う必要があります。
席の荷物をカートに載せるのに 5 分、カートから席に荷物を下ろすのに 5 分かかります。
1 台のカートには 1 人分の荷物しか載せることができません。
このとき、カートに荷物を載せ始めてから下ろし終えるまでは、カートに荷物が載っているものとし、他の人の荷物を載せることはできません。
移動先の席に荷物がある場合、荷物を下ろすことができません。
このとき、席の荷物をカートに載せ終わるまでは席に荷物があるものとします。
また、席替え後の席でなくても、荷物の無い席に一時的に荷物を下ろすことができますが、1つの席に複数の人の荷物を置くことはできません。

席替え前と席替え後の座席表と、カートの台数が与えられるので、席替えにかかる最小時間を計算してください。
カートの性能は非常に良いので、荷物を載せ終わってから移動先の席への移動には時間がかからないものとします。

入力

入力は以下の形式で標準入力から与えられる。 
N M L
a_{1} b_{1}
:
a_{L} b_{L}
  • 入力は L+1 行ある。
  • 1 行目には、席の数を表す N ( 1 \leq N \leq 30 ) と カートの数を表す M ( 1 \leq M \leq N ) と 社員の数を表す L ( 1 \leq L \leq N かつ L \leq 15 ) が空白区切りで与えられる。
  • 2 行目からの L 行には、 i ( 1 \leq i \leq L ) 番目の社員の席替え前の席の番号 a_{i} ( 1 \leq a_{i} \leq N ) と席替え後の席の番号 b_{i} ( 1 \leq b_{i} \leq N ) が空白区切りで与えられる。
  • i \neq j ならば a_i \neq a_j である。
  • i \neq j ならば b_i \neq b_j である。

部分点

席の数が少ない入力 ( 1 \leq N \leq 7 ) のみ正解すると、100 点満点に対して部分点として 50 点が与えられる。

出力

席替えにかかる最短時間を分単位で出力せよ。
席替えが不可能な場合は、 -1 を出力せよ。
なお、行の終端には改行が必要である。

入力例 1

3 3 3
1 2
2 3
3 1

出力例 1

10
  • 席替え開始時に、3人の荷物を3つのカートに載せ始める。
  • 席替え開始から5分後に、3人の荷物をそれぞれの移動先に下ろし始める。
  • 以上により、10分で席替えが完了する。

入力例 2

3 2 3
1 2
2 3
3 1

出力例 2

20
  • 席替えの例を以下に示す。
  • 席替え開始時に、番号1の席と番号2の席の荷物をカートに載せ始める。
  • 席替え開始から5分後に、番号1の席にあった荷物を、カートから番号2の席に下ろし始める。
  • 席替え開始から10分後に、番号3の席の荷物をカートに載せ始める。
  • 席替え開始から15分後に、カート上にある2人の荷物をそれぞれの移動先に下ろし始める。
  • 以上により、20分で席替えが完了する。

入力例 3

3 1 3
1 2
2 3
3 1

出力例 3

-1
  • この場合、席替えは不可能である。

入力例 4

4 1 3
1 2
2 3
3 1

出力例 4

40
  • この場合、空席を利用することで40分で席替えすることができる。
D - ゆうびんやさんのお花畑

実行時間制限: 5 sec / メモリ制限: 64 MB

問題文

あるところに妖精さんたちの住む村がありました。
図 1 は妖精さんの村の例です。妖精さんの村はマス目から成る長方形の形をしており、家と空き地と木で構成されています。

図 1：妖精さんの村の例

村には各妖精さんの家をまわって郵便配達をする妖精さん『ゆうびんやさん』がいます。
ゆうびんやさんには郵便配達のときに守らなければいけない以下の 5 つの規則があります。

  1. 村にある全ての家に入って郵便を届けなければならない。
  2. 木はよけなければならなく、空き地と家のみ通ってよい。また村の外は通ってはいけない。
  3. 配達する時に通る空き地は何度同じ場所を通ってもよい。
  4. 隣接した東西南北 4 方向のうち空き地である場所からのみ家に入らなければならない。
  5. 家への出入りは 1 つの方向からのみ行わなくてはならない。つまり、家を通り抜けてはならない。

例えばゆうびんやさんが配達に用いる経路の例を 1 つ挙げると図 2(a) のオレンジの線になります。
このとき、家は通り抜けてはいけない規則により図 2(b) のような配達経路は規則違反になります。

図 2(a)：配達経路の例　　　図 2(b)：規則違反の配達経路

さて、妖精さんたちはお花が大好きなので、ゆうびんやさんの配達経路以外の全ての空き地をお花畑にしたいと考えました。
その時のお花畑にできるマス目の個数の最大値を答えなさい。
なお、規則を守った配達経路が存在しない場合は -1 と答えなさい。

入力

入力は以下の形式で標準入力から与えられる。 
H W
c_{(0,0)}c_{(1,0)}‥‥c_{(W-1,0)}
c_{(0,1)}c_{(1,1)}‥‥c_{(W-1,1)}
:
:
c_{(0,H-1)}c_{(1,H-1)}‥‥c_{(W-1,H-1)}
  • 入力は H+1 行ある。
  • 1 行目には、長方形の形である妖精さんの村の南北の距離を表す整数 H(4≤H≤10) と 東西の距離を表す整数 W(4≤W≤10) が空白を区切りとして与えられる。
  • 2 行目からの H 行には、各行に妖精さんの村の各マス目の土地の利用状況を表す状態 c_{(i,j)}(0≤i≤W-1, 0≤j≤H−1) が W 文字ずつ与えられる。
    • c_{(i,j)} は下記のいずれかであり、それぞれ西から i+1 番目の北から j+1 番目のマスの土地が何であるかを表す。
      • H : そのマスの土地に家があることを表す。
      • # : そのマスに木があることを表す。
      • . : そのマスが空き地であることを表す。
    • 妖精さんの村に存在する家の総数は 3 以上 W×H 以下である。

出力

妖精さんの村の大きさが小さい入力 (W=4, H=4) のみ正解すると、100 点満点に対して部分点として 50 点が与えられる。

出力

配達経路以外の空き地をお花畑にした場合のお花畑のマス目の個数の最大値を標準出力に 1 行で出力せよ。
ただし、規則を守った配達経路が存在しない場合は -1 を出力せよ。 なお、最後には改行を出力せよ。

入力例 1

4 4
...H
#H..
...#
H..H

出力例 1

5
  • 下図のようにお花畑を作ると、配達経路は規則を守ることができ、お花畑は 5 個になります。

入力例 2

4 4
....
....
.HHH
....

出力例 2

10
  • 家同士が隣接していても直接家と家を移動することはできません。
  • したがって家に隣接する北側の空き地 3 つ、または南側の空き地 3 つには花を植えられないので、お花畑は最大で 10 個になります。

入力例 3

4 4
...H
.#.#
.#.#
H#.H
修正：2012/08/29 19:40　右上のHが#になっている誤りがありましたので、修正させて頂きました。申し訳ありません。
なお、この修正によっての出力例への変更はありません。

出力例 3

0
  • 全ての空き地が配達経路上にあるので、お花畑は作ることができません。

入力例 4

4 4
HH.H
H##.
.##.
H..H

出力例 4

-1
  • 北から 1 番目で西から 1 番目のマスにある家には配達できないことや、家を通り抜けないと配達できないことから、配達規則を守ることができません。

入力例 5

10 10
..##.H....
.H.#......
...#####..
##......#.
.#...#.H..
.....#....
.##H..####
..##....H.
.H..#.....
...#......

出力例 5

36

出典

天下一プログラマーコンテスト2012 予選C