Parsing qualifying rounds Technocup
On March 23 and 26, online, on the IT.Mail.Ru platform together with Codeforces , two qualifying rounds of the Technocup-2016 Programming Olympiad for pupils of 8–11th grades were held. More than one and a half thousand participants from all over Russia and the CIS fought for the opportunity to meet at the Moscow site. The top 300 reached the final, which will be held on April 17 at the Moscow State Technical University. N. E. Bauman and MIPT.
In April, they will have the opportunity to once again prove themselves and compete for attractive prizes: iPad mini 2, iPod nano, iPod shuffle. In addition to mundane material awards, as well as indispensable honor and respect, the winners of the first Tekhnokubka (diploma of I degree) will receive as many as eight additional points for admission to undergraduate and specialist programs at MIPT and MGTU. N. E. Bauman, and the winners (diploma II and III degree) - six additional points. The children will now be able to meet with leading IT-specialists, and in the future, they may decide to combine training in one of the best technical universities in Moscow with additional educational programs of Technopark and Tehnotrek.
')
For the participants of this year and those who would like to prepare for the future Tehnokubkam, we present a task analysis.
The profile of a mountain range is schematically set as a rectangular table of the characters "." (Empty space) and "*" (part of a mountain). Each column of the table contains at least one "asterisk". It is guaranteed that either any of the “*” symbols is in the bottom row of the matrix, or another symbol “*” is directly below it.
An example of the image of a mountain range
The tourist route passes through the entire ridge from left to right. Every day the tourist moves to the right - to the adjacent column in the schematic image. Of course, every time he rises to the highest point of the mountain (or descends), which is located in the corresponding column.
Considering that the tourist is initially located at the highest point in the first column, and ends his route at the highest point in the last column, find two values:
The decision . To solve this problem, we calculate the height of each mountain and store it in the array h [] , where h [j] is equal to the height of the j- th mountain. To do this, we go around the given matrix, and if the element standing in row i and column j (rows and columns 0 are indexed) is equal to an asterisk, we update the height of the jth mountain: h [j] = max (h [j], n - i) . It remains to simply iterate over the columns from 0 to m - 2 inclusive and, if the current column is equal to j , update the maximum ascent or maximum descent value of | h [j + 1] - h [j] | .
Vasya bought a table with n legs. Each leg consists of two parts, which are connected to each other. Each part can be of arbitrary positive length, but it is guaranteed that out of all 2n parts it is possible to make n legs of the same length. When making up the legs, any two parts can be connected to each other. Initially, all the legs of the table are disassembled, and you are given the length of 2n parts in random order.
Help Vasya to collect all the legs of the table so that they are all the same length, breaking the given 2n parts into pairs in the correct way. Each leg must be composed of exactly two parts; it is not allowed to use only one part as a leg.
The decision . To solve this problem, we first calculate the length of one assembled table leg and store it in the variable len (len = sum / n , where sum is the total length of all parts, and n is the number of table legs). Save the lengths of all parts of the legs in an array a [] and sort it in ascending order. Then we iterate over the parts of the legs of the variable i from 0 to n - 1 inclusively and we will output in response pairs of the form (a [i], len - a [i]) .
You are given a rectangular checkered field consisting of n rows and m columns. The field contains a cycle of the characters "*", such that:
Below are a few examples of valid cycles:
All cells of the field, other than the cycle, contain the symbol ".". Cycle on the field exactly one. Attend cells that are different from the cycle, the robot can not.
In one of the cells of the cycle is a robot. This cell is marked with an "S". Find the command sequence for the robot to bypass the loop. Each of the four possible commands is encoded by a letter and denotes the movement of the Robot one cell:
The robot must bypass the cycle, having been in each of its cells exactly once (except for the starting point - in it it starts and ends its way).
Find the desired sequence of commands; any direction of loop traversal is allowed.
Decision. First, find the starting position of the Robot, save it and assign the value of the starting position to the asterisk. Since the condition is given a polyline without self-intersections and self-casings, the following algorithm is true: if there is a cell next to the current one in which there is an asterisk, we move to the next one whose value is equal to the asterisk, and assign its value to a point in which we moved). In this case, the next cell must be different from the one from which we came into the current cell. If there is no neighboring cell with an asterisk, it means that we have bypassed the entire polyline and need to finish the work of the program.
There are n dogs on the coordinate line, the i- th dog is at point x i . In addition, there are m bowls of food on the straight line, each has its coordinate on the straight line u j and the time t j through which the food in the bowl cools and becomes tasteless. This means that if the dog runs to the bowl at a time, strictly greater t j , then the food will cool down and the dog will not eat it.
Considering that each dog runs at a speed of 1, find the maximum number of dogs that can eat. Consider that the dogs will run to the bowls to which you point them. From one bowl can not eat two or more dogs.
Dogs can overtake each other, that is, if one of them stops to eat, the other can pass by it to get to another bowl.
The decision . If each bowl is presented as [u j - t j , u j + t j ] , then the i- th dog can eat from j bowls, if u j - t j ≤ x i ≤ u j + t j .
We will solve the problem eagerly. Consider the leftmost dog and the bowls from which she can eat. If there are no such bowls, the dog will not be able to eat. Otherwise, from the bowls available to the left-most dog, we will choose for it a bowl with the left-most right end. Further we will not consider this dog and this bowl and we will continue similarly our reasonings.
It is easy to see that such greed leads to the optimal answer:
For this task, it was possible to try to write other greed, but many would be wrong.
In order to realize this, we sort the dogs and bowls (on the left end) from left to right. We will go from left to right, processing the events “a bowl appeared” (in this case we add its right end to some data structure) and a “little dog appeared” (it is necessary for the dog to find the left most suitable right end in the data structure).
Complexity: O ( n log n ) or O ( n ) depending on the data structure (* set * or queue ).
C ++ Solution
Given a non-negative integer k and n non-negative integers a 1 , a 2 , ..., a n . Writing some of these numbers one after another in an arbitrary order and, possibly, using some of them several times (and some without using them at all), you need to make the shortest (smallest number of digits) number divisible by k , or determine that is impossible.
Decision. Note that when building a response, at any moment only the remainder of dividing its current prefix by k is important to us. Indeed, if the current response prefix has the remainder of dividing by k , equal to r , then by assigning to the prefix of the number a i this remainder will become equal to the remainder of d divided by k of the number r • 10 l i + a i ( l i is the number of digits in the record the numbers a i ).
Then, obviously, we are interested in getting any remainder from dividing by such an operation using the minimum number of digits in the record. Of course, we can get the remainder 0 immediately using an empty prefix, so for the remainder 0 we will be interested in the second largest answer.
Everything described above allows us to construct a graph on k vertices (from 0 to k - 1, respectively, the residuals), the edges of which are determined by the numbers a i : from the vertex v to the vertex
of length l i , meaning that by adding l i digits we can get a prefix with a remainder u from the prefix with the remainder v . It is easy to notice that some a i in this graph will correspond to the same edges (now their nk ) are numbers with the same length of the decimal notation and the remainder from dividing by k , therefore you should leave only the numbers unique for this criterion (they will not more than 10 k ), and then the number of edges will not exceed 10 k 2.
Now all that is required of us is to find the length of the shortest non-empty path from the vertex 0 to itself in the constructed graph. To avoid such an unpleasant cyclicity, let's just add an additional vertex k having the same outgoing edges as vertex 0, assuming that such a residue can only have an empty prefix. Now the problem is reduced to finding the shortest path from the vertex k to the vertex 0, which can be solved by the Dijkstra algorithm in O (k 2 ) . However, due to the specificity of the problem, the solution by the Ford – Bellman algorithm (with the correct cut-offs, of course) also passes all the tests, even if in theory it has such large O (k 3 ) .
Restoration of the answer in the problem is rather standard, with the exception of storing an additional number for each vertex that formed an edge, along which the transition needed in the shortest answer was performed.
Dijkstra's solution
Polycarp dreams of becoming a programmer and is a fan of the powers of two. Among the two numbers, he likes the one that is divided by the greater degree of the number 2.
Given a sequence of positive integers a 1 , a 2 , ..., a n, it is required to find r - the maximum power of 2, into which at least one of the numbers in the sequence is divided. In addition, you want to display the number of numbers a i , which are divided by r .
Decision. To solve this problem, you need to take advantage of the fact that the power of two grows quickly and the maximum power of two, into which the number not exceeding 10 9 can be divided, is equal to 29. Therefore, you just need to iterate on the given numbers, find the maximum power of two that the current number divides into and update the answer with this maximum degree.
There is an n- access house, each floor has m floors, and there are exactly k apartments on each floor of each entrance. Thus, there are only n • m • k apartments in the house. They are numbered in a natural way from 1 to n • m • k , that is, the first apartment on the first floor in the first entrance has number 1, the first apartment on the second floor of the first entrance has number k + 1, and so on. The peculiarity of this house is that it is round. That is, if you bypass it clockwise, then after the entrance number 1 there is the entrance number 2, then the entrance number 3 and so on until the entrance number n . After the entrance number n there is access number 1 again.
Edward lives in apartment number a, and Natasha lives in apartment number b . The transition to one floor up or down the stairs takes 5 seconds, the transition from the door of the entrance to the door of the neighboring entrance - 15 seconds, and the transition within one floor of one entrance occurs instantly. There is also an elevator in each entrance. It is arranged as follows: it always arrives exactly 10 seconds after the call, and to move a passenger one floor up or down, the elevator spends exactly one second. Landing and disembarking occur instantly.
Help Edward find the minimum time he can get to Natasha’s apartment. Consider that Edward can exit the porch only from the first floor of the corresponding porch (this happens instantly). If Edward is standing in front of the door of an entrance, he can enter it and immediately be on the first floor of this entrance (this also happens instantly). Edward can choose which direction to go around the house.
Decision. To solve this problem, it was necessary to accurately implement what is written in the condition. The main difficulty was in identifying the porch number and the floor number according to the apartment number. This could be done in the following way: if there are n entrances in the house, there are m floors on each porch, and k apartments on each floor, then apartment number a is at the entrance number ( a - 1) / ( m • k ) and floor number ((a - 1)% (m • k)) / k , and these numbers are 0-indexed, which is convenient for further calculations. After determining the numbers of entrances and floors, it was necessary to consider two cases: when the numbers of the entrances of Edward and Natasha were equal (then it was necessary to choose which is more optimal - take an elevator or go up / down the stairs) and when these numbers are different (it was necessary not to forget, that the house is round, and choose the right direction).
N teams came to the training for programming programming competitions. The coach for each team picked up a training session, the set of tasks for the i- th team takes up a i pages. At the disposal of the coach there are x sheets of paper, in which both sides are clean, and y sheets, in which only one side is clean. When printing conditions on a sheet of the first type, you can print two pages of the conditions of the tasks, and when printing on a sheet of the second type - only one. Of course, conditions cannot be printed on the sheet from two different sets of tasks. Please note that when using sheets that have both sides clean, it is not necessary to print a condition on both sides, one of them can remain clean.
You have to determine the maximum number of teams that the coach can print complete sets of tasks.
Decision. First, sort the specified sizes of task sets in a non-decreasing order. Then you need to start sorting through sets of tasks, starting with the smallest. If we cannot print the current set, then we are guaranteed that we will not be able to print any next set, so we need to print the answer and finish the algorithm. Otherwise, you need to print the current set, increase the answer to the unit and go to the next set. Each set is optimally printed as follows. Let x be the remaining number of two-sided sheets, y the remaining number of one-sided sheets, and a is the number of pages in the current set of tasks. If x = 0 and y = 0, then we definitely cannot print the current set. If a is odd and y > 0, print one page on a one-sided sheet and reduce a and y by one, otherwise, if a is odd and x > 0, print one page on a two-sided sheet (which we will not use anymore) and decrease a and x per unit. Now a is always an even number. Therefore, it is advantageous to first use double-sided sheets for printing, and if they are not enough, one-sided sheets. If one-sided sheets are not enough, then we will not be able to print the current set.
Computer memory consists of n cells that are lined up. Number the cells from 1 to n from left to right. About each cell, it is known whether it is free or belongs to some process (in this case, the process to which it belongs is known).
For each process, it is known that the cells belonging to it occupy a continuous area in memory. With the help of operations like "rewrite data from a busy cell to a free one, and busy now to be considered free", all the cells belonging to the processes must be located at the beginning of the computer memory. , ( ) .
, . , , . , , i , j , .
, , - .
Decision. , . , , ( ) , . : , pos1 pos2 , pos1 , pos2 , pos1. , — , - , , ( , ).
n . , , .
, , x i , . , d i , i - . , i - x i + d i . , , .
, , a . . , .
, a . , . , a .
, ( ) . - , , , , .
. , — , , . , a .
. mid — . cnt — , . set'a, , , .
( , ). set' , , , set ans. , set' , , set' .
, set' ans. ans a , mid , mid . ans.
929 people took part in the first qualifying round . The best result was shown by Vladislav Makeev (Moscow, Russia). The second and third place was taken by Rostislav Velichko (Stavropol, Russia) and Roman Gorbunov (Moscow, Russia).
The second qualifying round gathered 686 people. With a large margin, the first place in the rating table was taken by Vlad Mosko (Gomel, Belarus). Second and third place - Nazarbek Altybay (Aktobe, Kazakhstan) and Vladimir Romanov (Moscow, Russia).
Once again we congratulate all the finalists and look forward to seeing new participants next year.
In April, they will have the opportunity to once again prove themselves and compete for attractive prizes: iPad mini 2, iPod nano, iPod shuffle. In addition to mundane material awards, as well as indispensable honor and respect, the winners of the first Tekhnokubka (diploma of I degree) will receive as many as eight additional points for admission to undergraduate and specialist programs at MIPT and MGTU. N. E. Bauman, and the winners (diploma II and III degree) - six additional points. The children will now be able to meet with leading IT-specialists, and in the future, they may decide to combine training in one of the best technical universities in Moscow with additional educational programs of Technopark and Tehnotrek.
')
“Technocup is an important social initiative: thanks to the Olympiad, talented young programmers will get an additional opportunity to enter the leading technical universities of the country. We are systematically working to give students and schoolchildren as many opportunities as possible to gain the knowledge and practice necessary to work in a large company or to start developing their own project. This is focused on our educational projects with universities (Technopark, Technosphere and Technotrek), our IT championships, and now this list will be added to Technoclub ”, - Dmitry Dmitry21 Voloshin, director of the department of research and education Mail.Ru Group.
For the participants of this year and those who would like to prepare for the future Tehnokubkam, we present a task analysis.
A. The greatest lift
The profile of a mountain range is schematically set as a rectangular table of the characters "." (Empty space) and "*" (part of a mountain). Each column of the table contains at least one "asterisk". It is guaranteed that either any of the “*” symbols is in the bottom row of the matrix, or another symbol “*” is directly below it.
...........
.........*.
.*.......*.
**.......*.
**..*...**.
***********
An example of the image of a mountain range
The tourist route passes through the entire ridge from left to right. Every day the tourist moves to the right - to the adjacent column in the schematic image. Of course, every time he rises to the highest point of the mountain (or descends), which is located in the corresponding column.
Considering that the tourist is initially located at the highest point in the first column, and ends his route at the highest point in the last column, find two values:
- the greatest rise in a day (equal to 0, if there is not a single rise in the profile of the mountain range),
- the greatest descent per day (equal to 0 if there is not a single descent in the profile of the mountain range).
The decision . To solve this problem, we calculate the height of each mountain and store it in the array h [] , where h [j] is equal to the height of the j- th mountain. To do this, we go around the given matrix, and if the element standing in row i and column j (rows and columns 0 are indexed) is equal to an asterisk, we update the height of the jth mountain: h [j] = max (h [j], n - i) . It remains to simply iterate over the columns from 0 to m - 2 inclusive and, if the current column is equal to j , update the maximum ascent or maximum descent value of | h [j + 1] - h [j] | .
Solution example
int n, m; int h[N]; char c; void solve() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> c; if (c == '*') { h[j] = max(h[j], n - i); } } } int maxU = 0, maxD = 0; for (int i = 0; i < m - 1; i++) { int diff = h[i + 1] - h[i]; if (diff > 0) { maxU = max(maxU, diff); } else { maxD = max(maxD, -diff); } } cout << maxU << ' ' << maxD << endl; } B. Assemble the table
Vasya bought a table with n legs. Each leg consists of two parts, which are connected to each other. Each part can be of arbitrary positive length, but it is guaranteed that out of all 2n parts it is possible to make n legs of the same length. When making up the legs, any two parts can be connected to each other. Initially, all the legs of the table are disassembled, and you are given the length of 2n parts in random order.
Help Vasya to collect all the legs of the table so that they are all the same length, breaking the given 2n parts into pairs in the correct way. Each leg must be composed of exactly two parts; it is not allowed to use only one part as a leg.
The decision . To solve this problem, we first calculate the length of one assembled table leg and store it in the variable len (len = sum / n , where sum is the total length of all parts, and n is the number of table legs). Save the lengths of all parts of the legs in an array a [] and sort it in ascending order. Then we iterate over the parts of the legs of the variable i from 0 to n - 1 inclusively and we will output in response pairs of the form (a [i], len - a [i]) .
Solution example
int n, len, sum; int a[N]; int main() { cin >> n; for (int i = 0; i < 2 * n; i++) { cin >> a[i]; sum += a[i]; } len = sum / n; sort(a, a + 2 * n); for (int i = 0; i < n; i++) { cout << a[i] << ' ' << len - a[i] << endl; } } C. Path of the Robot
You are given a rectangular checkered field consisting of n rows and m columns. The field contains a cycle of the characters "*", such that:
- the cycle can be bypassed by visiting each of its cells exactly once, moving each time up / down / left / right by one cell;
- the cycle does not contain self-intersections and self-casings, that is, two cells of the cycle are side by side if and only if they are adjacent when moving along the cycle (self-cornering along the corner is also prohibited).
Below are a few examples of valid cycles:
All cells of the field, other than the cycle, contain the symbol ".". Cycle on the field exactly one. Attend cells that are different from the cycle, the robot can not.
In one of the cells of the cycle is a robot. This cell is marked with an "S". Find the command sequence for the robot to bypass the loop. Each of the four possible commands is encoded by a letter and denotes the movement of the Robot one cell:
- "U" - move the cell up,
- "R" - move the cell to the right,
- "D" - move the cell down,
- "L" - move the cell to the left.
The robot must bypass the cycle, having been in each of its cells exactly once (except for the starting point - in it it starts and ends its way).
Find the desired sequence of commands; any direction of loop traversal is allowed.
Decision. First, find the starting position of the Robot, save it and assign the value of the starting position to the asterisk. Since the condition is given a polyline without self-intersections and self-casings, the following algorithm is true: if there is a cell next to the current one in which there is an asterisk, we move to the next one whose value is equal to the asterisk, and assign its value to a point in which we moved). In this case, the next cell must be different from the one from which we came into the current cell. If there is no neighboring cell with an asterisk, it means that we have bypassed the entire polyline and need to finish the work of the program.
Solution example
int n, m, sx, sy; char a[N][N]; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; char dir[] = {'U', 'D', 'L', 'R'}; void solve() { cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> a[i][j]; if (a[i][j] == 'S') { sx = i, sy = j; } } } a[sx][sy] = '*'; int px = -1, py = -1; while (true) { bool wasMove = false; for (int i = 0; i < 4; i++) { int nx = sx + dx[i]; int ny = sy + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) { continue; } if (a[nx][ny] != '*') { continue; } if (nx == px && ny == py) { continue; } a[nx][ny] = '.'; px = sx, py = sy; sx = nx, sy = ny; cout << dir[i]; wasMove = true; break; } if(wasMove) { break; } } puts(""); } D. Dogs and bowls
There are n dogs on the coordinate line, the i- th dog is at point x i . In addition, there are m bowls of food on the straight line, each has its coordinate on the straight line u j and the time t j through which the food in the bowl cools and becomes tasteless. This means that if the dog runs to the bowl at a time, strictly greater t j , then the food will cool down and the dog will not eat it.
Considering that each dog runs at a speed of 1, find the maximum number of dogs that can eat. Consider that the dogs will run to the bowls to which you point them. From one bowl can not eat two or more dogs.
Dogs can overtake each other, that is, if one of them stops to eat, the other can pass by it to get to another bowl.
The decision . If each bowl is presented as [u j - t j , u j + t j ] , then the i- th dog can eat from j bowls, if u j - t j ≤ x i ≤ u j + t j .
We will solve the problem eagerly. Consider the leftmost dog and the bowls from which she can eat. If there are no such bowls, the dog will not be able to eat. Otherwise, from the bowls available to the left-most dog, we will choose for it a bowl with the left-most right end. Further we will not consider this dog and this bowl and we will continue similarly our reasonings.
It is easy to see that such greed leads to the optimal answer:
- If the most left dog can eat, then there is no point for her not to eat, because with this we remove one bowl and worsen the answer to the unit.
- Consider the bowls of which the most left dog can eat. All these bowls will be available for the rest of the dogs, except for those whose right border is too far to the left. Thus, if we want to take any bowl (and we already understood from point 1 that it is worth doing), then it will be more profitable to take the bowl with the leftmost end, so we will not make it worse for the dogs on the right.
For this task, it was possible to try to write other greed, but many would be wrong.
In order to realize this, we sort the dogs and bowls (on the left end) from left to right. We will go from left to right, processing the events “a bowl appeared” (in this case we add its right end to some data structure) and a “little dog appeared” (it is necessary for the dog to find the left most suitable right end in the data structure).
Complexity: O ( n log n ) or O ( n ) depending on the data structure (* set * or queue ).
C ++ Solution
Solution example
const int N = 200200; int n, m; int x[N]; int u[N], t[N]; bool read() { if (!(cin >> n >> m)) return false; forn(i, n) assert(scanf("%d", &x[i]) == 1); forn(i, m) assert(scanf("%d%d", &u[i], &t[i]) == 2); return true; } pti segs[N]; void solve() { forn(i, m) segs[i] = mp(u[i] - t[i], u[i] + t[i]); sort(x, x + n); sort(segs, segs + m); int ans = 0; multiset<int> z; for (int i = 0, j = 0; i < n; ) { if (j < m && segs[j].x <= x[i]) { z.insert(segs[j].y); j++; } else { auto it = z.lower_bound(x[i]); i++; if (it != z.end()) { ans++; z.erase(it); } } } cout << ans << endl; } E. Collect the number
Given a non-negative integer k and n non-negative integers a 1 , a 2 , ..., a n . Writing some of these numbers one after another in an arbitrary order and, possibly, using some of them several times (and some without using them at all), you need to make the shortest (smallest number of digits) number divisible by k , or determine that is impossible.
Decision. Note that when building a response, at any moment only the remainder of dividing its current prefix by k is important to us. Indeed, if the current response prefix has the remainder of dividing by k , equal to r , then by assigning to the prefix of the number a i this remainder will become equal to the remainder of d divided by k of the number r • 10 l i + a i ( l i is the number of digits in the record the numbers a i ).
Then, obviously, we are interested in getting any remainder from dividing by such an operation using the minimum number of digits in the record. Of course, we can get the remainder 0 immediately using an empty prefix, so for the remainder 0 we will be interested in the second largest answer.
Everything described above allows us to construct a graph on k vertices (from 0 to k - 1, respectively, the residuals), the edges of which are determined by the numbers a i : from the vertex v to the vertex
of length l i , meaning that by adding l i digits we can get a prefix with a remainder u from the prefix with the remainder v . It is easy to notice that some a i in this graph will correspond to the same edges (now their nk ) are numbers with the same length of the decimal notation and the remainder from dividing by k , therefore you should leave only the numbers unique for this criterion (they will not more than 10 k ), and then the number of edges will not exceed 10 k 2.Now all that is required of us is to find the length of the shortest non-empty path from the vertex 0 to itself in the constructed graph. To avoid such an unpleasant cyclicity, let's just add an additional vertex k having the same outgoing edges as vertex 0, assuming that such a residue can only have an empty prefix. Now the problem is reduced to finding the shortest path from the vertex k to the vertex 0, which can be solved by the Dijkstra algorithm in O (k 2 ) . However, due to the specificity of the problem, the solution by the Ford – Bellman algorithm (with the correct cut-offs, of course) also passes all the tests, even if in theory it has such large O (k 3 ) .
Restoration of the answer in the problem is rather standard, with the exception of storing an additional number for each vertex that formed an edge, along which the transition needed in the shortest answer was performed.
Dijkstra's solution
Solution example
for (int i = 0; i < n; ++i) { int x; assert(scanf("%d", &x) == 1); any[x % k][length(x)] = x; } p10[0] = 1; for (int i = 0; i + 1 < P; ++i) p10[i + 1] = (p10[i] * 10) % k; for (int i = 0; i <= k; ++i) { d[i] = int(1e9); p[i] = -1; used[i] = false; } d[k] = 0; while (true) { int v = -1; for (int i = 0; i <= k; ++i) if (!used[i] && (v == -1 || d[v] > d[i])) v = i; if (v == -1) break; if (v == 0) break; used[v] = true; for (int r = 0; r < k; ++r) for (int l = 0; l < P; ++l) if (any[r][l] != -1) { int to = (v * p10[l] + r) % k; if (d[to] > d[v] + l) { d[to] = d[v] + l; p[to] = v; w[to] = any[r][l]; used[to] = false; } } } if (p[0] == -1) { puts("NO"); } else { puts("YES"); vector <int> res; int v = 0; do { res.push_back(w[v]); v = p[v]; } while (v != k); reverse(res.begin(), res.end()); for (auto x: res) printf("%d", x); } A. Polycarp's Favorite Numbers
Polycarp dreams of becoming a programmer and is a fan of the powers of two. Among the two numbers, he likes the one that is divided by the greater degree of the number 2.
Given a sequence of positive integers a 1 , a 2 , ..., a n, it is required to find r - the maximum power of 2, into which at least one of the numbers in the sequence is divided. In addition, you want to display the number of numbers a i , which are divided by r .
Decision. To solve this problem, you need to take advantage of the fact that the power of two grows quickly and the maximum power of two, into which the number not exceeding 10 9 can be divided, is equal to 29. Therefore, you just need to iterate on the given numbers, find the maximum power of two that the current number divides into and update the answer with this maximum degree.
Solution example
int n, x; int main() { cin >> n; int ans = -1, cnt = 0; for (int i = 0; i < n; i++) { cin >> x; int cur = 1, power = 0; while (true) { cur *= 2; if (x % cur) break; power++; } if (ans < power) { ans = power; cnt = 1; } else if (ans == power) { cnt++; } } cout << ans << ' ' << cnt << endl; } B. Floors
There is an n- access house, each floor has m floors, and there are exactly k apartments on each floor of each entrance. Thus, there are only n • m • k apartments in the house. They are numbered in a natural way from 1 to n • m • k , that is, the first apartment on the first floor in the first entrance has number 1, the first apartment on the second floor of the first entrance has number k + 1, and so on. The peculiarity of this house is that it is round. That is, if you bypass it clockwise, then after the entrance number 1 there is the entrance number 2, then the entrance number 3 and so on until the entrance number n . After the entrance number n there is access number 1 again.
Edward lives in apartment number a, and Natasha lives in apartment number b . The transition to one floor up or down the stairs takes 5 seconds, the transition from the door of the entrance to the door of the neighboring entrance - 15 seconds, and the transition within one floor of one entrance occurs instantly. There is also an elevator in each entrance. It is arranged as follows: it always arrives exactly 10 seconds after the call, and to move a passenger one floor up or down, the elevator spends exactly one second. Landing and disembarking occur instantly.
Help Edward find the minimum time he can get to Natasha’s apartment. Consider that Edward can exit the porch only from the first floor of the corresponding porch (this happens instantly). If Edward is standing in front of the door of an entrance, he can enter it and immediately be on the first floor of this entrance (this also happens instantly). Edward can choose which direction to go around the house.
Decision. To solve this problem, it was necessary to accurately implement what is written in the condition. The main difficulty was in identifying the porch number and the floor number according to the apartment number. This could be done in the following way: if there are n entrances in the house, there are m floors on each porch, and k apartments on each floor, then apartment number a is at the entrance number ( a - 1) / ( m • k ) and floor number ((a - 1)% (m • k)) / k , and these numbers are 0-indexed, which is convenient for further calculations. After determining the numbers of entrances and floors, it was necessary to consider two cases: when the numbers of the entrances of Edward and Natasha were equal (then it was necessary to choose which is more optimal - take an elevator or go up / down the stairs) and when these numbers are different (it was necessary not to forget, that the house is round, and choose the right direction).
Solution example
int n, m, k, a, b; int main() { cin >> n >> m >> k >> a >> b; a--, b--; int p1 = a / (m * k), p2 = b / (m * k); int f1 = (a % (m * k)) / k, f2 = (b % (m * k)) / k; if (p1 == p2) { cout << min(abs(f1 - f2) + 10, abs(f1 - f2) * 5) << endl; } else { if(p1 > p2) swap(p1, p2); cout << min((p2 - p1) * 15, (p1 + n - p2) * 15) + min(f1 * 5, 10 + f1) + min(f2 * 5, 10 + f2) << endl; } } C. Printing conditions
N teams came to the training for programming programming competitions. The coach for each team picked up a training session, the set of tasks for the i- th team takes up a i pages. At the disposal of the coach there are x sheets of paper, in which both sides are clean, and y sheets, in which only one side is clean. When printing conditions on a sheet of the first type, you can print two pages of the conditions of the tasks, and when printing on a sheet of the second type - only one. Of course, conditions cannot be printed on the sheet from two different sets of tasks. Please note that when using sheets that have both sides clean, it is not necessary to print a condition on both sides, one of them can remain clean.
You have to determine the maximum number of teams that the coach can print complete sets of tasks.
Decision. First, sort the specified sizes of task sets in a non-decreasing order. Then you need to start sorting through sets of tasks, starting with the smallest. If we cannot print the current set, then we are guaranteed that we will not be able to print any next set, so we need to print the answer and finish the algorithm. Otherwise, you need to print the current set, increase the answer to the unit and go to the next set. Each set is optimally printed as follows. Let x be the remaining number of two-sided sheets, y the remaining number of one-sided sheets, and a is the number of pages in the current set of tasks. If x = 0 and y = 0, then we definitely cannot print the current set. If a is odd and y > 0, print one page on a one-sided sheet and reduce a and y by one, otherwise, if a is odd and x > 0, print one page on a two-sided sheet (which we will not use anymore) and decrease a and x per unit. Now a is always an even number. Therefore, it is advantageous to first use double-sided sheets for printing, and if they are not enough, one-sided sheets. If one-sided sheets are not enough, then we will not be able to print the current set.
Solution example
int n, x, y; int a[N]; bool can(int a) { if (a % 2) { if (y > 0) a--, y--; else if (x > 0) a--, x--; else return false; } if (x * 2 >= a) { x -= a / 2; return true; } a -= 2 * x, x = 0; if (y >= a) { y -= a; return true; } return false; } int main() { cin >> n >> x >> y; for (int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); int ans = 0; for (int i = 0; i < n; i++) if(can(a[i])) ans++; else break; cout << ans << endl; } D. Memory defragmentation
Computer memory consists of n cells that are lined up. Number the cells from 1 to n from left to right. About each cell, it is known whether it is free or belongs to some process (in this case, the process to which it belongs is known).
For each process, it is known that the cells belonging to it occupy a continuous area in memory. With the help of operations like "rewrite data from a busy cell to a free one, and busy now to be considered free", all the cells belonging to the processes must be located at the beginning of the computer memory. , ( ) .
, . , , . , , i , j , .
, , - .
Decision. , . , , ( ) , . : , pos1 pos2 , pos1 , pos2 , pos1. , — , - , , ( , ).
int n; int a[N], need[N]; int szneed; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; if (a[i] != 0) need[szneed++] = a[i]; } int ans = 0; for (int i = 0; i < n; i++) { if (need[i] != 0 && need[i] != a[i]) ans++; } cout << ans << endl; } E.
n . , , .
, , x i , . , d i , i - . , i - x i + d i . , , .
, , a . . , .
, a . , . , a .
, ( ) . - , , , , .
. , — , , . , a .
. mid — . cnt — , . set'a, , , .
( , ). set' , , , set ans. , set' , , set' .
, set' ans. ans a , mid , mid . ans.
int n, a; vector<pair<pair<int, int>, int > > v; set<pair<int, int> > s; vector<int> ans; int ok (int x) { s.clear(); ans.clear(); for (int i = 0; i < n; i++) { int l = v[i].first.first, r = v[i].first.second; while (!s.empty() && s.begin()->first <= l) { ans.push_back(s.begin()->second); s.erase(s.begin()); } if ((int)s.size() + 1 <= x) s.insert(mp(r, v[i].second)); else { s.insert(make_pair(r, v[i].second)); set<pair<int, int> > :: iterator it = s.end();--it; s.erase(it); } } while (!s.empty()) { ans.push_back(s.begin()->second); s.erase(s.begin()); } return (int)ans.size(); } int main() { cin >> n >> a; v.resize(n); for (int i = 0; i < n; i++) cin >> v[i].first.first >> v[i].first.second, v[i].first.second += v[i].first.first, v[i].second = i; sort(v.begin(), v.end()); int l = 0, r = a; while (r - l > 1) { int mid = (l + r) / 2; if(ok(mid) >= a) r = mid; else l = mid; } ok(r); cout << r << endl; for (int i = 0; i < a; i++) cout << ans[i] + 1 << ' '; cout << endl; } 929 people took part in the first qualifying round . The best result was shown by Vladislav Makeev (Moscow, Russia). The second and third place was taken by Rostislav Velichko (Stavropol, Russia) and Roman Gorbunov (Moscow, Russia).
The second qualifying round gathered 686 people. With a large margin, the first place in the rating table was taken by Vlad Mosko (Gomel, Belarus). Second and third place - Nazarbek Altybay (Aktobe, Kazakhstan) and Vladimir Romanov (Moscow, Russia).
Once again we congratulate all the finalists and look forward to seeing new participants next year.
Source: https://habr.com/ru/post/280554/
All Articles