Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ABC動物園は、高橋王国で一番の人気を誇る動物園です。
ABC動物園の入場料の設定は以下のようになっています。
- 子供 1 人あたり A 円
- 大人 1 人あたり B 円
- 合計人数が K 人以上の団体は 1 人あたり C 円引き
今、子供 S 人、大人 T 人からなる団体が入場しようとしています。 この団体が合計で支払わなければならない入場料を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
A B C K S T
-
1 行目には入場料の値段設定を表す 4 つの整数 A, B, C, K が空白区切りで与えられる。各変数の意味は問題文と同様である。各変数は以下の制約を満たす。
- 0 ≦ C ≦ A ≦ B ≦ 1,000
- 0 ≦ K ≦ 100
- 2 行目には団体が含む子供と大人の人数を表す 2 つの整数 S(0 ≦ S ≦ 100), T(0 ≦ T ≦ 100) が空白区切りで与えられる。
出力
団体が合計で支払わなければならない入場料を 1 行に出力せよ。 出力の末尾に改行を入れること。
入力例1
100 200 50 20 40 10
出力例1
3500
子供 40 人、大人 10 人の団体です。合計人数が 20 人以上なので一人あたり 50 円割引、つまり全体で 2500 円割引されます。
入力例2
400 1000 400 21 10 10
出力例2
14000
団体の合計人数が 21 人以上ではないので割引は適応されません。
入力例3
400 1000 400 20 10 10
出力例3
6000
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ABCマーケットは高橋王国で最も人気なスーパーマーケットです。 入り口は自動ドアになっています。
この自動ドアは人が前を通りかかると自動で開き、そこから T 秒後まで開き続け、その後自動的に閉じます。 ドアが開いている状態で新たに人が前を通りかかると、通りかかった時刻のさらに T 秒後まで開き続ける時間が延長されます。
今日はのべ N 人の客が自動ドアの前を通りかかりました。 i 番目の人が通りかかった時刻はABCマーケットが開店してから A_i 秒経った時刻です。
今日、この自動ドアが開いていた合計秒数を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
N T A_1 A_2 : A_N
- 1 行目に今日自動ドアの前を通りかかった人数を表す整数 N(1 ≦ N ≦ 10^5) とドアが開き続ける時間を表す整数 T(1 ≦ T ≦ 10^5) が空白区切りで与えられる。
- 2 行目からの N 行のうち i 行目には i 番目の客が自動ドアの前を通りかかった時刻 A_i(1 ≦ A_i ≦ 10^6) が与えられる。
- A_1 ≦ A_2 ≦ … ≦ A_N が成り立つ。
部分点
この問題には部分点が設定されている。
- 1 ≦ T ≦ 100を満たすデータセットに正解した場合は 50 点が与えられる。
- 1 ≦ T ≦ 10^5を満たすデータセットに正解した場合はさらに 50 点が与えられる。合計で100点となる。
出力
ドアが開いていた秒数を 1 行に出力せよ。 出力の末尾に改行を入れること。
入力例1
5 10 20 100 105 217 314
出力例1
45
時刻が 20 ~ 30、100 ~ 115、217 ~ 227、314 ~ 324 のときにドアが開いています。
入力例2
10 10 1 2 3 4 5 6 7 8 9 10
出力例2
19
入力例3
10 100000 3 31 314 3141 31415 314159 400000 410000 500000 777777
出力例3
517253
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋王国には N 個の街があり、それぞれ 1 ~ N の整数によって番号付けされています。
高橋王国には K 種類の民族が住んでおり、i 番目の民族は街 S_i に住んでいます。
高橋王国の民族たちには、百年に一回住む街を変える「民族大移動」という文化が有ります。 基本的には全民族が同時期に「民族大移動」を行うのですが、全く同じ日に全民族が移動すると混雑が予想されるため、 以下の様な移動制限を毎日設けて、 D 日かけて行います。
- i 日目は 街の番号が L_i 以上 R_i 以下であるよう街の間を自由に行き来できる。それ以外の行き来は禁止される。
各民族はこの移動制限を守り、いくつかの街を経由しながら目的地の街まで移動します。
i 番目の民族の目的地は街 T_i です。どの民族もできるだけ早く目的地に到着したいと思っています。
各民族について、目的地に到着できる最も早い日を求めてください。
なお、どの民族も D 日以内に目的地に到着できることが保証されています。
入力
入力は以下の形式で標準入力から与えられる。
N D K L_1 R_1 L_2 R_2 : L_D R_D S_1 T_1 S_2 T_2 : S_K T_K
- 1 行目には高橋王国の街の個数 N(1 ≦ N ≦ 10^9) 、大移動にかける日数 D(1 ≦ D ≦ 10^4) 、高橋王国に住む民族の個数 K(1 ≦ K ≦ 100) が空白区切りで与えられる。
- 2 行目からの D 行のうち i 行目には i 日目の移動制限の内容を表す 2 つの整数 L_i, R_i(1 ≦ L_i ≦ R_i ≦ N) が空白区切りで与えられる。
- D+2 行目からの K 行のうち i 行目には i 番目の民族の初め住んでいる街 S_i( 1 ≦ S_i ≦ N)、目的地の街 T_i (1 ≦ T_i ≦ N) が空白区切りで与えられる。このとき S_i ≠ T_i が成り立つ。
- どの民族も D 日以内に目的地に到着できることが保証されている。
出力
出力は K 行からなる。 i 行目には i 番目の民族が目的地に到着できる最初の日を出力せよ。 出力の末尾にも改行を入れること。
入力例1
10 10 3 1 5 3 6 7 10 5 8 4 4 1 4 2 9 1 3 1 1 4 5 1 6 2 7 10 1
出力例1
2 4 8
1 番目の民族は以下のように移動すれば 2 日で目的地に到着できます。これより早く移動することはできません。
- 1 日目に街 1 から街 4 に移動する。
- 2 日目に街 4 から街 6 に移動する。
2 番目の民族は以下のように移動すれば 4 日で目的地に到着できます。これより早く移動することはできません。
- 1 日目に街 2 から街 5 に移動する。
- 4 日目に街 5 から街 7 に移動する。
3 番目の民族は以下のように移動すれば 8 日で目的地に到着できます。これより早く移動することはできません。
- 3 日目に街 10 から街 9 に移動する。
- 7 日目に街 9 から街 3 に移動する。
- 8 日目に街 3 から街 1 に移動する。
入力例2
10 10 4 1 2 2 4 3 6 4 8 5 10 9 10 7 8 5 6 3 5 1 3 10 1 3 8 2 4 1 3
出力例2
10 4 2 2
入力例3
314159265 10 1 1 10000 500 12031 1414 113232 111111 777777 666661 23423423 12345678 123456789 111111111 314159265 112334 235235235 1 223445 314 1592 1 314159265
出力例3
7
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君はタテ、ヨコともに 10^8 マスずつある方眼紙を使って以下の問題を解くことにしました。
「一番左下のマスから開始して、右もしくは上に1マス移動するという操作を繰り返して、各マスにたどり着く方法の個数を 1,000,000,007 で割った余りを求めよ。」
高橋君は動的計画法が好きなので、この問題が動的計画法を使って解けるということにすぐ気づきました。
具体的には
- 最も左の列もしくは最も下の行に属する全てのマスに 1 を書き込む。
- まだ整数が書き込まれていないマスについて、左のマスにも下のマスにも整数が書かれていたら、その 2 マスの和を1,000,000,007 で割った余りをそのマスに書き込む。
- 整数が書かれていないマスがなくなるまで操作2を繰り返す。
というアルゴリズムによって、答えを求めることが出来ます。
高橋君は上記のアルゴリズムですべてのマスに「左下からたどり着く方法の個数を 1,000,000,007 で割った余り」を書き込みました。
できあがった方眼紙の左下の一部は下図のようになります。
しかし書き込み終わったあと、達成感のために舞い上がってしまい、方眼紙の一部を破いてしまいました。
高橋君の手元には、あるマスと、その上のマスと右のマスの部分のみが書かれている方眼紙の欠片があります。
高橋君はこの欠片を元の位置に戻そうと思ったのですが、方眼紙が大きすぎるので、どこに置けばいいのかわかりません。
欠片の情報から、この欠片が元々の方眼紙の左から何マス、下から何マスの位置にあったのか求めてください。
つまり、左からxマス、下からyマスのマスのことを (x, y) と書くとして、(r, c)、(r, c + 1)、(r + 1, c)のマスに書かれている整数が与えられるので、 r と c を求めてください。
なお、一番左下のマスは (0, 0) です。
入力
入力は以下の形式で標準入力から与えられる。
A B C
- 1 行目には (r, c) のマスに書かれている整数 A(0 ≦ A < 1,000,000,007) が与えられる。
- 2 行目には (r, c + 1) のマスに書かれている整数 B(0 ≦ B < 1,000,000,007) が与えられる。
- 3 行目には (r + 1, c) のマスに書かれている整数 C(0 ≦ C < 1,000,000,007) が与えられる。
- 0 ≦ r, c < 99,999,999となるような答えが存在するような A, B, C が与えられる。
出力
欠片が元々あった位置を表す 2 つの整数 r(0 ≦ r < 99,999,999) と c(0 ≦ c < 99,999,999) を空白区切りで出力せよ。 答えとして考えられる r, c が複数あった場合はそのなかで r が最小のものを出力せよ。 それでも答えが 1 つに定まらない場合は、rが最小のもののなかで c が最小のものを出力せよ。 出力の末尾には改行を入れること。
入力例1
15 35 21
出力例1
4 2
高橋君の手元にある欠片は下図のようなものです。
元はあった位置としては下図の位置があてはまります。
入力例2
126 252 210
出力例2
5 4
入力例3
144949225 545897619 393065978
出力例3
314159 365358