Tutorial•8 saat öncə

Educational Round #6 — Editorial

Bruno and his friends are playing with water guns. They are avid gamers, so their game is not an ordinary water fight but almost like a real video game. They even invited a moderator to keep track of the gameplay.

At the beginning of the game, the players are divided into two teams — "Pineapple" and "Blueberry".

During the game, the moderator records the moments when one player shoots another. As in video games, successful shots earn points.

If a player from one team hits a player from the opposite team, their team earns $100$ points. However, if the same player hits some opponent within the next $10$ seconds, that shot is considered a double shot, and the team receives an additional $50$ points. A player can make several double shots in a row — for each of them, their team gains another $50$ points in addition to the regular $100$ .

Input. The first line contains one integer $n (1 \leq n \leq 100)$ — the number of shots made during the game.

Each of the next $n$ lines contains three integers $t_{i}$ , $a_{i}$ , $b_{i} (0 \leq t_{i} \leq 1000, 1 \leq a_{i}, b_{i} \leq 8)$ , meaning that player $a_{i}$ shot player $b_{i}$ at time $t_{i}$ (in seconds).

Players from team "Pineapple" are numbered from $1$ to $4$ , and players from team "Blueberry" are numbered from $5$ to $8$ . It is guaranteed that in each shot, players $a_{i}$ and $b_{i}$ belong to different teams.

All values of $t_{i}$ are distinct and given in increasing order.

Output. Print two integers — the total score of team "Pineapple" and the total score of team "Blueberry".

Examples. In the first example, at seconds $10$ and $20$ , player $1$ shoots players $6$ and $7$ from the opposite team.

For each shot, team "Pineapple" earns $100$ points, and since the second shot was made within $10$ seconds, the team receives an additional $50$ points. In total: $250 = 2 \cdot 100 + 50$ . Team "Blueberry" made only one shot at the opponents and scored $100$ points.

In the second example, player $2$ made two consecutive double shots, so team "Pineapple" earned a total of $3 \cdot 100 + 2 \cdot 50 = 400$ points.

Open problem

For each of the $8$ players, we will store information about the time of their last shot. For example, in the array $p re v T im e [i]$ , we will record the moment in time (in seconds) when player $i$ made their last shot.

Next, we process all $n$ shots sequentially. Let the current shot be represented by a triple $(t, a, b)$ . Then:

when player $a$ makes a shot, their team receives $100$ points;
if player $a$ performs a double shot (that is, if the condition $t - p re v T im e [a] \leq 10$ holds), their team receives an additional $50$ points;
after that, we update the value of $p re v T im e [a] = t$ , since player $a$ made their most recent shot at time $t$ .

Example

In the first example, at the $10$ th and $20$ th seconds, player $1$ shoots players $6$ and $7$ from the opposing team. For each shot, team "Pineapple" earns $100$ points. Since both shots were made within a $10$ -second interval, the team receives an additional $50$ points. Total: $250 = 2 \times 100 + 50$ . Team "Blueberry" made only one shot at an opponent and scored $100$ points.

In the second example, player $2$ made two consecutive double shots, so team "Pineapple" earned a total of $3 \times 100 + 2 \times 50 = 400$ points.

In $p re v T im e [i]$ , we'll store the time (in seconds) when player $i$ made their last shot.

int prevTime[10];

Read the number of shots $n$ .

scanf("%d", &n);

For each player, the initial value of the last shot time is set to $- \infty$ .

for (i = 1; i < 10; i++)
  prevTime[i] = -10000;

Store the scores of teams "Pineapple" and "Blueberry" in the variables $p a$ and $p b$ , respectively.

pa = pb = 0;

Process all $n$ shots.

while (n--)
{

Player $a$ makes a shot at player $b$ at time $t$ .

  scanf("%d %d %d", &t, &a, &b);

The team to which player $a$ belongs receives $100$ points.

  if (a < b) pa += 100;
  else pb += 100;

If player $a$ makes a shot within $10$ seconds after their previous one, their team earns an additional $50$ points.

  if (t - prevTime[a] <= 10)
    if (a < b) pa += 50;
    else pb += 50;

After that, update the information that player $a$ made a shot at time $t$ .

  prevTime[a] = t;
}

Print the answer.

printf("%d %d\n", pa, pb);

At school, Aziz was assigned to write an essay. The deadline was approaching, and Aziz still hadn't written anything. However, he remembered that his friend Barış had already completed the same assignment last year and decided to use it to his advantage.

Aziz didn't want the plagiarism detection system to identify the borrowing, so he came up with a trick: reversing the words in all the sentences of Barış's essay. After this, Aziz decided to calculate the difference between the original sentence and the one he created.

Barış's essay consists of $t$ sentences. Each sentence includes unique words. If the number of words in a sentence is denoted as $n$ , the original sentence can be represented as the sequence ${1, 2, ..., n}$ . Aziz's version of the sentence will then be represented as the sequence ${n, n - 1, ..., 1}$ .

The difference between the original sentence and Aziz's version is calculated as the sum of the absolute differences between the positions of each word in Barış's sentence and the positions of the same word in Aziz's sentence.

For example, if a sentence consists of three words and Barış's sentence is represented as ${1, 2, 3}$ , Aziz's sentence will be ${3, 2, 1}$ . In this case, the difference between the sentences will be:

∣1 - 3∣ + ∣2 - 2∣ + ∣3 - 1∣ = 4

Input. The first line contains one integer $t (1 \leq t \leq 1 0^{5})$ — the number of sentences in Barış's essay. Each of the following $t$ lines contains one integer $n_{i} (1 \leq n_{i} \leq 1 0^{9})$ — the number of words in the $i$ -th sentence.

Output. For each sentence, print the difference between Barış's and Aziz's sentences on a separate line.

Open problem

Let's find a formula for solving the problem based on the number of words $n$ in a sentence.

Let $n$ be an even number. Let us consider Barış's and Aziz's sentences:

Let's compute the sum of the numbers in the "difference" array. Split the numbers in the array into two equal parts. Find the sum of the numbers from $1$ to $n - 1$ with a step of $2$ (this is an arithmetic progression). There are $n /2$ numbers in this range. Therefore, the sum of all the numbers in the "difference" array is:

2 \cdot \frac{1 + n - 1}{2} \cdot \frac{n}{2} = \frac{n ^{2}}{2}

Let $n$ be an odd number. Let us consider Barış's and Aziz's sentences:

Let's compute the sum of the numbers in the "difference" array. Split the numbers in the array into two equal parts. Find the sum of the numbers from $2$ to $n - 1$ with a step of $2$ (this is an arithmetic progression). There are $(n - 1) /2$ numbers in this range. Therefore, the sum of all the numbers in the "difference" array is:

2 \cdot \frac{2 + n - 1}{2} \cdot \frac{n - 1}{2} = \frac{( n + 1 ) \cdot ( n - 1 )}{2} = \frac{n ^{2} - 1}{2}

Example

Let $n = 8$ .

The sum of the numbers in the "difference" array is $8^{2} /2 = 32$ .

Let $n = 7$ .

The sum of the numbers in the "difference" array is $(7^{2} - 1) /2 = 24$ .

Bessie is working on an essay for her writing class. Since her handwriting leaves much to be desired, she decides to type the essay using a word processor.

The essay consists of $n$ words separated by spaces. Each word has a length between $1$ and $15$ characters inclusive and contains only lowercase or uppercase Latin letters. According to the assignment instructions, the essay must be formatted in a very specific way: each line must contain at most $k$ characters, excluding spaces. Fortunately, Bessie's word processor can enforce this requirement in the following manner:

If, when adding the next word, it fits on the current line, the word is appended to that line.
Otherwise, the word is moved to the next line, and filling continues there.

Naturally, any two consecutive words on the same line must be separated by exactly one space. No line may end with a space.

Unfortunately, Bessie's word processor has just broken. Help her format the essay according to the rules described above.

Input. The first line contains two integers $n (1 \leq n \leq 100)$ and $k (1 \leq k \leq 80)$ . The second line contains $n$ words. No word exceeds $k$ characters, which is the maximum allowed number of non-space characters in a single line.

Output. Print Bessie's essay, formatted properly.

Note. Including the words " $h e ll o$ " and " $m y$ ", the first line contains $7$ non-space characters. Adding the word " $nam e$ " would increase this number to $11 > 7$ , so the word is moved to a new line.

Open problem

Little Vasya is playing a game called "Dwarf Tower". In this game, there are $n$ different items that can be equipped on a character — a dwarf. All items are numbered from $1$ to $n$ . Vasya wants to obtain item number $1$ .

There are two ways to obtain items:

Buy an item: the $i$ -th item costs $c_{i}$ coins.
Craft an item: there are $m$ different crafting recipes in the game. To craft a new item, you need to give two other distinct items.

Help Vasya spend as little money as possible to get item number $1$ .

Input. The first line contains two integers $n$ and $m (1 \leq n \leq 1 0^{4}, 0 \leq m \leq 1 0^{5})$ — the number of different items and the number of crafting recipes.

The second line contains $n$ integers $c_{i} (0 \leq c_{i} \leq 1 0^{9})$ — the costs of the items.

Each of the following $m$ lines describes a recipe. Each line contains three distinct integers $a_{i}, x_{i}, y_{i}$ , where $a_{i}$ is the item that can be crafted from items $x_{i}$ and $y_{i} (1 \leq a_{i}, x_{i}, y_{i} \leq n, a_{i} \neq = x_{i}, x_{i} \neq = y_{i}, y_{i} \neq = a_{i})$ .

Output. Print one integer — the minimum amount of money that needs to be spent.

Open problem

Build a graph in the form of an adjacency list $g$ , where $g [i]$ contains pairs of numbers $(j, a)$ such that items $i$ and $j$ can be combined to produce item $a$ : $(i, j) \to a$ .

Let $cos t$ be an array initially containing the purchase costs of the items $(cos t [i] = c_{i})$ . By the end of the algorithm $cos t [i]$ will store the minimum amount of money required to obtain item $i$ .

Initially, all items are considered unprocessed $(u se d [i] = 0)$ .

While there is at least one unprocessed item:

Find the item $a$ with the smallest cost;
Apply all rules listed in $g [a]$ ;
Mark item $a$ as processed: $u se d [a] = 0$ ;

For each rule $(a, b) \to t o$ from $g [a]$ we recompute

cos t [t o] = min (cos t [t o], cos t [a] + cos t [b])

Example

Consider the first test. There are $5$ items with the following purchase costs:

There are three item crafting rules. Let's build an adjacency list based on them.

Item $2$ has the smallest cost: $cos t [2] = 0$ . Apply all rules involving item $2$ , namely those listed in $g [2]$ . After that, mark item $2$ as processed.

The next unprocessed item with the smallest cost is $3$ . Apply the rules listed in $g [3]$ . The costs of the items do not change in this step.

Next, the unprocessed item with the smallest cost becomes item $4$ . Apply the rule from $g [4]$ .

In the subsequent operations, the costs of the items do not change. Thus, the minimum cost to obtain item $1$ is $2$ .

Declare the arrays. Declare an adjacency list $g$ , which will contain the item crafting rules.

vector<int> cost, used;
vector<vector<pair<int, int>>> g;

Read the input data. Initialize the arrays.

scanf("%d %d", &n, &m);
g.resize(n + 1);
cost.resize(n + 1);
used.resize(n + 1);

Read the purchase costs of the items.

for (i = 1; i <= n; i++)
  scanf("%d", &cost[i]);

Read the item crafting rules and build an adjacency list based on them.

for (i = 0; i < m; i++)
{
  scanf("%d %d %d", &a, &x, &y);
  g[x].push_back(make_pair(y, a));
  g[y].push_back(make_pair(x, a));
}

Perform $n$ iterations.

for (k = 0; k < n; k++)
{

In each iteration, among the unprocessed items, find the one with the smallest cost. Let this be the item with number $a$ .

  mn = 2e9; a = -1;
  for (i = 1; i <= n; i++)
    if (!used[i] && cost[i] < mn)
    {
      mn = cost[i];
      a = i;
    }

Mark item $a$ as processed.

  used[a] = 1;

Iterate through all rules involving item $a$ .

      for (auto x : g[a])
      {
         b = x.first;
         to = x.second; // (a, b) -> to
         if (cost[a] + cost[b] < cost[to]) cost[to] = cost[a] + cost[b];
  }
}

Print the minimum amount of money required to purchase the first item.

printf("%d\n", cost[1]);

Lucy loves letters. At school, she learned the concept of lexicographical order and now enjoys playing with it.

At first, she tried to form the lexicographically smallest word from a given set of letters — it turned out to be quite easy! Then she decided to form several words and make one of them minimal in lexicographical order. This turned out to be much more difficult.

Formally, Lucy wants to construct $n$ words of length $l$ each from the given $n \cdot l$ letters such that the $k$ -th word in the lexicographically sorted list is as small as possible in lexicographical order.

Input. The first line contains three integers $n, l$ , and $k (1 \leq k \leq n \leq 1000, 1 \leq l \leq 1000)$ — the number of words, the length of each word, and the index of the word that Lucy wants to minimize.

The second line contains a string of $n \cdot l$ lowercase English letters.

Output. Print $n$ words of length $l$ each, one word per line, using all the letters from the input. The words must be sorted in lexicographical order, and the $k$ -th word must be as small as possible in lexicographical order. If there are multiple valid answers with the same minimal $k$ -th word, print any of them.

Open problem

In this problem, the task is to distribute the given $n \cdot l$ letters into $n$ words of length $l$ , sorted lexicographically, so that the $k$ -th word is as lexicographically small as possible.

The lexicographical order of words is determined character by character from left to right. Therefore, to minimize the $k$ -th word, one must place the smallest possible letters in its earliest positions (starting from the left), without violating the lexicographical order of all words.

This leads to the following greedy algorithm:

Sort all the letters of the input string in ascending order.
Construct a two-dimensional array of characters
$v [1.. n] [1.. l],$
where each row represents a separate word.
Fill the array column by column from left to right, since the columns correspond to positions in the words and determine their lexicographical order.

Filling the first column

In the first column, assign letters only to the rows with numbers from $1$ to $k$ , using the $k$ smallest available letters.
Place these letters from top to bottom to maintain the lexicographical order.
The rows numbered $k + 1, ..., n$ are not filled at this stage, as they do not affect the minimality of the $k$ -th word.

This way, we ensure that the first character of the $k$ -th word is minimal.

Filling the remaining columns

For each column $j = 2, 3, ..., l$ :

Among the rows $1, ..., k$ , find the smallest index $pt$ such that the rows $pt$ and $k$ match in all previous columns $1, ..., j - 1$ .
The set of rows $[pt, k]$ consists of all words that are indistinguishable from the $k$ -th word on the current prefix and therefore must remain no greater than it.
In column $j$ , assign the smallest available letters only to the rows from $pt$ to $k$ , from top to bottom.
4. Repeat this process until all $l$ characters of the $k$ -th word are fixed.

Filling the remaining cells

After the $k$ -th word has been fully constructed:

All remaining letters can be distributed arbitrarily, as long as the lexicographical order is not violated.
• For example, the remaining letters can be filled into the array sequentially, row by row from top to bottom and left to right, in sorted order.

Correctness

In each column, we minimize the current character of the $k$ -th word.
We assign identical or non-decreasing letters to all words that match the $k$ -th word on the current prefix, so the order of the words is preserved.
Once the $k$ -th word is fully constructed, no further actions can make it larger.

Therefore, the resulting $k$ -th word is lexicographically minimal.

Example

Let's consider the following test:

6 3 6
fgahhfgaaebdcbbebc

Here, we need to construct $6$ words of length $3$ , using all the letters, so that the $6$ th word in the lexicographically sorted list is minimal.

Sort the letters of the input string:

aaabbbb cc d ee ff gg hh

There are $18 = 6 \cdot 3$ letters in total, which corresponds to a $6 \times 3$ table.

Column 1. Fill the first column with letters from top to bottom, from the first to the sixth row, since the sixth row is the one we are interested in.

Column 2. Now consider the rows whose prefix matches the prefix of the $6$ th row. The prefix of the $6$ th row after the first column is " $b$ ". The matching rows are $4, 5$ , and $6$ . The smallest index among them is $pt = 4$ .

In the second column, assign the smallest available letters to the rows numbered from $4$ to $6$ .

Column 3. Again, we look for the rows whose prefix matches " $b c$ " (after filling the first two columns). The matching rows are $5$ and $6$ . The smallest index among them is $pt = 5$ . Assign the smallest available letters to the rows numbered from $5$ to $6$ . Now the $6$ th word is fully constructed and equals " $b c d$ ".

Filling the remaining letters

After the $6$ th word has been fixed, the remaining letters can be distributed in any valid way. For example, we can fill the table row by row from top to bottom and left to right with the remaining letters in lexicographical order.

Let's consider the first test case:

3 2 2
abcdef

Sort the letters of the input string:

ab c d e f

We need to fill a matrix of $3$ words, each of length $2$ , lexicographically minimizing the $2$ nd word.

First, fill the first column with letters from top to bottom, only for the rows from $1$ to $2$ , since these are the ones that affect the minimality of the $2$ nd word.

Next, move to the second column. It should be filled starting from the earliest row whose prefix matches the prefix of the $2$ nd row. In this case, that row is the $2$ nd row itself, so $pt = 2$ . Fill the second column with letters from row $pt$ to row $2$ .

After that, distribute the remaining letters in lexicographical order, row by row from top to bottom and left to right, which completes the construction of a valid answer.

Read the input data.

cin >> n >> l >> k;
cin >> s;

Sort the letters of the input string. Let the current letter being processed be $s [p os]$ .

pos = 0;
sort(s.begin(), s.end());

Declare the result matrix $v$ , consisting of $n$ rows and $l$ columns, where each row corresponds to a word of length $l$ .

vector<string> v(n, string(l, ' '));

We'll distribute the letters in column $j$ , filling the rows from $pt$ to $k - 1$ inclusive (row numbering starts from zero).

int pt = 0;
for (j = 0; j < l; j++)
{
  for (i = pt; i < k; i++)
    v[i][j] = s[pos++];

Move the pointer $pt$ forward $(pt + +)$ until the $j$ -th character of the $(k - 1)$ -th row matches the $j$ -th character of row $pt$ . As a result, $pt$ points to the row with the smallest index that currently matches the prefix of the $(k - 1)$ -th row.

  while (v[pt][j] != v[k - 1][j]) pt++;
}

After that, fill the remaining cells of the matrix. To do this, go through the rows from top to bottom and the columns from left to right, distributing the remaining letters.

for (i = 0; i < n; i++)
for (j = 0; j < l; j++)
  if (v[i][j] == ' ') v[i][j] = s[pos++];

Print the answer.

for (i = 0; i < n; i++)
  cout << v[i] << endl;

A kid goat works as a controller on a ferry. His task is to ensure that the ferry does not sink from excessive weight. Today, only two tickets remain for the boat, and the ferry can carry at most $k$ additional kilograms.

In this forest, there is a single long road along which the animals live. Help the kid goat determine whether he can find two passengers within a specified segment of the forest.

Input. The first line contains two numbers $n$ $(2 \leq n \leq 1 0^{6})$ and $k$ $(1 \leq k \leq 1 0^{9})$ — the number of animals in the forest and the remaining capacity of the ferry, respectively.

The second line contains $n$ integers — the mass of each animal.

Then follows a number $m$ $(1 \leq m \leq 1 0^{5})$ — the number of queries.

Each of the next $m$ lines contains three integers $t$ , $l$ , and $r$ :

If $t = 1$ , then $1 \leq l < r \leq n$ . This means: check whether it is possible to choose two animals among those in the segment $[l, r]$ so that their total mass does not exceed $k$ .
If $t = 2$ , then $1 \leq l \leq n$ , $1 \leq r \leq 1 0^{9}$ . This means: update the mass of the animal with number $l$ to $r$ kilograms.

Output. For each query of type $1$ , print a line "Yes" if the kid goat can find two such passengers in the specified segment, and "No" otherwise.

Each query of type $2$ means that the mass of the animal with number $l$ is changed to $r$ kilograms.

Open problem

A segment tree can be built to maintain the two smallest values in each range. However, in this problem, we are not interested in the exact minimum values but rather in the existence of two numbers whose sum does not exceed $k$ .

The weights of the passengers are stored in the leaves of the segment tree. The internal nodes hold values according to the following rules:

If the sum of the two smallest values in the left and right subtrees does not exceed $k$ , then there exist two suitable passengers in the range $[l; r]$ . In this case, store $0$ in the node corresponding to the interval $[l; r]$ .
Otherwise, store the minimum value of its two child nodes.

Consider the processing of the queries.

If the minimum value in the range $[l; r]$ is $0$ , then there exist two passengers whose total weight meets the condition, so the answer is "Yes".
Otherwise, the answer is "No".

Example

Let's build a segment tree for $k = 9$ and passenger weights $7, 3, 8, 7, 6, 7$ .

Among the fundamental segments, only the node corresponding to $[1; 6]$ will contain $0$ .

Declare an array $S e g T ree$ to store the segment tree. The weights of the animals are stored in the array $a$ .

#define MAX 1000010
#define MAX_INT 1050000000
int SegTree[4*MAX];
int a[MAX];

The function f merges the values of the child nodes in the segment tree. The segment tree supports the minimum operation. However, if the sum of the values in the left and right child nodes does not exceed $k$ , return $0$ .

Additionally, if at least one of the child nodes already contains $0$ , this means that two suitable passengers exist in its range, so we also return $0$ .

int f(int a, int b)
{
  if (a == 0 || b == 0 || a + b <= k) return 0;
  return min(a,b);
}

The function BuildTree constructs the segment tree. It takes as input the index of the current node $v$ and the boundaries $lp os$ and $r p os$ corresponding to node $v$ . The function f is used to merge the values of the child nodes.

void BuildTree(int v, int lpos, int rpos)
{
  if (lpos == rpos)
    SegTree[v] = a[lpos];
  else
  {
    int mid = (lpos + rpos) / 2;
    BuildTree(2 * v, lpos, mid);
    BuildTree(2 * v + 1, mid + 1, rpos);
    SegTree[v] = f(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

The function Query processes a range query on $[l e f t; r i g h t]$ . The node $v$ corresponds to the segment $[lp os, r p os]$ .

If there exist two passengers in the range $[l e f t, r i g h t]$ whose total weight does not exceed $k$ , the function Query returns $0$ .
Otherwise, it returns the minimum passenger weight in the given range.

int Query(int v, int lpos, int rpos, int left, int right)
{
  if (left > right) return MAX_INT;
  if ((lpos == left) && (rpos == right)) return SegTree[v];
  int mid = (lpos + rpos) / 2;
  return f(Query(2 * v, lpos, mid, left, min(right, mid)),
          Query(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right));
}

The function Update updates the value of the element at index pos, assigning it $v a l$ . The node $v$ corresponds to the segment $[lp os, r p os]$ .

void Update(int v, int lpos, int rpos, int pos, int val)
{
  if (lpos == rpos)
    SegTree[v] = val;
  else
  {
    int mid = (lpos + rpos) / 2;
    if (pos <= mid) Update(2 * v, lpos, mid, pos, val);
    else Update(2 * v + 1, mid + 1, rpos, pos, val);
    SegTree[v] = f(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

The main part of the program. Read the weights of the animals into the array $a$ , starting from index $0$ .

scanf("%d %d",&n,&k);
for (i = 0; i < n; i++) scanf("%d",&a[i]);

Build a segment tree based on the elements of the array $a [0.. n - 1]$ .

BuildTree(1,0,n-1);

Process the queries sequentially.

scanf("%d",&q);
for (j = 0; j < q; j++)
{
  scanf("%d %d %d",&t,&l,&r);
  if (t == 1)
  {
    int Res = Query(1,0,n-1,l-1,r-1);
    if (Res == 0) printf("Yes\n"); else printf("No\n");
  } 
  else
    Update(1,0,n-1,l-1,r) ;
}

Open problem

Let $d p [l] [r] = f (l, r)$ be the minimum number of characters that need to be deleted from the substring $s_{l} ... s_{r}$ so that, by performing the allowed operations (removing two identical adjacent characters), we can obtain an empty string. Then:

$f (l, r) = 0$ , if $l > r$ ;
$f (l, l) = 1$ , since the single character must be deleted in advance;
$f (l, r) = f (l + 1, r - 1)$ , if $s [l] = s [r]$ . In this case, the inner part of the substring is deleted first, after which the boundary characters become adjacent and can be removed;

$f (l, r) = 1 + f (l + 1, r)$ , if the first character is deleted;
$f (l, r) = 1 + f (l, r - 1)$ , if the last character is deleted;

However, both of these cases can be conveniently generalized as follows: to solve the problem on the segment $[l; r]$ , split it into two subsegments $[l; i]$ and $[i + 1; r] (l \leq i < r)$ and choose the minimum value:

f (l, r) = l \leq i < r min (f (l, i) + f (i + 1, r))

For example:

deleting the first character is equivalent to choosing $i = l (f (l, l) = 1)$ ;
deleting the last character is equivalent to choosing $i = r - 1 (f (r, r) = 1)$ .

The answer to the problem will be $d p [0] [n - 1] = f (0, n - 1)$ , where $n$ is the length of the input string.

Example

Let’s consider the example given in the problem statement. We have:

f (0, 7) = f (0, 2) + f (3, 7) = 1 + 1 = 2

To prepare for the final stage of the European Code Challenge, the organizers need to send $n$ items to the event location. Each item has a known mass in grams, denoted by $m_{i}$ .

They decided to use the postal service "Superexpress" for shipping. This service accepts parcels, each of which may contain one or more items. The mass of a parcel is equal to the sum of the masses of all items placed inside it.

The cost of sending a parcel is $1$ euro per gram, except for parcels that fall under the special offer: if a parcel weighs exactly one kilogram, the shipping cost is $p$ euros.

The organizers want to send all items while spending as little money as possible. Help them distribute the items among parcels so as to minimize the total shipping cost.

Input. The first line contains two integers $n$ and $p (1 \leq n \leq 14, 1 \leq p \leq 1000)$ — the number of items and the special offer price for shipping a parcel.

The second line contains $n$ integers $m_{1}, m_{2}, \dots, m_{n} (1 \leq m_{i} \leq 1000$ for all $i$ from $1$ to $n$ ).

Output. Print one number — the minimum possible total cost of shipping all items (in euros).

Open problem

Let's introduce the notion of a mask that represents a subset of items to be shipped. For example, the mask $ma s k = 5 = 10 1_{2}$ specifies the subset containing the $0$ -th and $2$ -nd items (items are numbered from zero).

For each subset, we compute its total weight, which determines the shipping cost. If this weight is exactly $1000$ grams, then since $p \leq 1000$ , it is always beneficial to use the special offer.

Let $M in C os t [ma s k]$ denote the minimum cost (in euros) of shipping the subset of items represented by $ma s k$ . Then for any mask $x$ that is a subset of $ma s k$ , the following relation holds:

M in C os t [ma s k] = x \subset ma s k min (M in C os t [ma s k x or x] + M in C os t [x])

Since the mask $2^{n} - 1$ corresponds to the entire set of $n$ items, the answer to the problem will be the value $M in C os t [2^{n} - 1]$ .

Theorem. Enumerating all masks and all of their submasks takes $O (3^{n})$ time.

Proof 1. Consider the $i$ -th bit. There are three possible cases for it:

it is included in the mask $ma s k$ and included in the submask $s u b$ ;
it is included in the mask $ma s k$ but not included in the submask $s u b$ ;
it is included in neither the mask $ma s k$ nor the submask $s u b$ ;

There are $n$ bits in total, so the total number of different combinations is $3^{n}$ .

Proof 2. Let a mask $ma s k$ contain $k$ set bits. Then it has exactly $2^{k}$ submasks. The number of masks of length $n$ with exactly $k$ set bits is $C_{n}^{k}$ . Therefore, the total number of combinations is

k = 0 \sum n C_{n}^{k} 2^{k} = (1 + 2)^{n} = 3^{n}

We'll store the item weights in the array $m$ . In the cell $M in C os t [ma s k]$ , we'll store the minimum shipping cost for the subset of items represented by the mask $ma s k$ .

int m[15], MinCost[1 << 14];

Read the input data.

scanf("%d %d",&n,&p);
for (i = 0; i < n; i++) scanf("%d",&m[i]);

In the variable $ma s k$ , iterate over all possible masks from $0$ to $2^{n} - 1$ .

for (mask = 0; mask < (1 << n); mask++)
{

Store in the variable $C os t$ the total weight of the subset of items corresponding to the mask $ma s k$ . To do this, examine the binary representation of $ma s k$ : if the bit at position $i$ is $1$ , then add the weight of the $i$ -th item to $C os t$ .

  for (Cost = i = 0; i < n; i++)
    if (mask & (1 << i)) Cost += m[i];

If the value of $C os t$ is strictly equal to $1000$ , then since the problem states that $p \leq 1000$ , assign the value $p$ to $C os t$ .

  if (Cost == 1000) Cost = p;

Store the computed shipping cost in the corresponding cell of the $M in C os t$ array.

  MinCost[mask] = Cost;
}

For each mask $ma s k$ , iterate over all subsets $x \subset ma s k$ (the mask $x$ is a subset of $ma s k$ if and only if $ma s k A N D x$ equals $x$ ). If we subtract the set corresponding to $x$ from the set corresponding to $ma s k$ , we get the set with mask $ma s k XOR x$ .

For example, if $ma s k = 110 1_{2}$ and $x = 100 1_{2}$ , then $ma s k XOR x = 10 0_{2}$ , which corresponds to the set-theoretic operation ${1, 3, 4} ∖ {1, 4} = {3}$ .

for (mask = 0; mask < (1 << n); mask++)
  for (x = 0; x < mask; x++)

Recompute the value of $M in C os t [ma s k]$ according to the recurrence relation given in the problem analysis.

    if ((mask & x) == x) 
      MinCost[mask] = min(MinCost[mask],MinCost[mask^x] + MinCost[x]);

Print the answer, which is stored in the cell $M in C os t [2^{n} - 1]$ .

printf("%d\n",MinCost[(1 << n) - 1]);

Algorithm implementation with complexity O(3^n)

Declare the constant and the arrays.

#define MAX 0xFFFFFFFF
unsigned int m[15], MinCost[1 << 14];

For a mask $ma s k$ , it is necessary to iterate over all its submasks $s u b$ and find the minimum among all possible values

F in d C os t (s u b) + F in d C os t (ma s k XOR s u b)

Due to the symmetry of this sum, it is sufficient to consider only those submasks $s u b$ for which the condition $s u b \geq ma s k XOR s u b$ holds.

unsigned int FindCost(int mask)
{
  if (MinCost[mask] != MAX) return MinCost[mask];
  // sub перебирает все подмаски маски mask
  for (int sub = (mask - 1) & mask; 
           sub >= mask ^ sub; sub = (sub - 1) & mask)
    MinCost[mask] = 
            min(MinCost[mask], FindCost(sub) + FindCost(mask ^ sub));
  return MinCost[mask];
}

The main part of the program. Set $M in C os t [ma s k] = - 1$ for all masks whose shipping cost for the corresponding set of items has not yet been computed.

memset(MinCost,0xFF,sizeof(MinCost));

Read the input data.

scanf("%d %d",&n,&p);
for(i = 0; i < n; i++) scanf("%d",&m[i]);

If the cost of a certain subset of items does not exceed $1000$ (specifically, not more, not less, since the case $p = 1000$ is possible), then the special offer cannot be applied to their shipment. For such subsets, $M in C os t [ma s k]$ can be immediately computed as the sum of the costs of all items. If the sum of item costs is exactly $1000$ , then we assign $M in C os t [ma s k] = p$ .

Thus, we preliminarily fill in the known minimum costs for small subsets. This increases the efficiency of the program.

for (mask = 0; mask < (1 << n); mask++)
{
  for(Cost = i = 0; i < n; i++)
    if (mask & (1 << i)) Cost += m[i];
  if (Cost == 1000) Cost = p;
  if (Cost <= 1000) MinCost[mask] = Cost;
}

Print the answer. The entire set of items is represented by the mask $2^{n} - 1$ , whose binary representation consists of $n$ ones.

printf("%u\n",FindCost((1 << n) - 1));

Robots are becoming increasingly popular over time. Today, they are used not only in large factories, but also in everyday household settings. One programmer, together with his friends, decided to create their own home robot. As you may know, many programmers enjoy getting together at parties and drinking beer. After such parties, the table is usually left covered with empty bottles. Therefore, they decided to develop a robot capable of collecting empty bottles from the table.

The table is a rectangle of length $l$ and width $w$ . The robot starts at the point $(x_{r}, y_{r})$ , and $n$ bottles are located at the points $(x_{i}, y_{i})$ , where $1 \leq i \leq n$ . To pick up a bottle, the robot must move to its location, grab it, and then carry it to some point on the boundary of the table and release it. At any moment, the robot can hold only one bottle, and it may release it only at the boundary of the table.

The sizes of the bottles and the robot can be considered negligible (both the robot and the bottles are points). A robot holding a bottle may pass through points where other bottles are located.

One of the robot’s subprograms is route planning. You are required to write a program that determines the shortest possible route by which the robot can collect all the bottles.

Input. The first line contains two integers $w$ and $l (2 \leq w, l \leq 1000)$ — the width and length of the table.

The second line contains the number of bottles $n (1 \leq n \leq 18)$ . Each of the next $n$ lines contains two integers $x_{i}$ and $y_{i} (0 < x_{i} < w, 0 < y_{i} < l)$ — the coordinates of the $i$ -th bottle. No two bottles are located at the same point.

The last line contains two integers $x_{r}$ and $y_{r} (0 < x_{r} < w, 0 < y_{r} < l)$ — the coordinates of the robot's starting position. The robot is not located at the same point as any bottle.

Output. Print the length of the shortest route by which the robot collects all bottles. The computation error must not exceed $1 0^{- 6}$ .

Open problem

Let $A$ and $B$ be two bottles that the robot will pick up sequentially. After the robot picks up bottle $A$ , it must carry it to one of the four edges of the table and dispose of it. Only then may the robot proceed to bottle $B$ . We need to find the shortest path for the robot from point $A (x_{i}, y_{i})$ to point $B (x_{j}, y_{j})$ , with a mandatory visit to the table's edge.

The distance $A K + K B = A K + K P = A P$ . Knowing the coordinates of points $A (x_{i}, y_{i})$ and $P (x_{j}, - y_{j})$ , we can compute this distance:

A P = (x_{j} - x_{i})^{2} + (- y_{j} - y_{i})^{2} = (x_{j} - x_{i})^{2} + (y_{j} + y_{i})^{2}

The distance $A L + L B = A L + L Q = A Q$ . The $x$ -coordinate of point $Q$ equals $w + (w - x_{j}) = 2 w - x_{j}$ . Knowing the coordinates of points $A (x_{i}, y_{i})$ and $Q (2 w - x_{j}, y_{j})$ , we can compute this distance:

A Q = (2 w - x_{j} - x_{i})^{2} + (y_{j} - y_{i})^{2}

The distance $A E + EB = A E + ET = A T$ . Knowing the coordinates of points $A (x_{i}, y_{i})$ and $T (- x_{j}, y_{j})$ , we can compute this distance:

A T = (- x_{j} - x_{i})^{2} + (y_{j} - y_{i})^{2} = (x_{j} + x_{i})^{2} + (y_{j} - y_{i})^{2}

The distance $A D + D B = A D + D S = A S$ . The $y$ -coordinate of point $S$ equals $l + (l - y_{j}) = 2 l - y_{j}$ . Knowing the coordinates of points $A (x_{i}, y_{i})$ and $S (x_{j}, 2 l - y_{j})$ , we can compute this distance:

A S = (x_{j} - x_{i})^{2} + (2 l - y_{j} - y_{i})^{2}

Let us find the minimum distance the robot must travel to throw away the bottle located at point $(x_{i}, y_{i})$ over the edge of the table. This distance is equal to the minimum of the four values:

min (x_{i}, y_{i}, w - x_{i}, l - y_{i})

This is exactly the path the robot will have to take to dispose of the last bottle.

The initial position of the robot and the coordinates of all bottles are given. Consider a graph where vertex $0$ corresponds to the robot’s starting position, and the remaining vertices correspond to the bottles. The distance between vertex 0 and any other vertex is defined as the Euclidean distance between the corresponding points. The distance between bottles $i$ and $j$ is defined as the minimum path the robot must travel from bottle $i$ to bottle $j$ , with the requirement that it must touch the edge of the table. Since there are $n$ bottles on the table, the graph will contain $n + 1$ vertices.

Next, we need to find a Hamiltonian path of minimum length in this graph. After the robot reaches the last bottle, we must add the distance required to throw this bottle off the edge of the table to the total path length. The Hamiltonian path is computed using dynamic programming over subsets, with a time complexity of $O (n^{2} \cdot 2^{n})$ .

Example

Below are the robot's initial position and the coordinates of the bottles.

The length of the robot's shortest path is

1 + 3^{2} + 2^{2} + 1 = 2 + 13 \approx 5.605

Let's define the constant $I NF$ to represent infinity, and the constant $M A X$ as the maximum number of points in the Hamiltonian path.

#define INF 1e18
#define MAX 20

Declare an array $d p$ that will store the values $d p (S, i)$ , which are computed dynamically. The coordinates of the bottles are stored as points $(x_{i}, y_{i}) (1 \leq i \leq n)$ . The robot's initial position is stored at the point $(x_{0}, y_{0})$ .

double dp[1 << MAX][MAX + 1];
double x[MAX], y[MAX], m[MAX][MAX];

The function solve computes the value $d p (S, l a s t)$ — the minimum distance required to visit all points in the set $S$ , finishing at the vertex $l a s t$ . The set $S$ is encoded by an integer $ma s k$ . Then:

d p (S, l a s t) = i \in S ∖ l a s t min (d p (S ∖ l a s t, i) + m [i] [l a s t]),

where

$m [i] [l a s t]$ is the distance between points $i$ and $l a s t$ ,
$S ∖ l a s t = ma s k ˆ (1 << l a s t)$ is the set $S$ without the element $l a s t$ .

The variable $res$ corresponds to the cell $d p [ma s k] [l a s t]$ , so when $res$ is updated, the value of $d p [ma s k] [l a s t]$ is automatically updated as well.

double solve(int mask, int last)
{
  double &res = dp[mask][last];
  if (res == INF)
  {
    mask ^= (1 << last);
    for (int i = 1; i < n; i++)
      if ((mask & (1 << i)) && (i != last)) 
        res = min(res, solve(mask, i) + m[i][last]);
  }
  return res;
}

The function f returns the shortest distance from the point $(x [i], y [i])$ to the edge of the table.

double f(int i)
{
  return min(min(x[i], y[i]), min(l - y[i], w - x[i]));
}

The function dist returns the distance between the points $(x [i], y [i])$ and $(x [j], y [j])$ .

double dist(int i, int j)
{
  return sqrt((x[i] - x[j])*(x[i] - x[j]) + 
              (y[i] - y[j])*(y[i] - y[j]));
}

The main part of the program. Read the table dimensions $w$ and $l$ .

scanf("%d %d", &w, &l);

Read the number of bottles $n$ and their coordinates $(x [i], y [i])$ .

scanf("%d", &n);
for (i = 1; i <= n; i++)
  scanf("%lf %lf", &x[i], &y[i]);

The robot’s initial coordinates are stored in $(x [0], y [0])$ .

scanf("%lf %lf", &x[0], &y[0]);

We add a zero vertex to the $n$ bottles, corresponding to the robot's initial position. After that, $n$ is increased by one and becomes the total number of vertices in the graph. The graph vertices are numbered $0, 1, ..., n - 1$ .

n++;

Let's compute all pairwise distances between the bottles. The distance between bottles $i$ and $j$ is defined as the minimum path the robot must travel from bottle $i$ to bottle $j$ , with the requirement that it must touch the edge of the table.

for (i = 1; i < n - 1; i++)
for (j = i + 1; j < n; j++)
  m[i][j] = m[j][i] =
    min(
 	min(sqrt((x[i] + x[j])*(x[i] + x[j]) + (y[i] - y[j])*(y[i] - y[j])),
     sqrt((2 * w - x[i] - x[j])*(2 * w - x[i] - x[j]) + 
          (y[i] - y[j])*(y[i] - y[j]))),
 min(sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] + y[j])*(y[i] + y[j])),
     sqrt((x[i] - x[j])*(x[i] - x[j]) + 
          (2 * l - y[i] - y[j])*(2 * l - y[i] - y[j])))
       );

Initially, the values of $d p (S, i)$ are unknown, so we assign them positive infinity.

for (i = 0; i < 1 << n; i++)
for (j = 0; j < n; j++)
  dp[i][j] = INF;

The set ${0}$ corresponds to the mask $1$ . Set $d p ({0}, 0) = 0$ , since the minimum path from the zero vertex to itself without visiting other vertices is zero. The variable $t o t a l$ will store the required minimum length of the Hamiltonian path.

dp[1][0] = 0; total = INF;
for (i = 1; i < n; i++) dp[1 | (1 << i)][i] = dist(0, i);

Find the Hamiltonian path of minimum length. The value $2 n - 1$ corresponds to the set of all vertices ${0, 1, 2, ..., n - 1}$ . Compute the minimum among all values:

d p ({0, 1, 2, ..., n - 1}, i) + f (i), 1 \leq i < n

After obtaining the minimum length of the Hamiltonian path, we must add the distance the robot needs to travel to throw the final bottle $i$ off the edge of the table — this distance is $f (i)$ .

for (i = 1; i < n; i++)
  total = min(total, solve((1 << n) - 1, i) + f(i));

Print the required minimum path length.

printf("%.6lf\n", total);

Şərhlər

Hələ də heç nə

Söhbəti başladan ilk siz olun!

Daxil ol

Yüklənir

Bir an, serverdən məlumat alınır