A - 鉛筆リサイクルの新技術

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

世界的大手鉛筆会社のファイバーカステラ社が、小さくなって使えなくなってしまった鉛筆を再利用する画期的な新技術を発明した。
この技術は小さくなった鉛筆 m 本から新しい鉛筆を n 本 (m > n) 作り出すものである。
ファイバーカステラ社が N 本の鉛筆を製造・販売し、その全てが使用されて回収され、回収された使えなくなった鉛筆から新しい鉛筆を作る。
これらを販売し、やはり全てが使用後回収されて新たな鉛筆の原料となる。これを繰り返した結果として、ファイバーカステラ社が総計何本の鉛筆を販売できるか計算するプログラムを作成せよ。
再利用する際に、回収されたにもかかわらず新しい鉛筆の原料とされなかった鉛筆を保持しておき、任意のタイミングで回収した鉛筆に加えても良い。
販売できる本数には、はじめの N 本も忘れずに加えること。また、 N > m とし、m と n が互いに素であるとする。

入力

入力は以下の形式で標準入力から与えられる。 自然数 m 、 n 、 N がこの順に半角空白区切りで入力される。 
m n N
  1. 1 行目には整数 m 、 n 、N が与えられる。
    • m は小さくなって使えなくなってしまった鉛筆の数である。
    • n はファイバーカステラ社が作り出す新しい鉛筆の本数である。
    • N はファイバーカステラ社が最初に販売する鉛筆の本数である。
    • (1≦n<m<N≦1,000) であり、m と n が互いに素であることは保証されている。

出力

ファイバーカステラ社が販売する鉛筆の総数を標準出力に 1 行で出力すること。
この数には使い終わった後に再度製造された鉛筆も含まれる。
また、出力の最後には改行をいれること。

入力例 1

2 1 8

出力例 1

15
  1. 初めに、鉛筆を8 本販売する。
  2. 販売した 8 本を回収する。2 本から 1 本鉛筆を作るので新たに 4 本作成し、販売する。
  3. 販売した 4 本を回収する。2 本から 1 本鉛筆を作るので新たに 2 本作成し、販売する。
  4. 販売した 2 本を回収する。2 本から 1 本鉛筆を作るので新たに 1 本作成し、販売する。
  5. 販売した 1 本を回収する。2 本から 1 本鉛筆を作るが、 1 本しか回収できなかったので、新たに作成することができない。
  • 販売した鉛筆の合計は 8 + 4 + 2 + 1 = 15 本である。

入力例 2

7 4 30

出力例 2

62
  1. 初めに、鉛筆を30 本販売する。
  2. 販売した 30 本を回収する。鉛筆を新たに 16 本作成し、販売する。このとき、 2 本だけ再利用されない。
  3. 販売した 16 本を回収する。鉛筆を新たに 8 本作成し、販売する。このときも、 2 本再利用されない鉛筆があり、計 4 本再利用されていない。
  4. 販売した 8 本を回収する。鉛筆を新たに 4 本作成し、販売する。このとき、 1 本再利用されない鉛筆があり、計 5 本再利用されていない。
  5. 販売した 4 本を回収する。鉛筆 7 本から新たに 4 本鉛筆を作りたいが、販売した 4 本しか回収できなかったので、これだけでは新たに作成することができない。このとき、 回収した 4 本の鉛筆に新しい鉛筆の原料とされなかった 5 本の鉛筆を追加し、計 9 本の再利用されていない鉛筆がある。
  6. 再利用されていない鉛筆が 9 本あるので、そのうち 7 本から新たに 4 本鉛筆を作成し、販売する。このとき、 2 本再利用されない鉛筆がある。
  7. 販売した 4 本を回収する。7 本から 4 本鉛筆を作るが、 回収した 4 本と余った 2 本の鉛筆を足しても 6 本なので、新たに鉛筆を作成することができない。
  • 販売した鉛筆の合計は 30 + 16 + 8 + 4 + 4 = 62 本である。

入力例 3

100 99 1000

出力例 3

90199
B - ルイス・キャロルの記憶術

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

古今東西、数字の記憶には様々な方法が取り入れられてきた。
例えば日本では e の値を「鮒一鉢二鉢一鉢二鉢至極惜しい」などとして記憶するし、欧米では π の値を Yes, I know a number! として記憶する。 「不思議の国のアリス」の著者として知られるルイス・キャロル (本名:チャールズ・ラトウィッジ・ドジソン) は、子音のみを用いた独自の記憶術を作り、様々な年号を記憶していたらしい。 これによれば、次のように、文字に数字を割り当てていたという。
図：文字から数字への割り当て
この表に従い、覚えたい数字を子音に変換し、これを用いた単語をひとつ作って文にすることで、キャロルは年号などを覚えていたという。
なお、子音以外の文字 (a,e,i,o,u,y や、コンマ、ピリオド等) はすべて無視され、大文字も小文字も同じように変換される。

例えば、モーツァルトの正没年は Mozart plays magic. とし、plays を 756 に変換し、 magic を 791 に変換して、 1756 年 ～ 1791 年と覚えることができるわけ である。 この方式での記憶文が与えられるとき、それを前から順に変換し、変換した数字を出力するプログラムを作成せよ。

入力

入力は以下の形式で標準入力から与えられる。
N
w_{0} w_{1} ... w_{N-1}
  1. 1 行目は単語の数を表す整数 N(1≦N≦1,000) が与えられる。
  2. 2 行目は単語が半角スペース区切りで与えられる。
    • 単語とは半角英字 ピリオド コンマから構成される。
    • 各単語は 1 文字以上 30 文字以内である。

出力

与えられた単語から変換された数字を 1 行で出力せよ。
ただし、変換された数字と数字の間には半角スペースを 1 つ入れること。
整数の頭に 0 がつく場合もあるが、その場合は 0 も出力すること。
また、出力の最後には改行をいれること。

入力例 1

3
Mozart plays magic.

出力例 1

7003 756 791
  • 変換表により、MozartのMを 7 に変更します。
    zを 0 に変更します。
    rを 0 に変更します。
    tを 3 に変更します。
    こうして、Mozartから 7003 へ変換することができました。
  • 同様にして、playsから 756 へ、magicから 791 へ変換します。

    • 入力例 2

    3
Columbus found USA.

    出力例 2

    15716 492 6
    • Columbus を変換して 15716
    • found を変換して 492
    • USA を変換して 6 をそれぞれ得ることができます。

    入力例 3

    7
I have a scissors for right hand.

    出力例 3

    85 616606 40 0983 892
    • Iやaは母音のみからなる単語ですので、これらの単語は無視され、全部で 5 個の整数が出力されます。

    入力例 4

    4
abc ab aa aiueo

    出力例 4

    11 1
    • 最後に余分な空白を入れてはいけません。

    入力例 5

    [訂正] 2013.01.19 21:16　1 行目が誤って 5 になっておりましたので、修正いたしました。 
    4
aaa aa a aa

    出力例 5
    • 母音のみからなる単語しかないので、最後の改行のみが出力されます。
    C - ダブレット

    Time Limit: 2 sec / Memory Limit: 256 MB

    2013.01.19 21:28　入力の制限に「単語は英小文字のみで構成される」ことを追記しました。
    2013.01.20 21:03　入力の制限の、単語リストに含まれる単語の条件を訂正しました。

    問題文

    ヨーロッパでよく知られている言葉遊びとして「ダブレット」がある。
    これは、ある単語から別の単語へ、一文字ずつ文字を変えていくことによって変換する、というものである。
    例えば、head を tail に変える場合、4 単語を経由し、head→heal→teal→tell→tall→tailと変換することができる。
    与えられた単語リストを用いてダブレットをするとき、変換する過程を表示するプログラムを作成せよ。
    ただし、変換することが可能であるならば、その変換回数は最小でなければならない。

    入力

    入力は以下の形式で標準入力から与えられる。 
    first last
N
s_{0}
s_{1}
:
s_{N-1}
    1. 1 行目に最初の単語 first と、最後の単語 last が半角スペースで区切られて与えられる。
    2. 2 行目に単語リストに含まれる単語の個数を表す整数 N(1≦N≦1,000) が与えられる。
    3. 3 行目から N+2 行目までの N 行は単語リストが与えられる。
      • 単語リストの中に同じ単語が複数含まれることもあり、単語リストの中に最初の単語 first と、最後の単語 last が含まれることもある。
      • しかし、最初の単語 first と、最後の単語 last が同じパターンは入力としてありうる。
      • 各単語の文字数は全て等しく、1 文字以上 30 文字以下とする。
      • 各単語は英小文字 a-z のみで構成される。

    出力

    変換が可能な場合、 1 行目に変換に用いる単語の個数 k を出力し、続く k+2 行で最初の単語と最後の単語を含めた変換過程を出力せよ。
    ただし、k が最小となる変換過程でならなければならない。
    変換過程は 1 行につき 1 つの単語のみ出力すること。
    変換過程が複数ある場合、どれを出力しても構わない。
    最初と最後の単語が同じ単語である場合は k=0 である。
    変換できない場合には、-1 とだけ出力せよ。
    また、出力の最後には改行をいれること。

    入力例 1

    eye lid
4
lie
die
did
dye

    出力例 1

    3
eye
dye
die
lie
lid
    1. 1 行目には変換に用いる単語数である 3 を出力する。
    2. 2 行目以降は変換する過程を出力する。
      • eye ... 最初の単語 first である。
      • dye ... eyeの 1 文字目であるeをdへ変換した。
      • die ... dyeの 2 文字目であるyをiへ変換した。
      • lie ... dieの 1 文字目であるdをlへ変換した。
      • lid ... lieの 3 文字目であるeをdへ変換した。また、最後の単語 last なので終了する。

    入力例 2

    eye eye
4
lie
die
did
dye

    出力例 2

    0
eye
eye
    • 最初の単語 first と、最後の単語 last が一致するので、変換に用いる単語数は 0 である。
    • 最初の単語 first と、最後の単語 last をそれぞれ 1 行で出力して終了する。

    入力例 3

    eye lid
4
lie
lip
did
dye

    出力例 3

    -1
    • 与えられた単語リストのみを用いてeyeからlidへ変換することができないので、-1を出力する。
    D - きつねさんからの挑戦状

    Time Limit: 2 sec / Memory Limit: 256 MB

    2013.01.19 21:56 R の範囲を変更しました。

    問題文

    きつねのグレイは街中に秘密の兵器工場を作ろうとしています。
    彼は人間たちに工場の場所を知られたくないので、人間の住居が少ない辺鄙な場所に工場を建てようとしています。
    あなたはグレイの工作活動を阻止するために派遣された某国のエージェントで、任務のために某国から街の地図が支給されています。
    街は道路と住居で構成されており、それらは全て地図に記されています。
    地図は 2 次元平面で、道路は直線、住居は座標であるとみなします。

    いま別のエージェントからグレイが工場を建てる場所についての情報が入りました。
    1. グレイが考えている見つかりにくさとは、兵器工場から一番近い道路からの距離と、一番近い住居からの距離に依存する。
      • 兵器工場の座標を (x, y)
      • 兵器工場から一番近い道路への距離を dist_{road}(x, y)
      • 兵器工場から一番近い住居を dist_{point}(x, y)
      とそれぞれ定義したとき、見つかりにくさを示す評価関数 f(x, y) は、 f(x, y) = dist_{road}(x, y) + dist_{point}(x, y)^2 と表すことができる。
    3. グレイは評価関数 f(x, y) が最も大きくなるような座標 (x, y) に兵器工場を建てる。
    4. 兵器工場の座標 (x, y)　は、ある整数 R に対して -R≦x,y≦R を満たす。
    5. 座標 (x, y)　はともに実数である。

    あなたはこの情報と地図を頼りに、グレイが兵器工場を建設する予定の場所を突き止めるため、評価関数 f(x, y) の最大値を求めることにした。

    入力

    入力は以下の形式で標準入力から与えられる。 
    N M R
a_{0} b_{0} c_{0}
:
a_{N-1} b_{N-1} c_{N-1}
p_0 q_0
:
p_{M-1} q_{M-1}
    1. 1 行目には 3 つの整数 N M R が半角スペース区切りで与えられる。
      • N は道路の個数であり、 1≦N≦16 を満たす。
      • M は住居の個数であり、 1≦M≦16 を満たす。
      • R はグレイが建設する兵器工場の座標 (x, y) に関する制約で、 1≦R≦1,000 を満たす。
    2. 2 行目から N+1 行目までの N 行は道路に関する 3 つの整数 a_i b_i c_i が半角スペース区切りで与えられる。
      • i番目の道路は直線 a_ix + b_iy + c_i = 0 として与えられる。
      • a_i は -1,000≦a_i≦1,000 を満たす。
      • b_i は -1,000≦b_i≦1,000 を満たす。
      • c_i は -1,000≦c_i≦1,000 を満たす。
      • a_i = 0 かつ b_i = 0 となるようなケースは与えられない。
    3. N+1 行目から N+1+M 行目までの M 行は住居に関する 2 つの整数 p_j q_j が半角スペース区切りで与えられる。
      • j番目の住居は座標 (p_j, q_j) として与えられる。
      • p_j は -1,000≦p_j≦1,000 を満たす。
      • q_j は -1,000≦q_j≦1,000 を満たす。
    4. 直線は同一のものが複数与えられる可能性があり、これは座標についても同じである。

    出力

    見つかりにくさを示す評価関数 f(x, y) の -R≦x,y≦R における最大値を 1 行で出力せよ。
    出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{−6} 以下であれば許容される。
    また、出力の最後には改行をいれること。

    入力例 1

    4 4 1
1 1 2
1 1 -2
1 -1 2
1 -1 -2
1 1
1 -1
-1 1
-1 -1

    出力例 1

    3.414213562373
    図：出力例１を図示したもの
    • 座標 (0, 0) に兵器工場を建設すると、評価関数の値が最大となり、その値は 3.414213562373 になります。

    入力例 2

    7 5 3
-2 2 1
5 5 3
5 4 1
-2 2 -1
0 3 -4
-3 -1 -1
2 0 2
-2 4
-3 -3
4 3
4 -5
2 5

    出力例 2

    23.575923118987
    • 座標 (1.35714285714286, -1) に兵器工場を建設すると、評価関数の値が最大となり、その値は 23.575923118987 になります。