A - A

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

問題文

高橋君はとても英語が苦手で、アルファベットもまだ覚えきれていません。

そこで、高橋君のために、入力として与えられたアルファベットが A から数えて何番目のアルファベットかを求めるプログラムを作成してください。

ただし、高橋君は 5 より大きい数を知らないので、与えられるアルファベットは A, B, C, D, E のいずれかです。また、A 自身は A から数えて 1 番目であるとします（0 番目ではありません）。

入力

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

X
  • 1 行目には、英大文字のアルファベット X が与えられる。X は　A, B, C, D, E のいずれかである。

出力

X が A から数えて何番目のアルファベットであるかを 1 行に出力せよ。

出力の末尾には改行をいれること。

入力例1

A

出力例1

1

A は最初のアルファベットなので 1 を出力します。

入力例2

B

出力例2

2

入力例3

C

出力例3

3

入力例4

D

出力例4

4
B - 錠

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

問題文

セキュリティ意識の高い高橋君はこの度、自分の家に新しい錠をつけることにしました。

この錠はダイヤルロック式で、1 桁の数字が表示されるディスプレイと、赤色と青色の 2 種類のボタンがついています。赤いボタンを押すとディスプレイに表示されている数が 1 増え、青いボタンを押すと 1 減ります。

ただし、ディスプレイの表示が 9 のときに赤いボタンを押すと 0 になり、ディスプレイの表示が 0 のときに青いボタンを押すと 9 になります。

いま、ディスプレイに表示されている数字は a で、この数字が b になった瞬間に錠が開きます。さて、錠を開けるためには最低何回はボタンを押す必要があるでしょうか？

入力

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

a
b
  • 1 行目には、現在ディスプレイに表示されている数字を表す整数 a (0\,≦\,a\,≦\,9) が与えられる。
  • 2 行目には、解錠するために表示させる必要のある数字を表す整数 b (0\,≦\,b\,≦\,9) が与えられる。
    • a と b が同じ値になることはない。

出力

錠を開けるために必要な、ボタンを押す回数の最小値を 1 行に出力せよ。

出力の末尾には改行をいれること。

入力例1

4
6

出力例1

2

この例では、次のようにボタンを 2 回押すことで解錠することができます。

  • 赤いボタンを押し、数字を 4 から 5 にする。
  • 赤いボタンを押し、数字を 5 から 6 にする。

入力例2

6
4

出力例2

2

この場合は青いボタンを 2 回押すことで解錠することができます。

入力例3

8
1

出力例3

3

青いボタンを 7 回押すことでも解錠できますが、次のように 3 回ボタンを押すことでも解錠することができます。

  • 赤いボタンを押し、数字を 8 から 9 にする。
  • 赤いボタンを押し、数字を 9 から 0 にする。
  • 赤いボタンを押し、数字を 0 から 1 にする。
C - 節制

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

問題文

セキュリティ意識が高く、最新鋭の錠を購入した高橋君ですが、財布の管理は甘かったらしくお金がピンチな状況です。

高橋君の収入は安定せず、次の収入があるのは今から N 日後です。高橋君は N 日間、できるだけ食費を抑えて節約生活を送ることにしました。

はじめ、高橋君の満腹度は H です。N 日間のそれぞれの日について、その日にとる食事を次の 3 種類の中から 1 つ選びます。

  • 普通の食事: A 円の出費をして、満腹度が B 増える。
  • 質素な食事: C 円の出費をして、満腹度が D 増える。（ただし、C < A かつ D < B）
  • 食事抜き: 出費なしで、満腹度が E 減る。

厳しく節約すれば出費を抑えることができますが、あまりに節約しすぎて体調を崩してしまってはいけないため、N 日間で一度も満腹度が 0 以下にならないようにしなければなりません。

高橋君は最低何円の食費で N 日間を乗り切ることができるでしょうか？

ただし、高橋君は超人級の胃袋を持っており、その満腹度には上限がないとする。すなわち、いくら食事をしても高橋君の満腹度が頭打ちになることはない。

入力

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

N H
A B C D E
  • 1 行目には、節約生活の日数を表す整数 N (1\,≦\,N\,≦\,5 \times 10^5) と、節約生活を始める前の高橋君の満腹度を表す整数 H (1\,≦\,H\,≦\,10^9) が空白区切りで与えられる。
  • 2 行目には、3 種類の食事に関する情報を表す整数 A, B, C, D, E がこの順に空白区切りで与えられる。
    • 出費について、1\,≦\,C < A\,≦\,10^6 が成り立つ。
    • 満腹度の増減について、1\,≦\,D < B\,≦\,10^6 および 1\,≦\,E\,≦\,10^6 が成り立つ。

部分点

この問題には部分点が設定されている。

  • N\,≦\,10 を満たすテストケース全てに正解すると、部分点として 10 点が与えられる。
  • N\,≦\,50, H\,≦\,50, B\,≦\,50, D\,≦\,50 を満たすテストケースすべてに正解すると、部分点として 30 点が与えられる。（N\,≦\,10 を満たすテストケース全てにも正解していた場合は合計で 40 点となる）
  • N\,≦\,1,000 を満たすテストケース全てに正解すると、100 点が与えられる。
  • 全てのテストケースに正解すると、ボーナス点として追加で 1 点が与えられる。

ボーナス点に対応するテストケースに関しては、答えが 32 ビットの整数型に収まらない可能性があることに注意せよ。

出力

高橋君が満腹度を一度も 0 以下にせずに N 日間の節約生活を乗り切るために必要な食費の最小値が何円かを 1 行に出力せよ。

出力の末尾には改行をいれること。

入力例1

4 5
100 4 60 1 4

出力例1

160

たとえば、4 日間の食事を以下のようにすれば 160 円の出費で済ませることができます。

  • 節約生活を始める前、高橋君の満腹度は 5 である。
  • 1 日目には質素な食事をとる。60 円を出費して、満腹度が 1 増えて 6 になる。
  • 2 日目は食事を抜く。出費はなく、満腹度は 4 減って 2 になる。
  • 3 日目には普通の食事をとる。100 円を出費して、満腹度が 4 増えて 6 になる。
  • 4 日目は食事を抜く。出費はなく、満腹度は 4 減って 2 になる。

入力例2

10 1
5000 2 2000 1 300

出力例2

20000

この例では、高橋君は 1 日食事を抜くと満腹度が 300 も減ってしまうので、毎日食事をとる必要があります。

質素な食事を 10 日間とり続けることで 2,000 \times 10 = 20,000 円の出費となり、これが最小の出費になります。

入力例3

9 23
170 8 120 5 12

出力例3

650

入力例4

653 314159
6728 123456 5141 41928 222222

出力例4

2818162

この例は N\,≦\,10 という 10 点の部分点の制約および N\,≦\,50, H\,≦\,50, B\,≦\,50, D\,≦\,50 という 30 点の部分点の制約を満たしていないことに注意せよ。

D - 阿弥陀

実行時間制限: 4 sec / メモリ制限: 256 MB

問題文

古くより伝わる日本の伝統的なくじ引き、あみだくじをご存知だろうか？

あみだくじを行うときは、まず N 本の平行な縦線を引く。次に、M 本の横線をその中に引いていく。それぞれの横線は隣り合う 2 本の縦線を結ぶように引かなければならず、2 本以上の横線がまったく同じ高さにあってはいけない。ここでは、上から i (1\,≦\,i\,≦\,M) 番目にある横線が、左から A_i (1\,≦\,A_i < N) 番目の縦線と A_i + 1 番目の縦線を結んでいるとしよう。

N = 5, M = 7, A = \{1,4,3,4,2,3,1\} の場合のあみだくじを以下に示す。くじを引くときは、縦線を 1 本選び、その上端から線を下っていく。途中で横線に遭遇したときには必ず曲がらなければならず、また縦線を上向きに辿ってはいけない。たとえばこのあみだくじで左から 4 番目の縦線から始めてくじを引くと、左から 3 番目の縦線に辿り着く。

さて、ここまでは普通のあみだくじであるが、何かにつけビッグデータという言葉が騒がれる昨今である。あみだくじがこれから先生きのこるためには、あみだくじもビッグになってビッグデータに対抗していかなければならない。

そこで、あみだくじを縦に D 個つなげることで巨大なあみだくじを作ることを考えよう。たとえば、先ほど例に挙げたあみだくじを 2 個つなげてみると以下のようになる。この場合、左から 4 番目の縦線から始めてくじを引くと、辿り着く場所は左から 5 番目の縦線になる。

こうして作った巨大あみだくじだが、あみだくじ本来の目的を果たせなければビッグになった意味もない。つまり、この巨大なあみだくじを使ってくじを引いた結果がどうなるかを効率よく計算できなければ、せっかく作った巨大あみだくじもただの落書きである。

そこで、1\,≦\,k\,≦\,N を満たすすべての整数 k に対し、巨大あみだくじの左から k 番目の縦線を選んで線を辿っていったとき、最終的に下端で左から何番目の縦線に行き着くかを計算するプログラムを書いて欲しい。

入力

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

N M D
A_1 A_2 ... A_M
  • 1 行目には、元のあみだくじの縦線の本数を表す整数 N (2\,≦\,N\,≦\,10^5)、横線の本数を表す整数 M (0\,≦\,M\,≦\,2 \times 10^5)、元のあみだくじを縦につなげる回数を表す整数 D (1\,≦\,D\,≦\,10^9) が空白区切りで与えられる。
  • 2 行目には、元のあみだくじにおける横線の情報を表す M 個の整数 A_i (1\,≦\,i\,≦\,M) が空白区切りで与えられる。

部分点

この問題のテストケースは 4 つのグループに分けられており、それぞれに配点が決まっている。

  • 1 つめのグループにおいて、テストケースは D = 1 を満たす。このグループのテストケース全てに正解すると 10 点が与えられる。
  • 2 つめのグループにおいて、テストケースは N\,≦\,1,000 および D\,≦\,1,000 を満たす。このグループのテストケース全てに正解すると 20 点が与えられる。
  • 3 つめのグループにおいて、テストケースは N\,≦\,8 を満たす。このグループのテストケース全てに正解すると 20 点が与えられる。
  • 4 つめのグループにおいてはテストケースに追加の制限はない。このグループのテストケース全てに正解すると 50 点が与えられる。

出力

N 行出力せよ。このうち k 行目には、巨大あみだくじの左から k 番目の縦線を選んで線を辿っていったとき、下端で左から何番目の縦線に到達するかを表す整数を出力せよ。

出力の末尾にも改行をいれること。

入力例1

5 7 1
1 4 3 4 2 3 1

出力例1

4
2
5
3
1

この入出力例は問題文中の最初の図で示されたあみだくじに対応している。

入力例2

5 7 2
1 4 3 4 2 3 1

出力例2

3
2
1
5
4

この入出力例は問題文中の 2 番目の図で示されたあみだくじに対応している。このケースは 1 つめのテストグループの制約を満たさないことに注意せよ。

入力例3

10 20 300
9 1 2 5 8 1 9 3 5 6 4 5 4 6 8 3 2 7 9 6

出力例3

3
7
2
4
5
9
6
1
8
10

このケースは 1 つめおよび 3 つめのテストグループの制約を満たさないことに注意せよ。