Gauss
레이팅 미적용의견: 0
2 \(s / 256\) \(MB / 160\) points
It is a litt\(le-kn\)own story that the young Carl Friedrich Gauss was restless in class, so his
teacher came up with a task to keep him preoccupied.
The teacher gave him a series of positive integers F(1), F(2), ..., F(K). We consider F(t) = 0
for \(t > K\). Aditionally, she has given him a set of lucky numbers and the price of each lucky
number. If X is a lucky number, then C(X) denotes its price.
Initially, there’s a positive integer A written on the board. In each move, Carl must make one
of the following things:
●
If number N is currently written on the board, then Carl can write one of its divisors M,
smaller than N, instead of N. If he writes the number M, the price of the move is
F(d(\(N / M\))), where d(\(N/M\)) is the number of divisors of the positive integer \(N/M\)
(inlucluding \(N/M\)).
●
If N is a lucky number, Carl can leave that number on the board, and the price of the
move is C(N).
Carl must make exactly L moves, and after he has made all of his moves, the number B
must be written on the board. Let’s denote G(A, B, L) as the minimal price with which Carl
can achieve this.
If it is not possible to make L such moves, we define G(A, B, L) = -1.
The teacher has given Carl Q queries. In each query, Carl gets numbers A and B and must
calculate the value G(A, B, L {1}{ }) + G(A, B, L {2}{ }) + ... + G(A, B, L {M}{ }), where numbers L {1}{ }, ..., L {M}{ } are
the same for all queries.
The first line of input contains the positive integer K (\(1 \le K \le 10\,000\)).
The second line contains K positive integers F(1), F(2), ..., F(K) that are less than or equal to
1 000.
The following line contains the positive integer M (\(1 \le M \le 1\,000\)).
The following line contains M positive integers L {1}{ }, L {2}{ }, ..., L {M}{ } that are less than or equal to 10
000.
The following line contains the positive integer T, the total number of lucky numbers (\(1 \le T\) ≤
50).
Each of the following T lines contains numbers X and C(X) that denote that X is a lucky
number, and C(X) is his price (\(1 \le X \le 1\,000\,000\), \(1 \le C\)(X) ≤ 1 000).
Each lucky number appears at most once.
The following line contains the positive integer Q (\(1 \le Q \le 50\,000\)).
Each of the following Q lines contains 2 positive integers A and B (\(1 \le A\), \(B \le 1\,000\,000\)).
You must output Q lines. The i {th}{ } line contains the answer to the i {th}{ } query defined in the task.
2 \(s / 256\) \(MB / 160\) points
4
1 1 1 1
2
1 2
2
2 5
4 10
1
4 2
3
6 9 4
2
5 7
3
1 1
7 8
6 10
2
6 2
70 68
3
8 3 10
2
8 4
3
1 6
5 1
3 7
2
5 1
3 1output
output
7
118
-2
16
66Clarification of the first test case:
L 1 = 1, so Carl can make exactly one move - replace number 4 with number 2, so G(4, 2, 1) = F(d(2)) =
1.
L 2 = 2 so Carl has two options:
●
He can replace number 4 with number 2 and then leave number 2 (because it’s a lucky
number), so he pays the price F(d(4/2)) + C(2) = 1 + 5 = 6
●
He can leave number 4 in the first move, and replace it in the second move with number 2, so
the price is C(4) + F(d(4/2)) = 10 + 1 = 11
The first option costs less, so G(4, 2, 2) = 6.
The answer to the query is G(4,2,1) + G(4,2,2) = 7.
평가 및 의견
Gauss
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Gauss