Dynamic programming

ID 31928. Computer assembly

ID 28419. Template with? *

ID 30783. gardener-artist

ID 33142. Knight's move_1

Examples

ID 33143. Knight's move - 2

Given a rectangular board N × M (N rows and M columns). In the upper left corner is a chess knight, which must be moved to the lower right corner of the board. In this case, the horse can only walk as shown in the figure:

Examples

ID 23416. Equation with missing digits

Examples

ID 37892. Ant farm

ID 37893. King

Domovoy Kuzma loves to play checkers on an 8x8 board. When no one wants to play with him, he just sits and thinks. For example, now he is trying to calculate how many there are ways to push a white checker to the kings, if it is alone on the board?
(The white checker moves diagonally one cell up-right or up-left. The checker goes to the kings if it hits the top horizontal.)

Two numbers are entered from 1 to 8: the number is the number of the column (counting from the left) and the row (counting from the bottom) where the checker originally stands.

Print one number - the number of options.

Examples

ID 30767. Maximum sum of adjacent elements

Examples

ID 33135. Sawmill

ID 38143. cow counting

Farmer John's cows scattered across a huge pasture, represented as a 2D grid (chessboard).  Placement of cows is very entertaining. For each cell (x,y) c \(x>=0\)  and \(y>=0\), there is a cow in cell (x,y),  if for all integers \(k>=0\), the remainders \(\lfloor {\frac {x}{3^k} }\rfloor\) and \(\lfloor {\frac {y}{3^k} }\rfloor\ ) modulo 3 have the same parity. In other words, these remainders are both odd (equal to 1) or both even (equal to 0 or 2). For example, cells for  \(0<=x,y<9\) that contain cows are labeled 1 in the figure below.

 x
    012345678

  0 101000101
  1 010000010
  2 101000101
  3 000101000
y4000010000
  5 000101000
  6 101000101
  7 010000010
  8 101000101

ID 38144. Contemporary Art - 3

Bored with the standard two-dimensional artwork (and also frustrated that others copy her work), the great artist Picouso decided to move towards a more minimalist, one-dimensional style. Her final painting can be described by a one-dimensional array of colors of length N (\(1<=N<=300\)), where each color is specified an integer in the range \(1…N\).
Much to Picouso's dismay, her rival Mune seems to have figured out how to replicate even these one-dimensional paintings! Mune paints one interval with one color, waits for it to dry, then paints another interval, and so on. Mune can use each of the N colors as many times as she wants (possibly none).

Calculate the minimum number of brush strokes with one color that Muna needs to copy a Picouso painting.


Input
The first line contains the number N. The next line contains N integers in the range \(1…N\) indicating the color of each cell in Picouso's painting.

Examples

Explanation

In this example, Mounet can copy the picture like this: (unfilled cells are indicated by color 0).

Initially, the entire array is unfilled:
0 0 0 0 0 0 0 0 0 0
Mune paints the first 9 cells with color 1:
1 1 1 1 1 1 1 1 1 0
Mune paints the interval with color 2:
1 2 2 2 2 2 2 2 1 0
Mune paints the interval with color 3:
1 2 3 3 3 3 3 2 1 0
Mune paints the interval with color 4:
1 2 3 4 4 4 3 2 1 0
Mune paints one cell with color 1:
1 2 3 4 1 4 3 2 1 0
Mune paints the last cell with color 6:
1 2 3 4 1 4 3 2 1 6
Note that on the first stroke of the brush, it was possible to paint over the tenth cell with color 1. It wouldn't change the final state.

ID 38444. villages

There are N villages in the thirtieth state. Some pairs of villages are connected by roads. In order to save money, “superfluous” there are no roads, i.e. There is only one way to get from any village to any village by road.
The latest research has shown that the thirtieth state is located in a seismically dangerous zone. Therefore, the head of state wanted to know what kind of damage an earthquake could bring to his country. Namely, he wants to know what is the minimum number of roads that must be destroyed in order to form a group of exactly P villages, isolated from the rest, such that from any village from this group to any other village from this group it will still be possible to get by undestroyed roads (a group is isolated from the rest if no undamaged road connects a village in this group with a village not in this group).
You should write a program to help him with this.

Input data format
The first line of the input file contains two numbers: N and P (1 ≤ P ≤ N ≤ 150). All other lines contain road descriptions, one per line: the road description consists of two village numbers (from 1 to N) that this road connects. All numbers in the input file are separated by spaces and/or newlines.

Output data format
In the output file print a single number — desired number of roads.

Examples

ID 38475. skyline

You want the skyscrapers in your city to look good. It is decided to build N skyscrapers in a row. The skyscraper with number i must have exactly h[i] floors.

You have offers from various construction companies. The first of them proposes to build one floor in any of the skyscrapers for 3 million euros. The second proposes to build one floor in each of the two neighboring skyscrapers for 5 million euros. Note that it doesn't matter if these floors are at the same height or not. A third company is offering to build one floor in each of three consecutive skyscrapers for 7 million euros.

You can build the floors in any order. Calculate the minimum amount of money required for construction.

Input
The first line contains one integer N (1 ≤ N ≤ 300). The second line contains N integers h[1], h[2] ..., h[N], 1 ≤ h[i]≤ 200.

Imprint
In a single line print one integer: the minimum amount of money for construction, in millions.

ID 38509. Substrings of subsequences

Let's call a subsequence of array a a non-empty array b such that it can be obtained from array a by deleting some (possibly none) elements of array a. For example, array [1,3]  is a sequence of array [1,2,3] , but [3,1]  is not.

Let's call a subsegment of array a a non-empty array b such that it can be obtained by deleting several (possibly none) of the first and last elements of array a. For example, [1,2]  is a subsegment of the array [1,2,3] , but [1,3]  is not. It is easy to see that an array of length n has exactly  \( {n(n+1) \over 2}\)  subsegments.

Let's call an array a of length n increasing if for any 1 ≤ i≤ n a_i ≤ a_i+1.

The monotonicity of an array is the number of its increasing subsegments.

Given an array a of length n. Calculate the sum of monotonicities over all its subsequences. Since the answer can be very large, print it modulo 10⁹+7.

Input
The first line contains an integer n (1 ≤ n ≤ 200000) — array length a.
The second line contains n integers (1 ≤ a_i ≤ 200000) — array elements a.

Imprint
Print a single integer — the sum of the monotonicities of all subsequences modulo 10⁹+7.

Note
In the first test case, the array has 7 subsequences:

• Array [1]  has exactly one subsegment and is ascending.
• The array [2]   has exactly one subsegment and is increasing.
• The array [3]  has exactly one subsegment and is increasing.
• The array [1,2]  has three subsegments ([1], [2], [1,2] ) and they are all increasing.
• The array [1,3]  has three subsegments ([1], [3], [1,3] ) and they are all increasing.
• The array [3,2]   has three subsegments ([3], [2], [3, 2] ), but only two of them ([3]  and [2] ) are ascending.
• The array [1,3,2]  has six subsegments ([1], [3], [2], [1,3], [3,2], [1,3,2] ) and four of them ([1], [3], [2], [1,3] ) are increasing.

Examples

ID 38511. Journey along the line

Let's say that the sequence of strings t₁ , ..., t_k is a journey of length k if for all i > 1 t<sub>i< /sub> is a substring of ti - 1 of strictly less length. For example, { ab , b } is a journey, and { ab , c } or { a , a } — no.

Define a string traversal s as a traversal t1 , ..., tk , all of whose strings can be nested in s such that there are (possibly empty) strings u1 , ..., uk + 1 such that s = u1t1 u2 t2 ... uk tk uk +&thinsp ;1 . For example, { ab , b } is a string travel for abb , but not for bab , since the corresponding substrings are from right to left.

Let's call the length of the journey the number of lines of which it consists. Determine the maximum possible travel length along the given string s .

Input
The first line contains an integer n ( 1 ≤ n ≤ 500 000 ) — length of string s .

The second line contains the string s , consisting of n lowercase English letters.

Imprint
Print one number — the longest travel length in string s .

Note
In the first example, the longest string traversal is { abcd , bc , c } .

In the second example, { bb , b } would be appropriate.</sub>

Examples

ID 38515. Burgers at McDuck's

The popular fast food chain «McDuck's» opened a new branch in Berland. The restaurant has k stoves. To cook a burger, you need to fry a patty for a minute on one of the stoves, so a restaurant can cook no more than k burgers per minute.

It is known that in «McDuck's» n clients will come. The i-th of them will arrive at time t_i, order x_i burgers and be ready to pay c_i burles for them. Each client is ready to wait for an order for w minutes, and if w minutes after arrival he has not received x_i burgers, he will not pay anything. At the same time, each client is ready to receive only fresh burgers, that is, only those for which the burgers were fried not earlier than the time t_i. Due to such complex requirements, the restaurant will not always be able to fulfill all the orders of all customers.

The restaurant managers were interested in the maximum profit McDuck's could make. Help them answer this difficult question. We can assume that no money is spent on cooking burgers.

Input
The first line contains three integers n, k and w (1 ≤ n ≤ 100000, 1 ≤ k ≤ 10, 1 ≤ w ≤ 60) — the number of clients, the number of plates and the waiting time for the client, respectively.

The next n lines contain descriptions of clients, consisting of three integers — t_i, x_i, c_i (1 ≤ t_i, x_i sub>, c_i ≤ 10⁹) — the time (in minutes) of arrival of the i-th customer, the number of burgers he will order and the number of burles he is willing to pay, respectively. Clients are listed in ascending order of arrival time, i.e. for any i > 1 it is true that t_i−1 ≤ t_i.

Imprint
In a single line print a single number — maximum restaurant profit.

Note
In the first test example, the first patty can be fried at time 0, and then at time 1 it will be ready and can be served in a burger to the first client. At time 1, you can put another patty to fry, it will be ready at time 2 and can be served in a burger to the second client.
 

Examples

ID 38634. Number cookies - 2

Gromozeka has N cookies. The i-th (1<=i<=N) cookie has an integer xi written on it. He chooses one or more of these cookies so that the average value of the integers written on the chosen cookies is A.
In what ways can he make his choice?

Input
The first line contains two integers N (1<=N<=50) and A (1<=A<=50). The second line contains N integers - xi (1<=xi<=50).

Imprint
Print one number - the number of ways to choose such cookies so that the average value of all written numbers on the cookies is exactly A.
 

Examples

ID 39959. Number of messages

In the message, consisting of only Russian letters and spaces, each letter was replaced by its serial number in the Russian alphabet (A – 1, B – 2, …, I – 33), and the space – zero. 
Given a given sequence of digits, it is required to find the number of original messages from which it could be obtained.

Input:
The first line contains a sequence of no more than 70 digits.

Output:
Print one number - the number of possible messages.

Example:
 

ID 39960. Comfort Ride Max

Max is at the starting station of the train, and now n people (including Max herself) want to get on it. They are already lined up in some order, and each of them knows the area code a_i to which they are going.

The head of the train chooses a certain number of non-intersecting segments of the original sequence of people (the segments do not have to cover the entire sequence). People who are in the same segment will be in the same train car. The segments are chosen so that if at least one person goes to city X, then all people who go to city X will have to be in the same car. This means that they do not have the right to belong to different segments. It should be noted that all people who go to city X either go to it and are in the same car, or do not go anywhere at all.

The comfort of traveling on a train with people on the segment from l to r is equal to the XOR of different city codes for people on the segment from l to r. The XOR operation is also known as bitwise exclusive OR.

The overall comfort of the selected segments is calculated as the sum of the comfort of each individual segment.

Help Max find out the maximum achievable overall comfort.

Input:
The first line contains a natural number n - the number of people.
The second line contains n integers a_i (0 <= a_i <= 5000) - the code of the city the i-th person is going to.

Output:
Print one integer - the maximum overall comfort.

Examples:
 

ID 39961. Sum of lows

You are given an array of n integers. You need to divide it into k non-empty subsegments (a sequence of consecutive elements) so that:
1) Each element of the array was included in exactly one subsegment.
2) If for each subsegment we choose the minimum number in it, then the sum of all minima should be the maximum possible.

Report the sum of the minima of the values ​​in the subsegments of this partition.

Input:
The first line contains two natural numbers - n (1 <= n <= 500) and k (1 <= k <= n).
The second line contains n integers - the elements of the array a_i (1 <= a_i <= 10⁵).

Output:
Print one number - the answer to the problem.

Example:
 

ID 39962. String compression

Chloe wants to write a letter to her friend. Letter - string s, consisting of lowercase Latin letters.
Unfortunately, as soon as Chloe started writing the letter, she realized that it was too long, and it would take a very long time to write it in its entirety. So she wants to write a compressed version of the string s instead of the string itself.

A compressed version of the string s — the sequence of strings c₁, s₁, c₂, s₂,  ..., c_k, s_k, where c_i — decimal representation of a_i (without leading zeros), and s_i — some string of lowercase Latin letters. If Chloe writes the string s₁ exactly a₁ times, then s₂ exactly a₂ times, and so on , it will produce the string s.
The length of the compressed version is |c₁| + |s₁| + |c₂| +  |s₂|... |c_k| + |s_k|. Among all the compressed versions, Chloe wants to choose the one with the shortest length. Help Chloe find the shortest possible length.

Input:
The single line of the input contains a string s consisting of lowercase Latin letters (1 ≤ |s| ≤ 5000).

Output:
Print a single integer — the minimum length of the compressed version of the string s.

Examples:
 

ID 39963. Restaurant

The restaurant received n orders for a banquet. Each order is characterized by two values: the start time of the banquet l_i and the end time r_i (l_i ≤ r _i).

The restaurant management can either accept the order or reject it. What is the maximum number of orders that can be accepted?

No two accepted orders can intersect, that is, there should not be a point in time that belongs to two accepted orders at once. If one of the orders starts at the same time as the other ends, then they cannot be accepted together.

Input:
The first line contains an integer n (1 ≤ n ≤ 200000) — the number of orders. Each of the next n lines contains a pair of integers l_i, r_i (0 ≤ l_i &le ; r_i ≤ 10⁹).

Output:
Print the maximum number of orders that can be accepted.

Examples:
 

ID 39964. Maximum Questions

Max had two strings s of length n and t of length m written in her notebook, consisting of the letters "a"; and "b" Latin alphabet. Moreover, Max knows that the string t has the form «abab...», that is, the letter «a» is on the odd positions of the string, and the letter — "b".

Suddenly, in the morning, Max discovered that someone had messed up her string s. Some of the s's have been changed to "?".

Let's call the sequence of positions i, i + 1, ..., i + m - 1 an occurrence of string t in s, if 1 ≤ i ≤  n - m + 1 and t₁ = s_i, t₂&thinsp ;= s_i + 1, ..., t_m = s_{i +  m - 1}.

The beauty of string s is measured as the maximum number of non-overlapping occurrences of string t in it. Max can replace some of the "?" on "a" or "b" (characters in different positions can be replaced by different letters). Max wants to make substitutions so that the beauty of the string s is as large as possible. Of all these options, she wants to replace as few "?" characters as possible. Find out how many substitutions she has to make.

Input:
The first line contains a single integer n (1 ≤ n ≤ 10⁵) — string length s.
The second line of the input contains a string s of length n, consisting only of the letters "a"; and "b" the Latin alphabet, as well as the symbols «?».
The third line contains the integer m (1 ≤ m ≤ 10⁵) — string length t. The string t itself contains "a"; in odd positions, and "b" on even numbers.

Output:
Print a single integer — the minimum number of substitutions that Vasya must make in order to make the beauty of the string s the maximum possible.

Examples:
 

ID 40022. Interregional Olympiad

At the Interregional Robot Programming Olympiad, competitions are held in one round and in an unusual format. The tasks are given to the participants sequentially, not all at the very beginning of the round, and each i-th task (1 ≤ i ≤ n) becomes available to the participants at its time s_i. Upon receipt of the next task, each participant must immediately determine whether he will solve it or not. If he chooses to solve this problem, then he has t_i minutes to submit its solution for verification, and during this time he cannot switch to solving another problem. If the participant refuses to solve this problem, then in the future he cannot return to it. At the moment when the time allotted for the task that the participant is solving has ended, he can start solving another task that became available at the same moment, if there is such a task, or wait for another task to appear. At the same time, for the correct solution of the i-th problem, the participant receives c_i points.

Artur, who represents one of the regional artificial intelligence centers at the interregional Olympiad, understands that not only the ability to solve problems, but also the correct strategic calculation of which problems need to be solved and which ones to skip, plays an important role at such an Olympiad. He, like all participants, before the start of the tour knows at what point in time each task will become available, how much time will be allotted for its solution and how many points you can get for solving it. Artur is a talented student and therefore will be able to successfully solve any problem he chooses to solve at the Olympiad in the allotted time and pass for verification.

It is required to write a program that determines the maximum number of points Arthur can get with the optimal choice of problems that he will solve, as well as the number and list of such problems.

Input
The first line contains one integer n (1 ≤ n ≤ 10⁵) the number of problems in the Olympiad.

The next n lines contain descriptions of the problems, three numbers on each line: si the moment the i-th problem appears in minutes, t_i the time allotted for its solution in minutes, and ci how many points the participant will receive for solving this problem (1 ≤ s_i, t_i, c_i ≤ 10⁹).

Imprint
First line  must contain a single number – the maximum number of points that Arthur can get at the Olympiad.

The second line should contain one integer m - the number of tasks to be solved with the optimal choice.

The third line should contain m space-separated integers - the numbers of these problems in the order in which they were solved. The tasks are numbered, starting from one, in the order they are described in the input file.

If there are several optimal answers, print any of them.

Examples

ID 40058. fill game

You are given a strip of checkered paper made of n colored squares numbered from 1 to n from left to right. The i-th square is initially colored c_i.

We say that squares i and j lie in the same component if c_i = c_j and c_i = c_k for all k satisfying i < k < j. In other words, all squares on the segment from i to j must have the same color.
For example, the strip [3,3,3] has 1 connected component, while [5,2,4,4] has 3.

Fill game is played on this strip as follows:
At the beginning of the game, you choose one random starting square (this does not count as a turn).
Then, on each move, you change the color of the connected component containing the starting square to any other color.

Find out the minimum number of moves needed to recolor the entire strip in one color.

Input:
The first line contains a single integer n (1 ≤ n ≤ 5000) — number of squares.

The second line contains the integers c₁,c₂,…,c_n (1 ≤ c_i <5000) — the initial colors of the squares.

Output:
Print a single integer — the minimum number of moves to make.

Examples:
 

ID 40059. Zuma

Chloe recently installed Zuma on her phone. The player is given a row of n gems, the i-th of which has the color c_i. The purpose of the game — destroy all stones in as few seconds as possible.

In one second, Chloe can choose any substring (a sequence of adjacent stones) that is a palindrome and delete it. After removing this substring, the remaining stones are shifted to form a continuous row again. What is the minimum number of seconds needed to destroy the entire line?

Recall that a string (or substring) is a palindrome if it reads the same from left to right as from right to left. In this case, this means that the color of the first stone is equal to the color of the last stone, the color of the second is equal to the color of the penultimate one, and so on.

Input:
The first line of the input contains a single integer n (1 ≤ n ≤ 500) — the number of stones in the initial row.
The second line contains n integers, the i-th of which is equal to c_i (1 ≤ c_i ≤ n) — the color of the i-th stone in the initial row.

Output:
Print a single integer — the minimum number of seconds required to remove all gems.

Examples:
 

ID 40060. Removing pairs

Given a string consisting of uppercase Latin letters. It is possible to remove from this string all pairs of adjacent identical letters, including pairs formed after deleting other pairs. You need to replace 0 or more letters in the given string so that after deleting all pairs, the string becomes empty.

Input:
The first line contains one string of even length from 2 to 200, consisting of lowercase Latin letters.

Output:
In the first line print the minimum number of letter replacements.

Example: