AtCoder Regular Contest 008

A - たこ焼き買えるかな？

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

ある日、あなたはたこ焼きを買いに行きました。
そのお店ではたこ焼き 1 個 15 円、 10 個まとめて 100 円で売っています。
今、あなたは N 個のたこ焼きを買おうと思っています。あなたはたこ焼きを N 個以上買うのに少なくともいくら必要でしょうか。

入力

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

入力は 1 行ある。
1 行目には、購入したいたこ焼きの個数を表す整数 N(1≦N≦50) が与えられる。

出力

たこ焼きを N 個以上買うのに必要な最小金額を標準出力に 1 行で出力すること。
なお、最後には改行を出力せよ。

入力例 1

出力例 1

1 つ 15 円のたこ焼きを 2 つ購入します。

入力例 2

出力例 2

1 つ 15 円のたこ焼きを 5 つ購入します。

入力例 3

出力例 3

10 個 100 円のたこ焼き 1 パック購入する方が、たこ焼き 7 個を 15×7=105 円で買うよりも安いです。

Source Name

ARC 008

B - 謎のたこ焼きおじさん

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

あなたはたこ焼きを買いに来たところ、伝説のたこ焼きマスター高橋社長に認められ、新しく作るたこ焼き屋さんの店長を任されました。
店長に任命されたあなたに与えられた最初の仕事は、お店の看板を作成することでした。
ところが高橋社長は~~使えない~~時間がないので、たこ焼き屋さんの名前は決めましたが、看板を作るのはあなたに任せて去って行きました。
その際に看板を作るための英字ブロックが入ったいくつかのキットを渡されました。
英字キットとは、ランダムな英字ブロックが含まれている袋のことです。
例えば英字キットを表す文字列が ABCC であるような英字キットの場合、

英字ブロックAが1つ含まれている。
英字ブロックBが1つ含まれている。
英字ブロックCが2つ含まれている。

とみなすことができます。
つまり、英字キット ABCC 1 袋につき、英字ブロックAと英字ブロックBを1つずつ、英字ブロックCを2つを看板に用いることができます。
高橋社長から渡された英字キットは全て同じ英字キットだったので、どのキットを開けても中身は全く同じです。
あなたは看板にお金をかけるわけにもいかないので、開封する英字キットを最小にして残りは返品したいです。
どれだけの英字キットを使うことで、お店の看板を作ることができるでしょうか。

入力

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

N M
name
kit

入力は 3 行ある。
1 行目にお店の名前の文字数 N\ (1≦N≦50) と、英字キット 1 袋に入ってる英字ブロックの数 M\ (1≦M≦50) が空白区切りで与えられる。
2 行目にはお店の名前を表す文字列 name が N 文字で与えられる。
- 文字列 name に含まれる文字は A-Z のみである。
3 行目には英字キットに含まれている英字ブロックを表す文字列 kit が M 文字で与えられる。
- 文字列 kit に含まれる文字は A-Z のみである。

出力

看板をつくるために必要な英字キットの最小数を標準出力に 1 行で出力すること。
与えられた英字キットで看板を作成することができない場合は、-1を出力すること。
また、出力の最後には改行をいれること。

入力例 1

7 26
NAOHIRO
ABCDEFGHIJKLMNOPQRSTUVWXYZ

出力例 1

英字キット ABCDEFGHIJKLMNOPQRSTUVWXYZ には英字ブロックOが 1 つしかないため、お店の名前 NAOHIRO を作成するためには英字キットを 2 袋用いる必要があります。

入力例 2

8 8
TAKOYAKI
TAKOYAKI

出力例 2

英字キット TAKOYAKI を 1 袋用いると、お店の名前 TAKOYAKI を作成することができます。

入力例 3

8 4
CHOKUDAI
MYON

出力例 3

-1

英字キット MYON では英字ブロックCHKUDAIが足りないため、お店の名前 CHOKUDAI を作成することができません。
よって、-1を出力します。

入力例 4

6 6
MONAKA
NAMAKO

出力例 4

英字キット NAMAKO に含まれる英字ブロックNAMAKOを入れ替えると、お店の名前 MONAKA を作成することができます。

Source Name

ARC 008

C - THE☆たこ焼き祭り2012

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

たこ焼き屋の開店にあたって、たこ焼きの味を皆に分かってもらうために試食イベントを行うことにしました。
しかし、高橋社長はたこ焼きをより多くの人に食べてもらいたいので、試食イベントを兼ねたお祭り『THE☆たこ焼き祭り2012』をすることを提案してきました。高橋社長が提案してきた『THE☆たこ焼き祭り2012』の試食イベント内容は以下のようになっています。

会場にはあなたと参加者を足して N 人の人がいます。あなたはたこ焼きを N 個持っており、それを全員に 1 人 1 個ずつ行き渡るようにします。
会場は広いのであなたはたこ焼きを投げて配らないといけません。あなただけで全員に配ることは大変なので、参加者にも協力してもらうことにし、参加者は受け取ったたこ焼きを別の参加者へと投げることもできます。
あなたと参加者はつまようじを1 人につき 1 本しか持っていないので同じタイミングで複数のたこ焼きを投げることはできず、たこ焼きを投げてから 1 秒間は次のたこ焼きを投げることができません。受け取る側はいつでも何個でも受け取ることができます。
さらに、あなたと参加者は立っている位置から動いてはいけません。
参加者は大人から子供までいるのでそれぞれにはたこ焼きをキャッチできる速度の上限があり、たこ焼きを投げる側にも投げられる速度の上限があります。投げられたたこ焼きの速度は減衰することなく受け取り手に届きます。

たこ焼きはなるべく出来立てを食べて欲しいので、たこ焼きを全員に配り切るために必要な時間の最小値を答えなさい。

入力

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

N
x_{0} y_{0} t_{0} r_{0}
x_{1} y_{1} t_{1} r_{1}
:
:
x_{N-1} y_{N-1} t_{N-1} r_{N-1}

入力は N+1 行ある。
1 行目には、たこ焼き祭りの参加者数とあなたを足した数を表す整数 N\ (1≦N≦1,000) が与えられる。
2 行目には、あなたが立っている位置の x 座標を表す整数 x_0\ (-10,000≦x_0≦10,000)、y 座標を表す整数 y_0\ (-10,000≦y_0≦10,000)、たこ焼きを投げる速度の上限を表す整数 t_0\ (3≦t_0≦340) とたこ焼きを受け取る速度の上限を表す整数 r_0\ (3≦r_0≦340) が空白で区切られて与えられる。
3 行目から N-1 行のうち i+2\ (1≦i≦N-1) 行目には i 番目の参加者が立っている位置の x 座標を表す整数 x_i\ (-10,000≦x_i≦10,000)、y 座標を表す整数 y_i\ (-10,000≦y_i≦10,000)、たこ焼きを投げる速度の上限を表す整数 t_i\ (3≦t_i≦340) とたこ焼きを受け取る速度の上限を表す整数 r_i\ (3≦r_i≦340) が空白で区切られて与えられる。
与えられる速度は 1 秒辺りの速度である。
複数の人が同じ位置に立つことはない。

出力

たこ焼きを全ての参加者が 1 つずつ受け取るためまでに必要な秒数の最小値を 1 行で出力せよ。
出力は整数および小数のみとし、誤差は絶対誤差あるいは相対誤差の少なくとも片方が 10^{−6} 以下であれば許容する。
なお、最後には改行を出力せよ。

入力例 1

4
0 0 300 10
0 100 10 100
0 200 10 200
0 300 10 300

出力例 1

0 秒目 :
- あなた : 1 番目の参加者に速度 100 でたこ焼きを投げる。
1 秒目 :
- あなた : 2 番目の参加者に速度 200 でたこ焼きを投げる。
- 1 番目の参加者 : あなたが 0 秒目に投げたたこ焼きをキャッチする。
2 秒目 :
- あなた : 3 番目の参加者に速度 300 でたこ焼きを投げる。
- 2 番目の参加者 : あなたが 1 秒目に投げたたこ焼きをキャッチする。
3 秒目 :
- 3 番目の参加者 : あなたが 2 秒目に投げたたこ焼きをキャッチする。

入力例 2

4
0 0 100 10
0 90 10 10
0 100 30 100
-20 100 10 10

出力例 2

0 秒目 :
- あなた : 2 番目の参加者に速度 100 でたこ焼きを投げる。
1 秒目 :
- あなた : 2 番目の参加者に速度 100 でたこ焼きを投げる。
- 2 番目の参加者 : あなたが 0 秒目に投げたたこ焼きをキャッチし、3 番目の参加者に速度 10 で投げる。
2 秒目 :
- あなた : 2 番目の参加者に速度 100 でたこ焼きを投げる。
- 2 番目の参加者 : あなたが 1 秒目に投げたたこ焼きをキャッチし、2 番目の参加者に速度 10 で投げる。
3 秒目 :
- 1 番目の参加者 : 2 番目の参加者が 2 秒目に投げたたこ焼きをキャッチする。
- 2 番目の参加者 : あなたが 2 秒目に投げたたこ焼きをキャッチする。
- 3 番目の参加者 : 2 番目の参加者が 1 秒目に投げたたこ焼きをキャッチする。

入力例 3

1
0 0 3 3

出力例 3

参加者があなただけなので配る必要がありません。

入力例 4

4
58 -49 38 109
45 -29 200 56
-32 123 103 98
49 -234 289 43

出力例 4

4.874179

入力例 5

8
100 100 30 50
100 50 93 123
100 0 89 111
50 100 13 18
50 0 155 86
0 100 30 58
0 50 58 49
0 0 98 153

出力例 5

7.666667

Source Name

ARC 008

D - タコヤキオイシクナール

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたのたこ焼き屋さんは試食イベントのおかげもあり、とても繁盛しました。
喜んだ高橋社長は全国展開するために、工場で冷凍たこ焼きの生産をすることを決めました。
高橋社長がたこ焼き生産のために買ってきた機械の 1 つにタコヤキオイシクナールという機械があります。
このタコヤキオイシクナールはトンネルの形をした N 個のボックスからできています。
それぞれのボックスはベルトコンベアで一直線に接続されており、i(1≦i≦N-1) 番目のボックスの出口が i+1 番目のボックスの入り口に繋がっています。
ボックスにはそれぞれ 2 つの実数 (a,b) が書かれており、美味しさ r のたこ焼きを入れると不思議なことに美味しさが a×r+b に変化します。

図 1 はタコヤキオイシクナールにたこ焼きを入れた図です。
(2,1) と書かれたボックスを美味しさ 1 のたこ焼きが通過すると美味しさは 2×1+1=3 に変化し、さらに次の (-1,2) と書かれたボックスを通過すると 3 から -1 へと美味しさが変化します。

図：美味しさ 1 のたこ焼きを 1 個、タコヤキオイシクナールに載せた場合の美味しさの変化

最初ボックスに書かれている数字は全て (1,0) になっておりたこ焼きは N 個のボックスを通過しても美味しさが変化しない状態でした。
そこで、あなたは美味しさ 1 のたこ焼きを 1 個ずつタコヤキオイシクナールに入れてみることにしました。
しかし、ボックスの数字を M 回いたずら好きの高橋社長が変更してしまいました。
美味しさが保障できないと出荷ができません。出来上がったたこ焼きの美味しさの最小値と最大値を求めなさい。

なお、タコヤキオイシクナールは同時に 1 個分のたこ焼きしか加工することができず、タコヤキオイシクナールが加工を行なっている間に高橋社長が任意のボックスの数字を変更することはありません。
つまり、高橋社長がボックスの数字を変更することができるのは、たこ焼きが出来上がってから次のたこ焼きをあなたがタコヤキオイシクナールのベルトコンベアに乗せるまでの間です。
また、その間に高橋社長が複数のボックスの数字を変更することはないものとする。

入力

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

N M
p_0 a_0 b_0
p_1 a_1 b_1
:
:
p_{M-1} a_{M-1} b_{M-1}

入力は M+1 行ある。
1 行目には、一直線上に接続するボックスの個数を表す整数 N と高橋社長がボックスの数字を変更した回数を表す整数 M が空白区切りで与えられる。
2 行目からの M 行には高橋社長が変更したボックスの内容が与えられる。

i+2\ (0≦i≦M-1) 行目には高橋社長が i+1 番目に変更したボックスの番号を表す整数 p_i\ (1≦p_i≦N)、そのボックスの変更後の a の値を表す実数 a_i\ (-1≦a_i≦1)、b の値を表す実数 b_i\ (-1≦b_i≦1) が空白区切りで与えられる。
- ボックスの番号はたこ焼きが流れる順に 1 から N まで順に振られている。
- a_i と b_i は小数点以下第 5 位までで与えられる。

部分点

テストデータには以下の 2 種類のテストデータセットのいずれかに含まれており、それぞれのデータセットに含まれているテストデータは以下に示すように与えられる整数 N と M の範囲が異なっている。
あるテストデータセットに含まれているテストデータ全てに対して正しい解を出力できると、それ以外のテストデータセットで不正解を出力しても以下のように部分点が与えられる。

small ( 50 点) : 1≦N≦1,000,\ 0≦M≦1,000
large ( 50 点) : 1≦N≦10^{12},\ 0≦M≦100,000

出力

1 行目に出来上がったたこ焼きの中での美味しさの最小値を、 2 行目に最大値を標準出力に出力せよ。
出力は整数および小数のみとし、誤差は絶対誤差あるいは相対誤差の少なくとも片方が 10^{−6} 以下であれば許容する。
なお、最後には改行を出力せよ。

入力例 1

1 1
1 1 0

出力例 1

1
1

高橋社長が数字を変更してしまいますが、変更後の数字が元の数字と同じなので美味しさは変化しません。
したがって、出来上がるたこ焼きの美味しさは全て 1 になります。

入力例 2

3 2
2 -1 1
2 1 0.5

出力例 2

0
1.5

1 回目のボックスの数字変更後のたこ焼きの美味しさは (-1)×1+1=0 となります。
2 回目のボックスの数字変更後のたこ焼きの美味しさは 1×1+0.5=1.5 となります。

入力例 3

4 5
1 -0.8 0.5
2 0.72 -0.21
3 1 0.8
4 0.3 0.4142
3 1 0.8

出力例 3

-0.426
1

2 回目のボックスの数字変更後のたこ焼きの美味しさは-0.426、4 回目のボックスの数字変更後のたこ焼きの美味しさは0.5264 になります。
しかし、1 回目のボックスの数字を変更前はたこ焼きの美味しさは 1 だったので、美味しさの最大値は 1 になります。

入力例 4

10 10
6 0.5674 -1
3 -0.432 0.1235
8 0.92 0
4 -0.673 0.12578
6 0.986 -0.567
1 0.11111 1
10 0.98765 -0.1234
10 0.18543 -0.16532
9 -0.756 0.54849
2 -1 0.74436

出力例 4

-1.175043
1

Source Name

ARC 008