Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
スーパーマーケットで卵のパックが売られています。
卵 6 個入りのパックは S 円、卵 8 個入りのパックは M 円、卵 12 個入りのパックは L 円です。
どのパックも何パックでも購入できるとき、N 個以上の卵を買うために必要な最小の金額を求めてください。
制約
- 1 \leq N \leq 100
- 1 \leq S,M,L \leq 10^4
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N S M L
出力
答えを出力せよ。
入力例 1
16 120 150 200
出力例 1
300
8 個入りのパックを 2 個買うのが最適です。
入力例 2
10 100 50 10
出力例 2
10
12 個入りのパックを 1 個買うのが最適です。
入力例 3
99 600 800 1200
出力例 3
10000
8 個入りのパックと 12 個入りのパックを 5 個ずつ買うのが最適です。
Score : 200 points
Problem Statement
A supermarket sells egg packs.
A pack of 6 eggs costs S yen, a pack of 8 eggs costs M yen, and a pack of 12 eggs costs L yen.
When you can buy any number of each pack, find the minimum amount of money required to purchase at least N eggs.
Constraints
- 1 \leq N \leq 100
- 1 \leq S,M,L \leq 10^4
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N S M L
Output
Print the answer.
Sample Input 1
16 120 150 200
Sample Output 1
300
It is optimal to buy two 8-egg packs.
Sample Input 2
10 100 50 10
Sample Output 2
10
It is optimal to buy one 12-egg pack.
Sample Input 3
99 600 800 1200
Sample Output 3
10000
It is optimal to buy five 8-egg packs and five 12-egg packs.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
文字列 S が与えられます。
S の中に A, B, C がこの順に等間隔に並んでいる場所が何箇所あるか求めてください。
厳密には、3 つの整数の組 (i,j,k) であって、以下の条件をすべて満たすものの個数を求めてください。 ここで、|S| で S の長さを、S_x で S の x 文字目を表すものとします。
- 1\leq i<j<k\leq |S|
- j-i = k-j
- S_i=
A - S_j=
B - S_k=
C
制約
- S は英大文字からなる長さ 3 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
AABCC
出力例 1
2
(i,j,k)=(1,3,5),(2,3,4) の 2 つの組が条件を満たします。
入力例 2
ARC
出力例 2
0
入力例 3
AABAAABBAEDCCCD
出力例 3
4
Score : 200 points
Problem Statement
A string S is given.
Find how many places in S have A, B, and C in this order at even intervals.
Specifically, find the number of triples of integers (i,j,k) that satisfy all of the following conditions. Here, |S| denotes the length of S, and S_x denotes the x-th character of S.
- 1 \leq i < j < k \leq |S|
- j - i = k - j
- S_i =
A - S_j =
B - S_k =
C
Constraints
- S is an uppercase English string with length between 3 and 100, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
AABCC
Sample Output 1
2
There are two triples (i,j,k) = (1,3,5) and (2,3,4) that satisfy the conditions.
Sample Input 2
ARC
Sample Output 2
0
Sample Input 3
AABAAABBAEDCCCD
Sample Output 3
4
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 頂点の木 T があり、 i (1\leq i\leq N-1) 番目の辺は頂点 U_i と頂点 V_i を結んでいます。
T 上の相異なる 2 頂点 X,Y が与えられるので、 頂点 X から頂点 Y への単純パス上の頂点（端点含む）を順に列挙してください。
ただし、木上の任意の相異なる 2 頂点 a,b について、a から b への単純パスがただ一つ存在することが証明できます。
単純パスとは？
グラフ G 上の頂点 X,Y に対して、頂点列 v_1,v_2, \ldots, v_k であって、 v_1=X, v_k=Y かつ、1\leq i\leq k-1 に対して v_i と v_{i+1} が辺で結ばれているようなものを頂点 X から頂点 Y への パス と呼びます。 さらに、v_1,v_2, \ldots, v_k がすべて異なるようなものを頂点 X から頂点 Y への 単純パス と呼びます。制約
- 1\leq N\leq 2\times 10^5
- 1\leq X,Y\leq N
- X\neq Y
- 1\leq U_i,V_i\leq N
- 入力はすべて整数
- 与えられるグラフは木
入力
入力は以下の形式で標準入力から与えられる。
N X Y
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
出力
頂点 X から頂点 Y への単純パス上の頂点番号を順に空白区切りで出力せよ。
入力例 1
5 2 5 1 2 1 3 3 4 3 5
出力例 1
2 1 3 5
木 T は以下のような形であり、頂点 2 から頂点 5への単純パスは
頂点 2 \to 頂点 1 \to 頂点 3 \to 頂点 5 となります。
よって、2,1,3,5 をこの順に空白区切りで出力します。
入力例 2
6 1 2 3 1 2 5 1 2 4 1 2 6
出力例 2
1 2
木 T は以下のような形です。
Score : 300 points
Problem Statement
There is a tree T with N vertices. The i-th edge (1\leq i\leq N-1) connects vertex U_i and vertex V_i.
You are given two different vertices X and Y in T. List all vertices along the simple path from vertex X to vertex Y in order, including endpoints.
It can be proved that, for any two different vertices a and b in a tree, there is a unique simple path from a to b.
What is a simple path?
For vertices X and Y in a graph G, a path from vertex X to vertex Y is a sequence of vertices v_1,v_2, \ldots, v_k such that v_1=X, v_k=Y, and v_i and v_{i+1} are connected by an edge for each 1\leq i\leq k-1. Additionally, if all of v_1,v_2, \ldots, v_k are distinct, the path is said to be a simple path from vertex X to vertex Y.Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq X,Y\leq N
- X\neq Y
- 1\leq U_i,V_i\leq N
- All values in the input are integers.
- The given graph is a tree.
Input
The input is given from Standard Input in the following format:
N X Y
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
Output
Print the indices of all vertices along the simple path from vertex X to vertex Y in order, with spaces in between.
Sample Input 1
5 2 5 1 2 1 3 3 4 3 5
Sample Output 1
2 1 3 5
The tree T is shown below. The simple path from vertex 2 to vertex 5 is 2 \to 1 \to 3 \to 5.
Thus, 2,1,3,5 should be printed in this order, with spaces in between.
Sample Input 2
6 1 2 3 1 2 5 1 2 4 1 2 6
Sample Output 2
1 2
The tree T is shown below.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
ピザ屋で働く高橋くんは、まかないとして美味しいチーズピザを作ることにしました。
今、高橋くんの目の前に N 種類のチーズがあります。
i 種類目のチーズは 1 [g] あたりのおいしさが A_i で、 B_i [g] あります。
ピザのおいしさは、ピザに乗せたチーズのおいしさの総和で決まります。
但し、チーズを使いすぎると怒られてしまうため、乗せたチーズの重さは合計で W [g] 以下である必要があります。
この条件のもとで、可能なピザのおいしさの最大値を求めてください。
制約
- 入力は全て整数
- 1 \le N \le 3 \times 10^5
- 1 \le W \le 3 \times 10^8
- 1 \le A_i \le 10^9
- 1 \le B_i \le 1000
入力
入力は以下の形式で標準入力から与えられる。
N W A_1 B_1 A_2 B_2 \vdots A_N B_N
出力
答えを整数として出力せよ。
入力例 1
3 5 3 1 4 2 2 3
出力例 1
15
1 種類目のチーズを 1 [g] 、 2 種類目のチーズを 2 [g] 、 3 種類目のチーズを 2 [g] 乗せるのが最適です。
このとき、ピザのおいしさは 15 となります。
入力例 2
4 100 6 2 1 5 3 9 8 7
出力例 2
100
チーズの重量の総和が W [g] に満たないケースもあります。
入力例 3
10 3141 314944731 649 140276783 228 578012421 809 878510647 519 925326537 943 337666726 611 879137070 306 87808915 39 756059990 244 228622672 291
出力例 3
2357689932073
Score : 300 points
Problem Statement
Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are N kinds of cheese in front of him.
The deliciousness of the i-th kind of cheese is A_i per gram, and B_i grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most W grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.
Constraints
- All values in input are integers.
- 1 \le N \le 3 \times 10^5
- 1 \le W \le 3 \times 10^8
- 1 \le A_i \le 10^9
- 1 \le B_i \le 1000
Input
Input is given from Standard Input in the following format:
N W A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
Print the answer as an integer.
Sample Input 1
3 5 3 1 4 2 2 3
Sample Output 1
15
The optimal choice is to use 1 gram of cheese of the first kind, 2 grams of the second kind, and 2 grams of the third kind.
The pizza will have a deliciousness of 15.
Sample Input 2
4 100 6 2 1 5 3 9 8 7
Sample Output 2
100
There may be less than W grams of cheese in total.
Sample Input 3
10 3141 314944731 649 140276783 228 578012421 809 878510647 519 925326537 943 337666726 611 879137070 306 87808915 39 756059990 244 228622672 291
Sample Output 3
2357689932073
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
長さ n の数列 S = (s_1, s_2, \dots, s_n) がすべての i (1 \leq i \leq n - 1) に対して s_i \leq s_{i+1} を満たすとき、かつそのときに限り「数列 S は広義単調増加である」と呼びます。
広義単調増加な長さ N の整数列 A = (a_1, a_2, \dots, a_N), B = (b_1, b_2, \dots, b_N) が与えられます。
このとき、次の条件を満たす広義単調増加な長さ N の整数列 C = (c_1, c_2, \dots, c_N) を考えます。
- すべての i (1 \leq i \leq N) に対して a_i \leq c_i \leq b_i が成り立つ。
整数列 C としてあり得る数列の個数を 998244353 で割ったあまりを求めてください。
制約
- 1 \leq N \leq 3000
- 0 \leq a_i \leq b_i \leq 3000 (1 \leq i \leq N)
- 整数列 A,B は広義単調増加である。
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 \dots a_N b_1 b_2 \dots b_N
出力
C としてあり得る数列の個数を 998244353 で割ったあまりを出力せよ。
入力例 1
2 1 1 2 3
出力例 1
5
C としてあり得る数列は次の 5 個です。
- (1, 1)
- (1, 2)
- (1, 3)
- (2, 2)
- (2, 3)
数列 (2, 1) は広義単調増加でないため条件を満たさないことに注意してください。
入力例 2
3 2 2 2 2 2 2
出力例 2
1
C としてあり得る数列は次の 1 個です。
- (2, 2, 2)
入力例 3
10 1 2 3 4 5 6 7 8 9 10 1 4 9 16 25 36 49 64 81 100
出力例 3
978222082
個数を 998244353 で割ったあまりを求めることに注意してください。
Score : 400 points
Problem Statement
A sequence of n numbers, S = (s_1, s_2, \dots, s_n), is said to be non-decreasing if and only if s_i \leq s_{i+1} holds for every i (1 \leq i \leq n - 1).
Given are non-decreasing sequences of N integers each: A = (a_1, a_2, \dots, a_N) and B = (b_1, b_2, \dots, b_N).
Consider a non-decreasing sequence of N integers, C = (c_1, c_2, \dots, c_N), that satisfies the following condition:
- a_i \leq c_i \leq b_i for every i (1 \leq i \leq N).
Find the number, modulo 998244353, of sequences that can be C.
Constraints
- 1 \leq N \leq 3000
- 0 \leq a_i \leq b_i \leq 3000 (1 \leq i \leq N)
- The sequences A and B are non-decreasing.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N a_1 a_2 \dots a_N b_1 b_2 \dots b_N
Output
Print the number, modulo 998244353, of sequences that can be C.
Sample Input 1
2 1 1 2 3
Sample Output 1
5
There are five sequences that can be C, as follows.
- (1, 1)
- (1, 2)
- (1, 3)
- (2, 2)
- (2, 3)
Note that (2, 1) does not satisfy the condition since it is not non-decreasing.
Sample Input 2
3 2 2 2 2 2 2
Sample Output 2
1
There is one sequence that can be C, as follows.
- (2, 2, 2)
Sample Input 3
10 1 2 3 4 5 6 7 8 9 10 1 4 9 16 25 36 49 64 81 100
Sample Output 3
978222082
Be sure to find the count modulo 998244353.