Time Limit: 2 sec / Memory Limit: 256 MB
問題文
あなたは饅頭の店に来ています。ここでは白と緑の 2 種類の饅頭が売られていて、それぞれの種類は何個でも買うことができます。 白色の饅頭は 1 個 A 円で、緑色の饅頭は 1 個 B 円です。
あなたは C 円持っています。あなたはとにかく沢山の個数を食べたいので、種類は気にせず、なるべく多くの個数の饅頭を買おうと思っています。 2 種類で買う個数が違ったり、片方の種類しか買わなかったりしてもかまいません。
最大で何個の饅頭が買えるでしょうか。
制約
- 1 \leq A,B \leq 1,000
- 1 \leq C \leq 1,000,000
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
あなたが買える饅頭の個数の最大値を出力せよ。
入力例 1
3 5 6
出力例 1
2
入力例 2
8 6 20
出力例 2
3
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
長さ N の数列 \{a_i\} があります。最初、この数列の全ての要素は 0 です。
この数列に対し、計 Q 回次の操作を入力で与えられた順に行ってください。
- 数列の L_i 番目から R_i 番目 (両端を含む) を T_i に書き換える。ただし、数列の最初の要素が 1 番目である。
最終的に数列の各値が何になったかを求めてください。
制約
- 1 \leq N \leq 100
- 1 \leq Q \leq 100
- 1 \leq L_i \leq R_i \leq N
- 1 \leq T_i \leq 10^9
- T_i は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N Q L_1 R_1 T_1 : L_Q R_Q T_Q
出力
出力は N 行からなる。上から i 行目に操作後の a_i の値を出力せよ。
入力例 1
5 2 1 3 10 2 4 20
出力例 1
10 20 20 20 0
最初、数列は \{0, 0, 0, 0, 0\} です。 1 回目の操作の後、数列は \{10, 10, 10, 0, 0\} となります。 2 回目の操作の後、数列は \{10, 20, 20, 20, 0\} となります。
入力例 2
10 4 2 7 22 3 5 4 6 10 1 4 4 12
出力例 2
0 22 4 12 4 1 1 1 1 1
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
長さ N の数列 \{a_i\} と1 以上 N 以下の整数 K が与えられます。 この数列には長さ K の連続する部分列が N-K+1 個あります。これらのそれぞれ部分列に含まれる値の合計の総和を求めてください。
制約
- 1 \leq K \leq N \leq 10^5
- 0 \leq a_i \leq 10^8
- a_i は整数である。
部分点
- 50 点分のテストケースでは、 N \leq 10^3 である。
入力
入力は以下の形式で標準入力から与えられる。
N K a_1 .. a_N
出力
部分列に含まれる値の合計 N-K+1 個の総和を出力せよ。
入力例 1
5 3 1 2 4 8 16
出力例 1
49
(1+2+4)+(2+4+8)+(4+8+16)=49 なので、答えは 49 です。
入力例 2
20 10 100000000 100000000 98667799 100000000 100000000 100000000 100000000 99986657 100000000 100000000 100000000 100000000 100000000 98995577 100000000 100000000 99999876 100000000 100000000 99999999
出力例 2
10988865195
オーバーフローに注意してください。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
H * W のマス目があり、それぞれのマスには整数が書かれています。 i 行 j 列に書かれている数は a_{ij} です。
あなたはこのグリッドの中の好きなマスから好きなだけ動きます(最初のマスから動かなくてもかまいません)。 今いるマスの上下左右に隣接しているマスのうち、今いるマスより大きな整数が書かれたマスに移動することができます。
ありうる移動経路の個数を10^9+7で割った余りを求めてください。
制約
- 1 \leq H, W \leq 1,000
- 1 \leq a_{ij} \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
H W
a_{11} .. a_{1W}
:
a_{H1} .. a_{HW}
出力
移動経路の個数を10^9+7で割った余りを出力せよ。
入力例 1
2 3 1 4 5 2 4 9
出力例 1
18
例えば、1 行 2 列から出発し、右、下と移動する経路や、 1 行 1 列から出発し、下に移動する経路などがあります。
全部で 18 種類の経路があります。
入力例 2
6 6 1 3 4 6 7 5 1 2 4 8 8 7 2 7 9 2 7 2 9 4 2 7 6 5 2 8 4 6 7 6 3 7 9 1 2 7
出力例 2
170