A - 動物園

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
B - 自動ドア

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
C - 民族大移動

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
D - 動的計画法

Time Limit: 2 sec / Memory Limit: 256 MB

(21:52)ジャッジに使われているサンプルテストケースのうち1つのテストケースが問題文のものと異なることが判明致しました。ご不便をおかけして申し訳ありません。なお、テストケース自体は正しいものであるため、リジャッジ等は行いません。ご了承ください。

問題文

高橋君はタテ、ヨコともに 10^8 マスずつある方眼紙を使って以下の問題を解くことにしました。

「一番左下のマスから開始して、右もしくは上に1マス移動するという操作を繰り返して、各マスにたどり着く方法の個数を 1,000,000,007 で割った余りを求めよ。」

高橋君は動的計画法が好きなので、この問題が動的計画法を使って解けるということにすぐ気づきました。

具体的には

  1. 最も左の列もしくは最も下の行に属する全てのマスに 1 を書き込む。
  2. まだ整数が書き込まれていないマスについて、左のマスにも下のマスにも整数が書かれていたら、その 2 マスの和を1,000,000,007 で割った余りをそのマスに書き込む。
  3. 整数が書かれていないマスがなくなるまで操作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