A - 門限

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

今日は憧れの先輩と一緒にお買い物！お買い物の後、お茶して、他にもいろんな思い出を作って…。

気がついたらもうこんな時間！18 時の門限までに家に帰らないとパパに怒られちゃう＞＜。

というわけで、友人であるあなたは、現在の時間から門限まであと何分あるかを計算することになった。

入力

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

h m
  • 1 行目には、現在時刻を表す 2 個の整数 h (0 ≦ h ≦ 17), m (0 ≦ m ≦ 59) がこの順に空白区切りで書かれている。これらは、現在時刻が 24 時間表記で h 時 m 分ちょうどであることを表す。

出力

門限である 18 時 0 分まで、あと何分あるかを出力せよ。出力の末尾にも改行を入れること。

入力例1

16 23

出力例1

97

現在時刻は 16 時 23 分です。門限まであと 1 時間 37 分あるので、答えとして 60 + 37 = 97 を出力します。

入力例2

17 59

出力例2

1

なんと、あと 1 分しかありません。急げ！

入力例3

13 0

出力例3

300

入力例4

2 7

出力例4

953
B - 大事な数なのでZ回書きまLた。

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

私は 10 進数のある正の整数を覚えておくように言われました。その数字は N 桁で、先頭の数字は 0 ではないです。

大事な数なのでメモ帳に 2 回書きました。

ところで私は文字を書くのが下手です。

後でメモ帳を読み返すと、メモ帳に書いた数字のうちいくつかについて、元はどの数字だったかわからなくなってしまいました。

元の数字がわからない文字は最大 26 文字で、以下では A から Z までの大文字アルファベットで表すことにします。これらの文字は、元は 0 から 9 までの 1 桁の数字のいずれかです。

メモ帳に書いた文字には、同じアルファベットが複数出てくるかもしれません。同じアルファベットが複数回出てきた場合、それらのアルファベットについてはいずれも元は同じ数字となります。1 回目に書いた文字列と 2 回目に書いた文字列に共通して登場するアルファベットが存在する場合もありますが、その場合でも、それらのアルファベットについて元は同じ数字となります。また、異なる種類のアルファベットの元の数字が同じ数字である場合も考えられます。

例えば、メモ帳の 1 回目の文字列が 1XYX であった場合、覚えておくように言われた数字としては 1101 (X = 1, Y = 0) や 1111 (X = 1, Y = 1), 1848 (X = 8, Y = 4) などが考えれますが、一方で例えば 1132 (Y = 3) は X に対する元の数字が 1 と 2 の複数種類存在するので、覚えておくように言われた数字としては考えられません。

メモ帳に書いた 2 つの文字列が与えられるので、覚えておくように言われた数字として全部で何通り考えられるかを求めるプログラムを作成してください。

入力

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

N
s_1
s_2
  • 1 行目には、覚えておくように言われた整数の桁数 N (1 ≦ N ≦ 18) が書かれている。
  • 2 行目には、1 回目にメモ帳に書いた文字列 s_1 が与えられる。s_1 の長さはちょうど N 文字で、半角の大文字アルファベットと数字のみで構成されている。
  • 3 行目には、2 回目にメモ帳に書いた文字列 s_2 が与えられる。s_2 の長さはちょうど N 文字で、半角の大文字アルファベットと数字のみで構成されている。
  • 採点で用いられるすべての入力に関して、覚えておくように言われた整数として考えられる整数は少なくとも 1 つは存在する。つまり、どのようにアルファベットに数字を割り当てたとしても、s_1 と s_2 の最上位桁が 0 になってしまうか、s_1 と s_2 が異なる数字を表してしまう、ということはないものとして良い。

部分点

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

  • N ≦ 6 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
  • 追加制約のないデータセット 2 に正解した場合は、上記とは別に 70 点が与えられる。

出力

覚えておくように言われた整数として考えれられるものの個数を 1 行で出力せよ。出力の末尾にも改行を入れること。

なお、この問題での出力は 32-bit 整数に収まらない場合があることに注意せよ。

入力例1

4
1XYX
1Z48

出力例1

1

覚えているように言われた数としては 1848 (X=8, Y=4, Z=8) しか考えられません。

入力例2

3
XXX
YYY

出力例2

9

先頭に 0 を使用できないことに注意してください。

入力例3

6
PRBLMB
ARC027

出力例3

90
C - 最高のトッピングにしような

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

私の行きつけの飲食店では、食事をすることでチケットを得ることができる。

チケットは、トッピングとの交換に必須なスペシャルチケットと、通常のチケットの 2 種類存在する。

このお店には N 種類のトッピングがあり、トッピング i は、t_i 枚のチケットと交換することによって入手できる。このお店ではチケットを組み合わせて複数種類のトッピングを入手することもできるが、同じトッピングを複数回入手することはできない。

交換の際、スペシャルチケットも通常のチケットも区別なく 1 枚として数えられるが、交換で用いるチケットには、各トッピングごとにスペシャルチケットが 1 枚以上含まれなければならない。例えば 4 枚のチケットと交換できるトッピングがあった場合、以下の 4 通りの交換方法が考えられる。

  • スペシャルチケット 1 枚と通常のチケット 3 枚の組み合わせ。
  • スペシャルチケット 2 枚と通常のチケット 2 枚の組み合わせ。
  • スペシャルチケット 3 枚と通常のチケット 1 枚の組み合わせ。
  • スペシャルチケット 4 枚のみからなる組み合わせ。

またトッピングにはそれぞれ嬉しさという正の整数が決められていて、トッピング i を入手した時の嬉しさは h_i である。

今日は特別な日なので、現在持っているチケットをうまく使用して、入手したトッピングの嬉しさの合計値を最大化させたい。チケットとトッピングの情報から、嬉しさの合計値として考えられる最大値を求めるプログラムを作成せよ。

入力

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

X Y
N
t_1 h_1
t_2 h_2
:
t_N h_N
  • 1 行目には、持っているチケットの枚数を表す 2 つの整数 X (1 ≦ X ≦ 300) と Y (0 ≦ Y ≦ 300) が空白区切りで書かれている。これは、最初にスペシャルチケットを X 枚、通常のチケットを Y 枚持っていることを表す。
  • 2 行目には、トッピングの種類数を表す整数 N (1 ≦ N ≦ 300) が与えられる。
  • 3 行目から N 行には、トッピングに関する情報を表す 2 つの整数 t_i (1 ≦ t_i ≦ 600), h_i (1 ≦ h_i ≦ 5,000,000) が空白区切りで与えられる。これは、トッピング i がチケット t_i 枚と交換することで入手でき、入手したことで得られる嬉しさが h_i であることを表す。

部分点

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

  • X ≦ 50, Y ≦ 50, N ≦ 50, t_i ≦ 100 (1 ≦ i ≦ N) を満たすデータセット 1 に正解した場合は、30 点が与えられる。
  • 追加制約のないデータセット 2 に正解した場合は、上記とは別に 70 点が与えられる。

出力

嬉しさの合計値として考えられる最大値を 1 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

3 5
4
3 30
3 40
5 60
7 80

出力例1

100

初期状態ではスペシャルチケットを 3 枚、通常のチケットを 5 枚持っています。例えば以下のような交換を行うと最大値 100 (= 40 + 60) を達成できます。

  • トッピング 2 (チケットが 3 枚必要)をスペシャルチケット 1 枚と通常のチケット 2 枚を用いた交換で入手します。トッピング 2 の嬉しさは 40 です。
  • トッピング 3 (チケットが 5 枚必要)をスペシャルチケット 2 枚と通常のチケット 3 枚を用いた交換で入手します。トッピング 3 の嬉しさは 60 です。

この方法は、スペシャルチケットを 3 (= 1 + 2) 枚、通常のチケットを 5 (= 2 + 3) 枚消費する方法なので実行可能です。

入力例2

3 3
4
3 30
3 40
5 60
7 80

出力例2

70

トッピング 1 とトッピング 2 を入手するのが最適となります。

入力例3

1 5
4
3 30
3 40
5 60
7 80

出力例3

60

トッピング 3 を入手して、チケットを 1 枚余らせるのが最適となります。

入力例4

6 12
4
3 30
3 40
5 60
7 80

出力例4

210

すべてのトッピングを入手できます。

D - ぴょんぴょんトレーニング

Time Limit: 8 sec / Memory Limit: 256 MB

問題文

跡鼓駄 (あとこだ) 町には ARC 珈琲店があり、競技プログラミング喫茶店として知られている。

高橋君は ARC 珈琲店でアルバイトをしている。

高橋君は ARC 珈琲店に行く際にいつも精進通りという道を通る。精進通りは、高橋君の家と ARC 珈琲店とを結んでいる。

精進通りは N 個の石で構成されている石畳の道である。石には、高橋君の家がある側から順に 1 から N まで番号がつけられている。

高橋君は足腰を鍛えるため、D 日間精進通りでトレーニングをすることにした。

i 日目のトレーニングは、以下の要領で行われる。

  • トレーニング中、石 x にいる場合、石 x からは石 x + 1, x + 2, … , x + h_x に跳んで移動することができる。h_x はトレーニングの日によらず一定である。
  • トレーニング開始時点では石 s_i にいる。
  • トレーニングでは、石 s_i からジャンプを繰り返して石 t_i に移動する。途中で石 t_i より大きな番号の石に跳べたとしても、t_i より大きな番号の石に移動してはならない。
  • トレーニングは石 t_i に到達した時点で終了する。

高橋君は、石 s_i から石 t_i までジャンプで移動する組み合わせが全部で何通りあるのかが気になった。ジャンプで移動する組み合わせというのは、ジャンプで移動する際に使用する石の組み合わせの総数である。高橋君はすべての組み合わせについて自力で跳んで確かめるつもりである。

同僚の青木君は、高橋君を止めるために、石 s_i から石 t_i までジャンプで移動する方法が全部で何通りあるのかを前もって調べ、結果を高橋君に伝えることにした。

それぞれの日について、石 s_i から石 t_i までジャンプで移動する方法が全部で何通りあるのかを求めるプログラムを作成せよ。　なお、 2 つの移動方法が異なるとは、途中で通った石の組み合わせが異なることである。

入力

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

N
h_1 h_2 ... h_N
D
s_1 t_1
s_2 t_2
:
s_D t_D
  • 1 行目には、石の個数を表す整数 N (2 ≦ N ≦ 300,000) が書かれている。
  • 2 行目には、N 個の整数が空白区切りで書かれている。これらの整数のうち左から i (1 ≦ i ≦ N) 番目の整数 h_i (1 ≦ h_i ≦ 10) は、石 i からは石 i + 1, i + 2, … , i + h_i に跳べることを表す。この入力では、i + h_i ＞ N となる場合も入っている点に注意せよ。
  • 3 行目には、トレーニングの日数を表す整数 D (1 ≦ D ≦ 5,000) が与えられる。
  • 4 行目から D 行には、トレーニングに関する情報が書かれている。これら D 行のうち上から i (1 ≦ i ≦ D) 行目には 2 つの整数 s_i, t_i (1 ≦ s_i ＜ t_i ≦ N) が空白区切りで与えられる。これは、i 日目のトレーニングでは、石 s_i から開始して、石 t_i で終了することを表す。

部分点

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

  • N ≦ 500 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
  • 追加制約のないデータセット 2 に正解した場合は、上記とは別に 70 点が与えられる。

出力

D 行にわたって出力せよ。D 行のうち i 行目には、i 日目におけるジャンプで移動する組み合わせ数を 1000000007 (= 1,000,000,007) で割った余りを出力せよ。出力の末尾にも改行を入れること。

入力例1

7
1 2 3 2 2 1 1
3
2 6
5 7
1 7

出力例1

6
2
9

1 日目のトレーニングでは、石 2 から石 6 に移動します。この入力では、(h_2, h_3, h_4, h_5, h_6) =(2, 3, 2, 2, 1) です。ジャンプによる移動としては、以下の 6 通りが考えられます。

入力例2

11
3 1 4 1 5 9 2 6 5 3 5
4
3 7
2 9
1 10
1 11

出力例2

6
22
90
175