DP Beginner Level
A. Long Jumps Input
The first line contains one integer t (1 ≤ t ≤ 10
4
) — the number of test
2 seconds, 256 megabytes cases. Then t test cases follow.
Polycarp found under the Christmas tree an array a of n elements and The first line of each test case contains one integer n (
instructions for playing with it: 1 ≤ n ≤ 2 ⋅ 10
5
) — the length of the array a.
At first, choose index i (1 ≤ i ≤ n) — starting position in the array. The next line contains n integers a1 , a2 , … , an (1 ≤ ai ≤ 10
9
)—
Put the chip at the index i (on the value ai ). elements of the array a.
While i ≤ n, add ai to your score and move the chip ai positions to
It is guaranteed that the sum of n over all test cases does not exceed
the right (i.e. replace i with i + ai ).
2 ⋅ 10
5
.
If i > n , then Polycarp ends the game.
Output
For example, if n = 5 and a = [7, 3, 1, 2, 3] , then the following game
For each test case, output on a separate line one number — the maximum
options are possible:
score that Polycarp can get by playing the game on the corresponding
+7
array according to the instruction from the statement. Note that Polycarp
Polycarp chooses i = 1 . Game process: i = 1 ⟶ 8 . The score of chooses any starting position from 1 to n in such a way as to maximize
the game is: a1 = 7 . his result.
+3 +3
Polycarp chooses i = 2 . Game process: i = 2 ⟶ 5 ⟶ 8 . The
input
score of the game is: a2 + a5 = 6 .
+1 +2 4
Polycarp chooses i = 3 . Game process: i = 3 ⟶ 4 ⟶ 6 . The 5
score of the game is: a3 + a4 = 3. 7 3 1 2 3
+2
3
Polycarp chooses i = 4 . Game process: i = 4 ⟶ 6 . The score of 2 1 4
6
the game is: a4 = 2 .
2 1000 2 3 995 1
+3
Polycarp chooses i = 5 . Game process: i = 5 ⟶ 8 . The score of 5
1 1 1 1 1
the game is: a5 = 3.
Help Polycarp to find out the maximum score he can get if he chooses the
starting index in an optimal way.
output input
7 5 5 3 2
6
1000 output
5 2
The first test case is explained in the statement.
In the second test case, the maximum score can be achieved by choosing input
i = 1. 7 5 5 2
In the third test case, the maximum score can be achieved by choosing output
i = 2. 2
In the fourth test case, the maximum score can be achieved by choosing
In the first example Polycarpus can cut the ribbon in such way: the first
i = 1.
piece has length 2, the second piece has length 3.
In the second example Polycarpus can cut the ribbon in such way: the first
B. Cut Ribbon piece has length 5, the second piece has length 2.
1 second, 256 megabytes
Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a C. New Skateboard
way that fulfils the following two conditions: 1 second, 256 megabytes
After the cutting each ribbon piece should have length a, b or c. Max wants to buy a new skateboard. He has calculated the amount of
After the cutting the number of ribbon pieces should be maximum. money that is needed to buy a new skateboard. He left a calculator on the
floor and went to ask some money from his parents. Meanwhile his little
Help Polycarpus and find the number of ribbon pieces after the required brother Yusuf came and started to press the keys randomly. Unfortunately
cutting.
Max has forgotten the number which he had calculated. The only thing he
Input knows is that the number is divisible by 4.
The first line contains four space-separated integers n, a, b and c You are given a string s consisting of digits (the number on the display of
(1 ≤ n, a, b, c ≤ 4000) — the length of the original ribbon and the the calculator after Yusuf randomly pressed the keys). Your task is to find
acceptable lengths of the ribbon pieces after the cutting, correspondingly. the number of substrings which are divisible by 4. A substring can start
The numbers a, b and c can coincide. with a zero.
Output A substring of a string is a nonempty sequence of consecutive characters.
Print a single number — the maximum possible number of ribbon pieces.
It is guaranteed that at least one correct ribbon cutting exists.
For example if string s is 124 then we have four substrings that are output
divisible by 4: 12, 4, 24 and 124. For the string 04 the answer is three: 0,
9
4, 04.
As input/output can reach huge size it is recommended to use fast
input/output methods: for example, prefer to use D. Vacations
gets/scanf/printf instead of getline/cin/cout in C++, 1 second, 256 megabytes
prefer to use BufferedReader/PrintWriter instead of
Scanner/System.out in Java. Vasya has n days of vacations! So he decided to improve his IT skills and
Input do sport. Vasya knows the following information about each of this n
The only line contains string s (1 ≤ |s| ≤ 3·105). The string s contains days: whether that gym opened and whether a contest was carried out in
only digits from 0 to 9. the Internet on that day. For the i-th day there are four options:
Output 1. on this day the gym is closed and the contest is not carried out;
Print integer a — the number of substrings of the string s that are divisible 2. on this day the gym is closed and the contest is carried out;
by 4. 3. on this day the gym is open and the contest is not carried out;
4. on this day the gym is open and the contest is carried out.
Note that the answer can be huge, so you should use 64-bit integer type
to store it. In C++ you can use the long long integer type and in Java On each of days Vasya can either have a rest or write the contest (if it is
you can use long integer type.
carried out on this day), or do sport (if the gym is open on this day).
input Find the minimum number of days on which Vasya will have a rest (it
means, he will not do sport and write the contest at the same time). The
124
only limitation that Vasya has — he does not want to do the same activity
output on two consecutive days: it means, he will not do sport on two consecutive
4 days, and write the contest on two consecutive days.
Input
input The first line contains a positive integer n (1 ≤ n ≤ 100) — the number of
04 days of Vasya's vacations.
output The second line contains the sequence of integers a1, a2, ..., an
3 (0 ≤ ai ≤ 3) separated by space, where:
input ai equals 0, if on the i-th day of vacations the gym is closed and the
contest is not carried out;
5810438174
ai equals 1, if on the i-th day of vacations the gym is closed, but the In the second test Vasya should write contests on days number 1, 3, 5 and
contest is carried out; 7, in other days do sport. Thus, he will not have a rest for a single day.
ai equals 2, if on the i-th day of vacations the gym is open and the In the third test Vasya can do sport either on a day number 1 or number 2.
contest is not carried out; He can not do sport in two days, because it will be contrary to the his
ai equals 3, if on the i-th day of vacations the gym is open and the limitation. Thus, he will have a rest for only one day.
contest is carried out.
Output E. Basketball Exercise
Print the minimum possible number of days on which Vasya will have a
rest. Remember that Vasya refuses: 2 seconds, 256 megabytes
to do sport on any two consecutive days, Finally, a basketball court has been opened in SIS, so Demid has decided
to write the contest on any two consecutive days. to hold a basketball exercise session. 2 ⋅ n students have come to
Demid's exercise session, and he lined up them into two rows of the same
input size (there are exactly n people in each row). Students are numbered from
1 to n in each row in order from left to right.
4
1 3 2 0
output
2
input
7 Now Demid wants to choose a team to play basketball. He will choose
1 3 3 2 1 2 3 players from left to right, and the index of each chosen player (excluding
the first one taken) will be strictly greater than the index of the previously
output
chosen player. To avoid giving preference to one of the rows, Demid
0 chooses students in such a way that no consecutive chosen students
belong to the same row. The first student can be chosen among all 2n
input students (there are no additional constraints), and a team can consist of
2 any number of students.
2 2
Demid thinks, that in order to compose a perfect team, he should choose
output students in such a way, that the total height of all chosen students is
1 maximum possible. Help Demid to find the maximum possible total height
of players in a team he can choose.
In the first test Vasya can write the contest on the day number 1 and do
sport on the day number 3. Thus, he will have a rest for only 2 days.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 10
5
) — the In the first example Demid can choose the following team as follows:
number of students in each row.
The second line of the input contains n integers h1,1 , h1,2 , … , h1,n (
9
1 ≤ h1,i ≤ 10 ), where h1,i is the height of the i-th student in the first
row.
The third line of the input contains n integers h2,1 , h2,2 , … , h2,n (
1 ≤ h2,i ≤ 10
9
), where h2,i is the height of the i-th student in the
second row.
Output In the second example Demid can choose the following team as follows:
Print a single integer — the maximum possible total height of players in a
team Demid can choose.
input
5
9 3 5 7 3
5 8 1 4 5
output
29
input
F. k-Tree
3 1 second, 256 megabytes
1 2 9
10 1 1 Quite recently a creative student Lesha had a lecture on trees. After the
lecture Lesha was inspired and came up with the tree of his own which he
output
called a k-tree.
19
A k-tree is an infinite rooted tree where:
input
each vertex has exactly k children;
1 each edge has some weight;
7
4 if we look at the edges that goes from some vertex to its children
(exactly k edges), then their weights will equal 1, 2, 3, ..., k.
output
7 The picture below shows a part of a 3-tree.
input
4 3 2
output
6
input
4 5 2
As soon as Dima, a good friend of Lesha, found out about the tree, he
immediately wondered: "How many paths of total weight n (the sum of all
output
weights of the edges in the path) are there, starting from the root of a k- 7
tree and also containing at least one edge of weight at least d?".
Help Dima find an answer to his question. As the number of ways can be
rather large, print it modulo 1000000007 (109 + 7).
G. Easy Problem
Input 2 seconds, 256 megabytes
A single line contains three space-separated integers: n, k and d
Vasya is preparing a contest, and now he has written a statement for an
(1 ≤ n, k ≤ 100; 1 ≤ d ≤ k).
easy problem. The statement is a string of length n consisting of
Output lowercase Latin latters. Vasya thinks that the statement can be
Print a single integer — the answer to the problem modulo 1000000007 considered hard if it contains a subsequence hard; otherwise the
9
(10 + 7). statement is easy. For example, hard, hzazrzd, haaaaard can be
considered hard statements, while har, hart and drah are easy
input statements.
3 3 2 Vasya doesn't want the statement to be hard. He may remove some
output characters from the statement in order to make it easy. But, of course,
some parts of the statement can be crucial to understanding. Initially the
3
ambiguity of the statement is 0, and removing i-th character increases the
ambiguity by ai (the index of each character is considered as it was in the
input original statement, so, for example, if you delete character r from hard,
3 3 3 and then character d, the index of d is still 4 even though you delete it
from the string had).
output
1 Vasya wants to calculate the minimum ambiguity of the statement, if he
removes some characters (possibly zero) so that the statement is easy.
Help him to do it!
Recall that subsequence is a sequence that can be derived from another output
sequence by deleting some elements without changing the order of the
0
remaining elements.
In the first example, first two characters are removed so the result is
Input
ardh.
The first line contains one integer n (1 ≤ n ≤ 10
5
) — the length of the
statement. In the second example, 5-th character is removed so the result is
hhzawde.
The second line contains one string s of length n, consisting of lowercase
Latin letters — the statement written by Vasya. In the third example there's no need to remove anything.
The third line contains n integers a1 , a2 , … , an (
1 ≤ ai ≤ 998244353 ).
Output
Print minimum possible ambiguity of the statement after Vasya deletes
some (possibly zero) characters so the resulting statement is easy.
input
6
hhardh
3 2 9 11 7 1
output
5
input
8
hhzarwde
3 2 6 9 4 8 7 1
output
4
input
6
hhaarr
1 2 3 4 5 6
Codeforces (c) Copyright 2010-2023 Mike Mirzayanov
The only programming contests Web 2.0 platform
