10 місяців тому

Educational Round #6 — Editorial

Eolymp #10836. Summer

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)$ n~(1 \le n \le 100) — the number of shots made during the game.

Each of the next $n$ lines contains three integers $t_{i}$ t_i, $a_{i}$ a_i, $b_{i} (0 \leq t_{i} \leq 1000, 1 \leq a_{i}, b_{i} \leq 8)$ b_i~(0 \le t_i \le 1000,~1 \le a_i, b_i \le 8), meaning that player $a_{i}$ a_i shot player $b_{i}$ b_i at time $t_{i}$ 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}$ a_i and $b_{i}$ b_i belong to different teams.

All values of $t_{i}$ 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$ 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$ 3 \cdot 100 + 2 \cdot 50 = 400 points.

Open problem

In $p r e v T im e [i]$ prevTime[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);

Eolymp #10452. The essay

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}$ \{1, 2,..., n\}. Aziz's version of the sentence will then be represented as the sequence ${n, n - 1, ..., 1}$ \{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}$ \{1, 2, 3\}, Aziz's sentence will be ${3, 2, 1}$ \{3, 2, 1\}. In this case, the difference between the sentences will be:

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

|1 − 3| + |2 − 2| + |3 − 1| = 4

Input. The first line contains one integer $t (1 \leq t \leq 1 0^{5})$ t~(1 \le t \le 10^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})$ n_i~(1 \le n_i \le 10^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

Read the number of test cases $t es t s$ .

scanf("%d", &tests);
while (tests--)
{

For each value of $n$ , compute and print the result.

  scanf("%d", &n);
  if (n % 2 == 0)
    res = n * n / 2;
  else
    res = (n * n - 1) / 2;
  printf("%lld\n", res);
}

C++

Eolymp #9596. Word Processor

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)$ n~(1 \le n \le 100) and $k (1 \leq k \leq 80)$ k~(1 \le k \le 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 l l o$ " and " $m y$ ", the first line contains $7$ non-space characters. Adding the word " $nam e$ " would increase this number to $11 > 7$ 11 > 7, so the word is moved to a new line.

Open problem

Read the input data.

cin >> n >> k;

The variable $pt r$ stores the current length of the output string.

ptr = 0;

Read the $n$ words sequentially.

while (n--)
{

Read the current word $s$ and find its length $l e n$ .

  cin >> s;
  len = s.size();

If $pt r + l e n \leq k$ ptr + len \le k, then the word $s$ can be printed on the current line. The length of the output string will not exceed $k$ characters.

  if (ptr + len <= k)
  {
    ptr += len;
    cout << s << " ";
  }

Otherwise, the word $s$ should be printed on a new line. Set the value of $pt r$ for the new line to $l e n$ .

  else
  {
    ptr = len;
    cout << endl << s << " ";
  }
}

Eolymp #6263. Dwarf Tower

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}$ 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})$ m~(1 \le n \le 10^4, 0 \le m \le 10^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})$ c_i~(0 \le c_i \le 10^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}$ a_i, x_i, y_i, where $a_{i}$ a_i is the item that can be crafted from items $x_{i}$ 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})$ y_i~(1 \le a_i, x_i, y_i \le n, a_i \ne x_i, x_i \ne y_i, y_i \ne a_i).

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

Open problem

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;
    }

C++

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];
  }
}

C++

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

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

Eolymp #9591. Lexicography

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$ 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)$ k~(1 \le k \le n \le 1000, 1 \le l \le 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$ 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$ 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],$
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$ 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$ j = 2, 3, ..., l:

Among the rows $1, ..., k$ 1, ..., k, find the smallest index $pt$ such that the rows $pt$ and $k$ match in all previous columns $1, ..., j - 1$ 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 f f g g hh

aaabbbbccdeeffgghh

There are $18 = 6 \cdot 3$ 18 = 6 \cdot 3 letters in total, which corresponds to a $6 \times 3$ 6 × 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$ 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$ 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$ 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$ 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 + +)$ (pt++) until the $j$ -th character of the $(k - 1)$ (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)$ (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;

Eolymp #4483. The kid who learned to count

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})$ (2 \le n \le 10^6) and $k$ $(1 \leq k \leq 1 0^{9})$ (1 \le k \le 10^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})$ (1 \le m \le 10^5) — the number of queries.

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

If $t = 1$ t = 1, then $1 \leq l < r \leq n$ 1 \le l < r \le n. This means: check whether it is possible to choose two animals among those in the segment $[l, r]$ [l, r] so that their total mass does not exceed $k$ .
If $t = 2$ t = 2, then $1 \leq l \leq n$ 1 \le l \le n, $1 \leq r \leq 1 0^{9}$ 1 \le r \le 10^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

Declare an array $S e g T r ee$ SegTree 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 $l p 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]);
  }
}

C++

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

If there exist two passengers in the range $[l e f t, r i g h t]$ [left, right] 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));
}

C++

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

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]);
  }
}

C++

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]$ 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) ;
}

C++

Open problem

Let's declare the constants and the array.

#define MAX 101
#define INF 0x3F3F3F3F
int dp[MAX][MAX];

The function f solves the problem on the segment $[l; r]$ [l; r].

int f(int l, int r) 
{

First, consider the base cases.

  if (l > r) return 0;
  if (l == r) return 1;

If the value $d p [l] [r]$ dp[l][r] is already computed, return it.

  if (dp[l][r] != INF) return dp[l][r];

If the characters $s [l]$ and $s [r]$ are equal, they do not need to be removed in advance. First, we clear the middle part of the segment; after that, these characters become adjacent and can be removed for free.

  int &res = dp[l][r];
  if (s[l] == s[r]) 
    res = min(res, f(l + 1, r - 1));

Consider splitting the segment $[l; r]$ [l; r] into two parts: $[l; i]$ and $[i + 1; r]$ [i + 1; r]. Solve the problem independently for each subsegment and take the minimum result.

  for (int i = l; i < r; i++)
    res = min(res, f(l, i) + f(i + 1, r));

Finally, return the computed value.

  return res;
}

The main part of the program. Read the input string.

cin >> s;
memset(dp,0x3F,sizeof(dp));

Compute and print the result $f (0, n - 1)$ f(0, n - 1), where $n$ is the length of the string $s$ .

printf("%d\n",f(0, s.size() - 1));

Eolymp #2509. The post office

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}$ 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)$ p~(1 \le n \le 14, 1 \le p \le 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$ m_1, m_2, \ldots, m_n~(1 \le m_i \le 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

We'll store the item weights in the array $m$ . In the cell $M in C os t [ma s k]$ MinCost[mask], 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$ 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$ p \le 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$ x \sub mask (the mask $x$ is a subset of $ma s k$ if and only if $ma s k A N D x$ mask~AND~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 X O R x$ mask~XOR~x.

For example, if $ma s k = 110 1_{2}$ mask = 1101_2 and $x = 100 1_{2}$ x = 1001_2, then $ma s k X O R x = 10 0_{2}$ mask~XOR~x = 100_2, which corresponds to the set-theoretic operation ${1, 3, 4} ∖ {1, 4} = {3}$ \{1, 3, 4\} \setminus \{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]$ MinCost[mask] 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]$ MinCost[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 X O R s u b)

FindCost(sub) + FindCost(mask~XOR~sub)

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 X O R s u b$ sub \ge mask~XOR~sub 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];
}

C++

The main part of the program. Set $M in C os t [ma s k] = - 1$ MinCost[mask] = -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$ 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]$ MinCost[mask] 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$ MinCost[mask] = 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;
}

C++

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

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

Eolymp #2268. Kitchen Robot

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})$ (x_r, y_r), and $n$ bottles are located at the points $(x_{i}, y_{i})$ (x_i, y_i), where $1 \leq i \leq n$ 1 \le i \le 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)$ l~(2 \le w, l \le 1000) — the width and length of the table.

The second line contains the number of bottles $n (1 \leq n \leq 18)$ n~(1 \le n \le 18). Each of the next $n$ lines contains two integers $x_{i}$ x_i and $y_{i} (0 < x_{i} < w, 0 < y_{i} < l)$ 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}$ x_r and $y_{r} (0 < x_{r} < w, 0 < y_{r} < l)$ 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}$ 10^{-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})$ A(x_i, y_i) to point $B (x_{j}, y_{j})$ 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$ AK + KB = AK + KP = AP. Knowing the coordinates of points $A (x_{i}, y_{i})$ A(x_i, y_i) and $P (x_{j}, - y_{j})$ 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}

AP = \sqrt{(x_j - x_i)^2 + (-y_j - y_i)^2} = \sqrt{(x_j - x_i)^2 + (y_j + y_i)^2}

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

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

AQ = \sqrt{(2w - x_j - x_i)^2 + (y_j - y_i)^2}

The distance $A E + E B = A E + E T = A T$ AE + EB = AE + ET = AT. Knowing the coordinates of points $A (x_{i}, y_{i})$ A(x_i, y_i) and $T (- x_{j}, y_{j})$ 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}

AT = \sqrt{(-x_j - x_i)^2 + (y_j - y_i)^2} = \sqrt{(x_j + x_i)^2 + (y_j - y_i)^2}

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

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

AS = \sqrt{(x_j - x_i)^2 + (2l - 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})$ (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})

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$ 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})$ 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

1 + \sqrt{3^2 + 2^2} + 1 = 2 + \sqrt{13} ≈ 5.605

Let's define the constant $I N F$ 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)$ dp(S, i), which are computed dynamically. The coordinates of the bottles are stored as points $(x_{i}, y_{i}) (1 \leq i \leq n)$ (x_i, y_i)~(1 \le i \le n). The robot's initial position is stored at the point $(x_{0}, y_{0})$ (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)$ dp(S, last) — 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]),

dp(S, last) = \min_{i \in S \setminus {last}}⁡(dp(S \setminus {last},i) + m[i][last]),

where

$m [i] [l a s t]$ m[i][last] is the distance between points $i$ and $l a s t$ ,
$S ∖ l a s t = ma s k ˆ (1 << l a s t)$ S\setminus {last} = mask~\^{}~(1<< last) is the set $S$ without the element $l a s t$ .

The variable $r es$ corresponds to the cell $d p [ma s k] [l a s t]$ dp[mask][last], so when $r es$ is updated, the value of $d p [ma s k] [l a s t]$ dp[mask][last] 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;
}

C++

The function f returns the shortest distance from the point $(x [i], y [i])$ (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])$ (x[i], y[i]) and $(x [j], y [j])$ (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])$ (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])$ (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$ 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])))
       );

C++

Initially, the values of $d p (S, i)$ dp(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$ dp(\{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$ 2n - 1 corresponds to the set of all vertices ${0, 1, 2, ..., n - 1}$ \{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

dp(\{0, 1, 2, ..., n - 1\}, i) + f(i), 1 \le 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);

Educational Round #6 — Editorial

Коментарі