e-olymp 2267. Journey

The army of Rzeczpospolita is moving from the city Kostroma to the village Domnino. Two hetmans, Stefan and Konstantin, lead the army.

Stefan procured the roadmap of Kostroma province, and every night he routes the army from one village to the other along some road. Konstantin bought the map of secret trails between villages in advance, and every day he leads the march along the one of such trails. Each hetman asks their guide Ivan Susanin for a route before each march.

The length of each road is indicated on Stefan’s map. So Stefan knows the minimal distance from each village to the Domnino village according to his map. Similarly Konstantin knows the minimal distance from each village to Domnino village along trails on his map.

Ivan Susanin does not want to be disclosed as a secret agent, so each time he chooses a road (for Stefan) or a trail (for Konstantin) so, that the minimal distance to the Domnino village according to the map owned by the asking hetman is strictly decreasing.
Maps
Help Ivan to find the longest possible route to the Domnino village.

Input

The first line contains three integer numbers [latex]n, s[/latex] and [latex]t[/latex] — number of villages in Kostroma province, and numbers of start and Domnino village [latex](2 \le n \le 1000; 1 \le s; t \le n)[/latex]. Villages are numbered from [latex]1[/latex] to [latex]n[/latex]. Start and Domnino villages are distinct.

Two blocks follow, the first one describing Stefan’s map, and the second one describing Konstantin’s map.

The first line of each block contains an integer number [latex]m[/latex] — the number of roads/trails between villages [latex](n-1 \le m \le 100000)[/latex]. Each of the following [latex]m[/latex] lines contains three integer numbers [latex]a, b[/latex], and [latex]l[/latex] — describing the road/trail between villages [latex]a[/latex] and [latex]b[/latex] of length [latex]l[/latex] [latex](1 \le a, b \le n; 1 \le l \le 10^6)[/latex].

Rzeczpospolita army can move in any direction along a road or a trail. It’s guaranteed that one can travel from any village to any other using each of the maps. The army starts its movement in the evening from the village number and moves one road each night and one trail each day.

Output

Output the total length of the longest route that Ivan Susanin can arrange for Rzeczpospolita army before reaching the Domnino village (along the roads and trails). If Ivan Susanin can route the army forever without reaching the Domnino village, output the number «[latex]-1[/latex]».

Tests

Input Output
1 5 1 5
5
1 2 2
1 4 2
2 3 1
3 4 1
5 3 1
4
1 2 2
2 4 2
2 3 1
2 5 2
-1
2 3 1 3
4
1 2 10
2 3 10
1 3 20
2 3 30
4
2 1 10
1 3 10
1 1 10
2 3 10
20

Algorithm

The problem has been resolved together with Sploshnov Kirill.

So, we are dealing with a rather cumbersome task for the graphs, therefore we analyze it consistently. To get started we define the data structure

because dealing with the routes and subsequently, we will have to color our edges. For convenience, we don’t think about two maps as about different graphs, and can establish one graph, where edges of each map are painted in a different color.
For example edges of first map color in RED, and the other in BLUE. Then select the first map is equivalent to passing by red edges, or blue otherwise. In this way, route, that we are looking for, should be based on the successively alternating colors of the edges.
Proceed directly to the solution.
From the condition is understandable, that each hetman knows the shortest path to the final village. This data will be needed for us too, so for each map (edges of the same color) use Dijkstra’s algorithm and find the shortest path from each vertex to the target.  (Function   void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color); ).  We need absolutely standard Dijkstra’s algorithm with the only difference that the edges of the opposite color aren’t available. You can learn more about Dijkstra’s algorithm in the sources of information listed at the end of the article.
Continue analyzing the condition, we understand, that we can’t pass over the edges so, that the shortest distance to the final vertex increased. This will help us to simplify the graph, and significantly reduce the number of possible variants of passage, namely, any bidirectional edge will be either removed completely or strictly directed.  Then, passing on to the edges of the same color in each map, if it doesn’t satisfy the specified condition coloring it as DELETED. (Function  void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color); ).
Now we can get started with the search for the longest route. There are two options: either there is the longest path, or we can walk along the edges infinitely, if it does not contradict the statement of the problem, that is, in the combined of two maps graph there is a cycle. So we organize checks on acyclic. Now we have the right to pass along the edges only alternating colors at each step. In order to find a cycle, we use vertex coloring, and will explore the graph until we try to treat already colored vertex or not conclude that it is acyclic.  (Function  bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color); ). This algorithm can be obtained after detailed acquaintance with the usual cycle searching algorithm (reference to the source is located at the end of the article). If we find any loop in this graph, then our job is over and we should just output «[latex]-1[/latex]».
Otherwise, make sure that the graph is acyclic, we are looking for the longest route. As our graph has been simplified and has no cycles, and all edges are directed, then the task of finding this way becomes computationally simple. For this declaring an array of longest distance dynamically, along the way memorizing the already calculated values, sequentially find the maximum length of the route until we arrive at the finish village. (Function  int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) ). This will be the answer to the task.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

Links

e-olymp 2307. The sum

The array of [latex]n[/latex] elements is given. Find the sum of numbers on a segment.

Input

The first line contains two integers [latex]n[/latex] and [latex]k[/latex] [latex](1 \le n \le 10^5, 0 \le k \le 10^5)[/latex] — the number of elements in array and the number of queries. The next [latex]k[/latex] lines contain the queries of two forms:

  • [latex]A[/latex] [latex]l[/latex] [latex]r[/latex] [latex]x[/latex]  — assign the value of [latex]x[/latex] to each element form position [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n, 0 \le x \le 10^9)[/latex]
  • [latex]Q[/latex] [latex]l[/latex] [latex]r[/latex] — find the sum of array elements on positions from [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n)[/latex]

Initially the array is filled with zeroes.

Output

For each query of the form «[latex]Q[/latex] [latex]l[/latex] [latex]r[/latex]» print the sum of numbers on a segment.

Tests

Input Output
1 5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5
3
2
3
4
2
7
2 10 6
A 1 10 1
Q 1 10
A 1 5 2
Q 1 10
A 4 7 3
Q 1 10
10
15
21
3 100000 2
A 1 100000 1000000000
Q 1 100000
100000000000000

Algorithm

After reading the statement of the problem it is understandable that we should implement segment tree with support for multiple modification request — assignment. To make modifications to the whole segment and quickly answer for the amounts queries, we organize data structure in which each node store «colored» — if it is painted in any color or not and a sum on corresponding to this node segment.

Under the node coloring we will understand that all segment with all its subsegments should be colored in the appropriate color (assigned a specific number). Also define the mark that the node isn’t colored (in the code defined as WHITE), for example, any negative number, because queries contain only positive. This implementation allows us to do «delayed» update of the tree. Specifically, for each request of modification, instead of changing the values at all vertices where it is required, change only some of them, leaving «colored» markers for the other segments, which means that the whole segment with its subsegments should be painted in this color.
But if we do it so, after each modification request segment tree will stop being up to date. For resolving this problem, organise a function, that will «push» information from parents to children: void push(Node *tree, int currentNode, int left, int right) . This function is called during requests processing to update the appropriate values:

  • assign parent’s color to the children
  • recalculate the amount of the segment for children (as the length of the segment multiplied by the current color (number))
  • set parent node as uncolored

Thus, to solve this task, we need two usual for segment tree functions:

  • void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color)
  • long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder)

With the difference that, when we are going down by the tree, pushes information only as far as necessary (it should be noted, that in this way the asymptotic doesn’t impair and remains standard [latex]O(\log n)[/latex]).

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Footnote: such realization, where the problem constraints too large queries, and in the current version when we update a range and only mark its child that it needs to be updated and update it when needed, usually calls lazy propagation. This approach allows us to solve a variety of new at first glance seemed complex tasks. More information listed at the end of the article.

Code

Links

e-olymp 2906. Can you answer these queries — 1

You are given an integer sequence.

[latex]a_1, a_2, \ldots, a_n (|a_i| \le 15007, 1 \le n \le 50000)[/latex].

A query is defined as follows:

[latex]Query(x, y) = MAX (a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y)[/latex]

Given [latex]m[/latex]  queries, your program must output the results of these queries.

Input

The first line contains the integer [latex]n[/latex]. In the second line [latex]n[/latex] integers of the sequence are given. The third line contains the integer [latex]m[/latex]. Then [latex]m[/latex] lines follow, where line [latex]i[/latex] contains two numbers [latex]x_i[/latex] and [latex]y_i[/latex].

Output

Print the results of the [latex]m[/latex] queries, one query per line.

Tests

Input Output
1 3
-1 2 3
1
1 2
2
2 5
1 2 3 4 5
1
1 5
15
3 5
-1 -2 -3 -4 -5
1
1 5
-1
4 8
1 2 -3 -2 10 1 -15 7
4
1 1
3 4
3 6
1 8
1
-2
11
11
5 9
1 -2 3 -4 5 -6 7 -8 9
3
1 9
2 8
2 4
9
7
3

Algorithm

After analyzing the condition of the problem, we can understand that we need on a given segments of array to find subsegment with a maximum amount. We can solve this task by using segment tree, but before this we should modify it a bit. Create a structure of which our tree consists:

That is, in each vertex of tree we store [latex]4[/latex] values:
  • the answer to the task for the current subsegment
  • the maximum amount among all prefixes
  • the maximum amount among all suffixes
  • the sum on the segment

First we need to get the values in the leaves. It’s simple enough all [latex]4[/latex] fields take the value of the number, that corresponds to this leaf. Now, having values in the leaves, we need to learn how to get the values in parent. For this we use the function Node mergeNodes(Node leftChild, Node rightChild), which assign to parent’s fields such values:

  • Answer in the parent equal to the answer in the right or the left child (means that the best subsegment of the current node is entirely in the left or right child), or the maximum amount of the maximum suffix in the left child and the maximum prefix in the right child (which means that it is partially is in the left child and partially is in the right child).
  • The maximum amount of the parent on prefix is equal to the maximum prefix of left child or sum on segment of left child and maximum prefix of right child.
  • The maximum amount of the parent on suffix is equal to the maximum suffix of right child or sum on segment of right child and maximum suffix of right child.
  • Amount on segment of the parent is equal to the sum on segment of left child and sum on segment of right child.

Now, with all the auxiliary functions for working with a built data structure, we need only to construct a tree and learn to get an answer on it.
We need two more functions:

  • void build(int *base, Node *tree, int currentNode, int left, int right) — recursive construction of a tree from the leaves to the root by initial sequence numbers.
  • Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) — as in the usual tree segments we get an answer going down by the tree, but instead of any associative function (eg sum or maximum) we execute the merger of nodes described earlier. Resulting node will store an answer corresponding to a given in the query segment.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

Links

e-olymp 4002. Down with cheating!

During the test, Professor Floyd noticed that some students exchanged notes. At first, he wanted to put a bad mark everyone, but that day the professor was in a good mood, therefore he decided to split all the students into two groups and put a bad mark to only those,who writting off.
The professor recorded all the pairs of students, who exchanged notes. You need to determine whether they can be divided into two groups, where student of one group exchange notes only with student of other group.

Input

There are two numbers in first line [latex]m[/latex] and [latex]n[/latex] — quantity of students and quantity of pairs, who exchanged notes. [latex](1 \le n \le 100[/latex], [latex]0 \le m \le n(n-1)/2)[/latex]. Further in [latex]m[/latex] lines there are description of student pairs: two different numbers, corresponding to the student serial number, who exchanged notes (numbering from [latex]1[/latex]). Each pair of students is listed only once.

Output

Print the answer to the Professor’s Floyd task. If it is possible to divide the students into two groups output «YES», or «NO» otherwise.

Test

Input Output
1 3 2
1 2
2 3
YES
2 3 3
1 2
1 3
2 3
NO
3 12 9
1 3
2 3
4 5
5 6
6 8
6 9
7 9
8 10
11 12
YES
4 12 10
1 3
2 3
4 5
5 6
6 8
6 9
7 9
8 9
8 10
11 12
NO

bipartite graph
Illustration for the test №3notBipartiteGraph
Illustration for the test №4
 

Algorithm

After reading the statement of the problem becomes clear that our goal is to determine whether it is possible to divide the graph into two sets in each of them there aren’t adjacent vertices — check whether the graph is bipartite.
For the implementation, we need a basic function
bool isBipartite(vector<int> *listOfVertices, int *colorOfVertices, int sourceVertex, int quantityOfVertex), that takes a graph (in this program as an array of vectors of adjacent vertices, but can be done similar implementation on the adjacency matrix), array of vertices’ colors, vertex, which we start checking, and the number of vertices.
To solve the problem we perform graph coloring. Naturally, we organize data reading process. And our next sequence of steps is:

  • Initially, we define all the vertices as WHITE — not processed.
  • Call the fucntion for the first vertex (in our numbering — zero).
  • Assign source vertex with one of the colors (for convenience in program we denote it as RED) — equivalent to the action that we put the vertex in the first of two sets.
  • Color all adjacent vertex with inverse color (in program it’s BLUE — has opposite to RED number value) — equivalent to the action that we put vertices in the second set.
  • Color all adjacent to the adjacent vertices with RED color —  we put them in the first set.
  • Repeat this until we have completed bypassing (for convenience we use queue)  — coloring of all connected vertices. But we can find adjacent vertices with same color that sygnalize that our graph cannot be colored with two color — so it isn’t bipartite.

It should be noted that the function implemented in such way works for only one connected component. Therefore, to check the disconnected graphs we must check  all vertices which color is white.

Code

 

Links

AL16

Algolist. Data structures. Task 16.

There is a Ministry, that includes [latex]N[/latex] officials ([latex]N[/latex] is a natural number). Each official possibly has subordinates and chiefs. What is more, there are some rules:

  • Subordinates of my subordinate are my subordinates.
  • Chiefs of my chief — my chiefs.
  • My chief is not my subordinate.
  • Each official has no more than one direct chief.

In order to get a license for the export of copper, necessary to obtain a signature of the 1st official — сhief of all the сhiefs. But the situation complicated by the fact, that each official, generally speaking, can require «visas» — signatures some of his immediate subordinates and a bribe — a certain amount of dollars. Non-empty list of possible visas and corresponding to this list bribe are known for each official. The empty list means that the official doesn’t require a visa in this case. The official will put his signature, only if he receives all signatures from one of the visas list and the appropriate bribe.

You need to define and output the permissible and minimal for sum of bribes order and its cost.

Input

The input data is the following sequence of lines:

  • Quantity of officials [latex]N[/latex] ([latex]N < 100[/latex] ).
  • List of subordinates for current visa, which consists of their indeces, suitable to the order in which they came to input (could be empty, it suggests that the official doesn’t require a visa in this case).
  • «bribe» — signalyze, that input of current visa end. In next line you will recieve the cost of bribe — real number [latex]B[/latex] ([latex]0 < B < 10^6[/latex]) .
  • «next_official» — determine that information about previous official ended and next line will contain empty or not empty list of next official’s visas (there is no such command before 1st official. If there is no command «next_official « after the number, that determine a bribe, you will recieve next visa of the current official).

More info about input data you can find in test examples.

Output

You need to output in the separate lines the minimum sum of bribes for getting a license and the order. This is a string with the consecutive indices of the officials, who participated in the payment of the minimum bribe, (in order of raising in the hierarchical system, from left to right (arranging in entering the appropriate official)) separated with delimetr /.

Tests

Input Output
1 2
2
bribe
50
next_official
50
2/1
2 5
2
bribe
100
3
bribe
200
4
bribe
150
next_official
5
bribe
10
next_official
next_official
next_official
110
5/2/1
3 7
2
bribe
150
3
bribe
50
next_official
4
bribe
40
5
bribe
20
next_official
6
bribe
150
7
bribe
200
next_official
next_official
next_official
next_official
170
5/2/1
4 5
2
bribe
50
next_official
3
bribe
40
4
bribe
10
next_official
next_official
5
bribe
10
next_official
70
5/4/2/1
5 8
2
bribe
100
next_official
3
bribe
200
4
bribe
150
3 4
bribe
50
next_official
7
bribe
25
next_official
5
bribe
10
6
bribe
80
next_official
next_official
next_official
8
bribe
35
next_official
220
8/7/5/3/4/2/1

tree_2

Illustration for the test №3tree_1Illustration for the test №4

treeIllustration for the test №5

Algorithm

In order to implement solution of this problem, we construct two data structures Visa and Official. First of these stores fields vector <unsigned int> listOfSubordinatesForBribe — indices of subordinates, whose signatures are needed in this bribe and directly bribe. Every official, in their turn, has Id (serial number) and a list of all his visas — vector <Visa> listOfRequiredVisas. Also, we need two functions:

    • bool isBypassed(Official currentOfficial, string order) — determines whether the official is bypassed. It is realized on the condition that every official has no more than one direct chief. Therefore to find out if we take into account this official, we need to check whether there is in the list of bypassed at least one of his subordinates. Implementing a check directly on the current official Id is not possible, because we will go recursively from the leaves to the root.
    • void findCheapestWay(Official *listOfOfficials, Official currentOfficial, string &amp;order, unsigned int &amp;minimumBribe) — the main function dedicated to the search of the answer. Consider its job in detail:
      Because there is no point in considering the officials, who don’t require any visa, we will process only those,who have non-empty list of visas and haven’t been visited yet. Otherwise, we will just go up to a higher level in the tree. For each official store vector <unsigned int> possibleSumsOfBribes and vector <string> possibleOrdersOfBypassing — possible variants of bribes and the order by which it was achieved. Also, we need two variables passed by reference in function — number minimumBribe and string order. They will help us to maintain a minimum bribe and its order at each hierarchy level, when we will call the recursive search for each subordinate in the visa.

Let us turn to the main executable part of the program. Organize the correct reading of the incoming data stream and save each official with its corresponding Id.
Start the search function of the first and the most important official — root. Getting in the first visa and starting a recursive search for all the subordinates we descend directly to the leaves of the tree. Leaning into a dead end, we start to climb from the bottom up, and for each official we find minimum possible bribe and order directly at his level. Thus we will be able consistently for each branch find it mimimum and pick it up by going to the root of the tree. Doing this for every possible visas, we fill the vector of potential bribes values, in which by searching the minimum element  we can select required value. This will be the lowest possible price for a license.
Further details of the implementation can be seen in the comments to the code.

Code

Code of the program (here you can analyze the working time of program)

A300

There is a sequence of real numbers [latex]a_1, a_2, \ldots[/latex](read to the end of the input stream). You need to get the sequence of numbers [latex]b_1, \ldots, b_{10}[/latex], where [latex]b_i[/latex] is the sum of those members of input sequence, that belong left-open interval [latex](i — 1, i](i = 1, \ldots, 10)[/latex]. If the interval doesn’t contain any members of the sequence, the corresponding [latex]b_i[/latex] will be set equal to zero.

Input

The sequence of real numbers  [latex]a_1, a_2, \ldots[/latex].

Output

Output the sequence [latex]b_1, \ldots, b_{10}[/latex], that satisfies specified conditions.

Tests

Input sequence Output sequence
1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
2 1 1 1 1 1 1 1 7 0 0 0 0 0 0 0 0 0
3 2.1 2.5 2.7  0 0 7.3 0 0 0 0 0 0 0
4  11 12 13 14 15 0 0 0 0 0 0 0 0 0 0
5   2 12 85 0.6 0.6 2 0 0 0 0 0 0 0 0
6 2.02 42 1.998 3 7.43 3.33 3.03 5.56 5 5.5 0 1.998 5.02 6.36 5 11.06 0 7.43 0 0

Algorithm

The proposed task we can solve in two different ways: using class vector and like a problem with stream processing of data.

  1. Class vector:
    Initialize a vector, that will store all the elements of the input sequence (push them to the vector to the end of the input stream). Further, sort it ascending for easy follow-up work. For the each element of initial sequence check whether it belongs to the current interval. If it is true, it will be added to the corresponding element of resulting sequence, or zero will be added otherwise. Output the resulting sequence.
  2. Stream processing:
    While we are reading the input stream, we can determine which element of the resulting sequence it belongs, by using rounding to smallest integral value that is not less that our and substracting one (we need to remember that we can’t go beyond the bounds of the array, therefore we use a separate check). Perform the output of the result.

Code (class Vector)

Code (stream processing)

e-olymp 332. Детская железная дорога

Витэк не прекращает своих игр с кубиками. А тут еще папа подарил ему детскую железную дорогу. Витэк расставляет какое-то количество кубиков по одному на вагончик и перед тем как закончить игру, решает перестроить состав таким образом, чтобы получившееся слово было лексикографически наименьшим из всех возможных, но так как он уже наигрался, поэтому может только один раз отцепить какое-то количество кубиков и паровозиком перевезти их в хвост своего состава.

Какое слово получится у Витэка?

Входные данные

Первая и единственная строка содержит исходное слово. Кубики у Витэка только из заглавных букв латинского алфавита и их количество не превышает [latex]500000[/latex].

Выходные данные

Слово, которое образовал Витэк.

Задача взята с сайта e-olymp.

Тесты

Входные данные Выходные данные
CBABC ABCCB
XXXXX XXXXX
ABEABFABBABC ABBABCABEABF
RATOBCQATOBC ATOBCQATOBCR
OROOXOOSTO OOROOXOOST
 LBDEAFAARDEABBAF AARDEABBAFLBDEAF

Алгоритм

В данной задаче из исходного слова, записанного заглавными буквами латинского алфавита, нужно составить наименьшее лексикографическое слово при условии, что мы имеем право всего один раз взять некоторое количество букв с конца слова и перенести их в начало.

Так как мы работаем над упорядоченным алфавитом, то для получения наименьшего лексикографического слова следует из всех возможных для нас перестановок выбрать то слово, которое будет стоять первым при их упорядочивании в лексикографическом порядке.

Нетрудно догадаться, что для этого следует найти наименьший символ в данной строке по номеру вхождения в данный алфавит (в дальнейшем будем называть его минимальным символом) и выполнить сдвиг так, чтобы он оказался в начале. Но следует учесть, что минимальный символ может встречаться в данном слове не один раз, тогда следует построить алгоритм поиска наименьшей подстроки для сдвига.

Так как мы имеем право выбирать подслово только начиная от некоторого символа и до конца строки, то нам следует сравнить все подстроки начинающиеся с вхождения минимального символа и заканчивающиеся в конце слова.

Рассмотрим на произвольно выбранном примере:

                                                               LBDEAFAARDEABBAF                                                                                   

Тогда следует сравнить такие подслова:

AFAARDEABBA
     AARDEABBA
        ARDEABBA
                   ABBAF
                           A

Найти среди них минимальное лексикографическое и передвинуть его в начало слова.

Реализуем описанный выше алгоритм на практике с некоторыми особенностями.

  1. Прочитаем слово.
  2. Найдем минимальный символ в данном слове.
  3. Создадим вектор для хранения индексов вхождения минимального символа (indicesOfMinSymbol) и будем добавлять в него значение только в том случае, если текущий символ является минимальным, а предыдущий нет. (Обратившись к предоставленному примеру, можно заметить, что не имеет смысла отдельно проводить сравнение подслов AARDEABBAF  и ARDEABBAF, так как первое из них явно «выгоднее». Также мы сможем упростить ситуацию и избавиться от большого количества лишних проверок, когда на вход поступает слово состоящее из всех одинаковых символов (например, XXXXX), в котором не нужно выполнять ни единого сравнения и как-либо изменять слово).
  4. Объявим индекс начала текущего наименьшего лексикографического подслова (indexOfMinLexicSubstr) и для каждого значения из заполненного ранее вектора будем сравнивать от иднекса начала текущего наименьшего лексикографического подслова столько символов, сколько осталось до конца строки от текущего индекса вхождения минимального символа, с подстрокой, начинающейся с этого индекса и заканчивающейся в конце слова, с помощью функции compare. (Рассмотрим произвольные подслова из заданного примера: AFAARDEABBAF  и AARDEABBAF. Тогда исходя из пункта 4 следует сравнить подслова AFААRDEABB и AARDEABBAF. Мы имеем полное право выполнить такое упрощение, так как отсутствие следующего символа меньше, чем наличие любого другого символа, и если будет выбрано первое подслово, то второе подслово, стоящее справа от него, автоматически также будет сдвинуто в начало.
    Однако существует немаловажное исключение при построении такого алгоритма. Его удобно рассмотреть на каком-либо конкретном случае, например, OROOXOOSTO. Когда мы дойдем до сравнения подслов OOSTO (на данный момент будет являться минимальным) и О, исходя из выше описанного алгоритма, мы получим равенство подстрок и не изменим индекс начала минимальной строки, тогда ложно будет построена как наименьшая лексикографическая строка из данной OOSTOOROOX. Исправить эту проблему можно дополнительной проверкой того, что выйдет при сдвиге второй (более короткой) подстроки в начало заданного слова. То есть для данного примера, можно заметить, что подслово OROO лексикографически меньше чем OSTO (сравниваем такое же количество символов в начале строки, сколько оставалось до конца у текущей наименьшей лексикографической подстроки).
    Примечание: следует отметить, что даже без  выполнения второй проверки алгоритм проходил все тесты к данной задаче на сайте e-olymp, что может говорить лишь о неполноте тестов.).
  5. И только в том случае, если функция compare в пункте 4 вернула значение больше чем [latex]0[/latex], то есть правое подслово меньше, или же меньше подслово получаемое при сдвиге правой строки в сравнении с текущим наименьшим лексикографическим, тогда изменяем значение индекса минимального лексикографического подслова на текущий индекс вхождения минимального символа.
  6. После прохождения всего вектора, выполняем сдвиг найденного минимального лексикографического подслова в начало, благодаря встроенной функции rotate, и выполняем вывод полученного слова.

Код программы:

Код программы

Засчитанное решение

e-olymp 330. Слово-чемпион

Задано некоторое предложение на неизвестном языке. Назовем слово в нем чемпионом, если оно является палиндромом и количество букв в нем максимально. Буквами алфавита в неизвестном языке являются буквы латинского алфавита и арабские цифры. Гарантируется, что других символов, кроме пробелов и знаков препинания в предложении нет.

Задача взята с сайта e-olymp.

Входные данные

Предложение на неизвестном языке.

Выходные данные

Номер слова-чемпиона.

Тесты

Предложение Номер слова-чемпиона
Oo, it aaa is not bb. 3
Tummut, suuruu 18! 1
Qrtew asd x, pol 123 xcv. 3
Antaa, qor — aapapaa for Saippuakivikauppias kappak! 6
A b C d E f G h 1
NoPalindrome 0
123321 oro 1234554321? 3

Примечание : в ходе решения задачи выяснилось, что, если в предложении присутствуют несколько палиндромов одинаковой длины, следует вывести первый из встретившихся.

Алгоритм

В данной задаче требуется найти в заданном предложении палиндром максимальной длины. Так как нам нужно проводить анализ отдельных слов, то считывать будем по одному слову пока предложение не закончится, при этом храня порядковый номер текущего слова. Однако, следует учесть следующее:

  1. Слово-палиндром может содержать в себе буквы различного регистра, что может помешать при проверке на палиндромность. Во избежание ошибки переведем все слово, например, в нижний регистр с помощью соответствующей функции.
  2. В предложении встречаются знаки препинания, поэтому если последний символ в слове не является буквой латинского алфавита или цифрой (проверку для удобства чтения вынесем в отдельную функцию), заменим его на нуль-символ, чтобы в дальнейшем его не учитывать.

После проведенных операций найдем длину текущего слова и, если она превышает максимальную длину ранее найденного слова-чемпиона, проверим, является ли текущее слово палиндромом. Осуществим это с помощью рекурсивной функции, сравнивающей соответствующие символы в данной строке по индексам. Функция работает до тех пор, пока начальный и конечный индекс не сравняются или поменяются местами (изначально первый индекс (start) равен нулю, а конечный (end) меньше длины строки на единицу), или же соответствующие символы окажутся разными. Если данное слово оказалось палиндромом, храним его порядковый номер в предложении.
Как только предложение завершено, выводим индекс найденного слова-чемпиона, или индекс первого из них, если таковых было несколько.

Код программы:

Код программы

Засчитанное решение

MLoop 3

Используйте метод золотого сечения для того, чтобы отыскать с точностью [latex]\varepsilon[/latex] локальный максимум функции f\left( x \right) = \ln \left(1+ x^{2} - \cos x \right) - e^{\sin \pi x} на отрезке \left[a;b\right].

save

Входные данные

[latex]a, b[/latex] — концы отрезка, на котором требуется найти максимум, и точность [latex]\varepsilon[/latex].

Выходные данные

Точка локального максимума и локальный максимум в формате [latex](x_{max}, y_{max})[/latex].

Тесты

[latex]\varepsilon[/latex] [latex]a[/latex] [latex]b[/latex] [latex](x_{max}, y_{max})[/latex]
[latex]0.001[/latex] [latex]1.05[/latex] [latex]2.2[/latex] [latex](1.74435, 0.951781)[/latex]
 [latex]0.0001[/latex] [latex]1.05[/latex] [latex]2.2[/latex] [latex](1.74417, 0.951781)[/latex]
 [latex]0.0001[/latex]  [latex]5.7[/latex] [latex]8[/latex] [latex](7.57498, 3.68407)[/latex]
 [latex]0.0001[/latex]  [latex]3[/latex] [latex]4[/latex] [latex](3.61901, 2.31289)[/latex]

Алгоритм

Для начала проанализируем данную нам функцию. Найдем ее область определения.

[latex]D(f) = x^2 + 1 + \cos x > 0 [/latex]

[latex]D(f) = x^2 + 1 + \cos x = x^2 + [/latex] [latex]\frac{1}{2}[/latex] [latex] \cos^2[/latex] [latex]\frac{x}{2}[/latex] [latex] > 0[/latex]  [latex]\forall[/latex]  [latex]x[/latex] [latex]\in [/latex] [latex] \mathbb{R}[/latex]

 

Таким образом, функция определена на всей числовой оси и мы имеем право рассматривать функцию для любого значения аргумента (также это видно по графику).
Однако следует помнить о том, что используемый нами метод золотого сечения принадлежит к группе симметричных методов и накладывает некоторые ограничения на исследуемую функцию. Применимость данного метода гарантируется только для непрерывныхунимодальных функций.
Унимодальная функция — это функция, которая монотонна на обе стороны от точки максимума [latex]x_{max}[/latex].

[latex]x_1 \le[/latex] [latex]x_2 \le[/latex] [latex]x_{max}[/latex]   [latex]\Rightarrow[/latex]  [latex]f(x_1) \le[/latex] [latex]f(x_2) \le[/latex][latex]f(x_{max})[/latex]

[latex]x_1 \ge[/latex] [latex]x_2 \ge[/latex] [latex]x_{max}[/latex]   [latex]\Rightarrow[/latex]  [latex]f(x_1) \le[/latex] [latex]f(x_2) \le[/latex][latex]f(x_{max})[/latex]

 

Отсюда следует, что если функция [latex]f(x)[/latex] унимодальна на отрезке [latex][a; b][/latex], то максимум этой функции единственен, а локальные минимумы обязательно располагаются на его концах. Так как данная нам функция не является таковой, то для корректного применения метода и получения желаемого результата мы будем собственноручно задавать такие отрезки, на которых представленная функция унимодальна (их несложно выделить по графику).

Проведя анализ функции, обратимся к самому методу золотого сечения.

Для того чтобы найти определенное значение функции на заданном отрезке, отвечающее заданному критерию поиска (в нашем случае максимум), рассматриваемый отрезок требуется поделить в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки [latex]x_1[/latex] и [latex]x_2[/latex] такие, что

[latex]\frac{b — a}{b — x_1}[/latex] [latex]= \frac{b — a}{x_2 — a} =[/latex] [latex]\varphi[/latex] [latex] = \frac{1 + \sqrt{5}}{2}[/latex]

 

То есть точка [latex]x_1[/latex]  делит отрезок [latex][a; x_2][/latex] в отношении золотого сечения. Аналогично [latex]x_2[/latex] делит отрезок [latex][x_1; b][/latex] в той же пропорции. Для нахождения максимума выполняем следующую последовательность действий:

  1. На первом шаге исходный отрезок делим двумя симметричными относительно его центра точками и находим значение в этих точках.
  2. После чего тот из концов отрезка, к которому среди двух вновь поставленных точек ближе оказалась та, значение в которой минимально, откидываем.
  3. На следующем шаге следует найти всего одну новую точку.
  4. Повторяем до тех пор, пока не будет достигнута заданная точность.

Код программы:

 

 

Ссылки

MLoops24

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n > 0[/latex] (количество столбцов) и [latex] m > 0[/latex] (количество строк).

Входные данные 

Количество столбцов ([latex]n > 0[/latex]) и количество строк ([latex] m > 0[/latex]) в таблице.

Выходные данные

Построенная для данной последовательности таблица с соответствующим количеством столбцов и строк.

Тесты

[latex]n[/latex] [latex]m[/latex] Результат работы программы
1 1 0
2 2
1 6
4 4
5 5
32 5
50  10
10  10

Алгоритм

Для начала определим алгоритм построения предоставленной последовательности. Перед нами так называемая Look-and-Say sequence, начинающаяся с 0. Чтобы получить последующий член последовательности, нам потребуется обратиться к предыдущему и выполнить следующее:

  1. Посчитать количество одинаковых подряд идущих цифр и записать его.
  2. Записать саму эту цифру.

Разберем на примере:

  • Первый член последовательности — [latex]0[/latex] («Основание» последовательности);
  • Второй член последовательности — [latex]10[/latex] («Вижу» один ноль);
  • Третий член последовательности — [latex]1110[/latex] («Вижу» одну единицу и один ноль);
  • Четвертый член последовательности — [latex]3110[/latex] («Вижу» три единицы и один ноль).

Реализуем данное построение на практике. Создадим два вектора для хранения предыдущего и текущего члена последовательности (previousTerm и currentTerm соответственно), а также переменные для хранения номера элемента с которым ведется сравнение (изначально start [latex] = 0[/latex]) и счетчик количества совпадающих элементов (изначально quantity [latex] = 0[/latex]). Запустим цикл от первого до последнего элемента массива previousTerm и выполним ряд действий, а именно:

  1. Пока последующие элементы совпадают с текущим сравниваемым, инкрементируем счетчик.
  2. Как только находиться элемент не совпадающий с текущим сравниваемым, выполняем вывод количества вхождений и само число, также записываем данные значения в вектор currentTerm. Переходим к следующей цифре для сравнения и присваиваем счетчику значение [latex]1[/latex].
  3. Отдельно выполняем предыдущий пункт для последней последовательности цифр или одной цифры, так как нет возможности сравнения с последующими.
  4. Как только один член последовательности полностью построен, обнуляем значения индекса сравниваемой цифры и счетчика. Также очищаем вектотр previousTerm и передаем ему значения вектора currentTerm, очищаем вектор currentTerm.

Теперь наша задача состоит в том, чтобы выполнить правильный вывод таблицы. Основную работу по построению таблицы будет выполнять метод ToPrint, принимающий как параметры заданное количество столбцов, строк, номер текущего столбца, текущей строки и цифру которую нужно вывести на печать (или пробел).
Рассмотрим детали его работы:

  1. При запуске метода сразу же увеличиваем текущий номер столбца, в который записывается символ, на [latex]1[/latex].
  2. Далее проверяем не превышает ли номер текущего столбца возможный. Если это так, то выполняем перевод курсора на новую строку, присваиваем текущему столбцу значение [latex]1[/latex] и инкрементируем значение номера текущей строки.
  3. Если количество строк превышает заданное, заканчиваем работу программы.
  4. В противном же случае выполняем печать символа, если это не пробел в начале строки (если это все же пробел в начале строки, то ничего не печатаем и уменьшаем значение текущего столбца для печати).  Для упрощения вывода пробел передается в метод по его коду в таблице ASCII — [latex]32[/latex]. Мы имеем полное право использовать число [latex]32[/latex] без угрозы ошибки, так как передавать мы будем  только цифры [latex]0, 1, 2, 3[/latex].

Таким образом общий алгоритм работы программы можем сформулировать так:

  1. Считываем заданное количество столбцов ([latex]n > 0[/latex]) и количество строк ([latex] m > 0[/latex]).
  2. Для последующей работы объявляем переменные хранящие значения номера текущего столбца и строки (currentNumberColumn и currentNumberRow соответственно), два вектора для хранения предыдущего и текущего члена последовательности (previousTerm и currentTerm соответственно), а также переменные для хранения номера элемента с которым ведется сравнение (start) и счетчик количества совпадающих элементов (quantity) .
  3. Отправляем в вектор previousTerm значение «основания» последовательности — [latex]0[/latex].
  4. Выводим первый член последовательности и пробел после него (если потребуется).
  5. Далее запускаем бесконечный цикл, так как окончание работы программы предусмотрено в методе ToPrint.
  6. И выполняем последовательное построение членов последовательности (описано выше) и тут же вывод, пока количество строк не превышает заданное.

Код программы:

 

Ссылки

e-olymp 16. Дракон

У каждой [latex]S[/latex]-ножки [latex]1[/latex] голова. Найти количество ног [latex]N[/latex] у [latex]K[/latex]-главого дракона, если у всех вместе [latex]A[/latex] голов и [latex]B[/latex] ног.

Входные данные

4 числа: [latex]S[/latex], [latex]K[/latex], [latex]A[/latex], [latex]B[/latex]. Все числа не превышают [latex]1000[/latex].

Выходные данные

Количество ног у дракона. Если входные данные противоречивы, вывести [latex]-1[/latex], в случае наличия нескольких решений – вывести любое из них.

Задача взята с сайта e-olymp.

Тесты

[latex]S[/latex] [latex]K[/latex] [latex]A[/latex] [latex]B[/latex] [latex]N[/latex] Комментарий
4 7 35 36 2 7 многоножек и 4 2-ногих дракона
10 3 10 34 8 1 многоножка и 3 8-ногих дракона
44 17 37 132 0 3  многоножки и 2 0 — ногих дракона
4 19 42 42 13 4 многоножки и 2 13 — ногих дракона
1 0 1 1 0 1 многоножка и 1 0 — ногий дракон
5 8 3 6 -1 Количество голов в сумме меньше чем у одного дракона
5 17 6 2 -1 Количество ног в сумме меньше чем у одной многоножки

Алгоритм

Для начала введем несколько дополнительных параметров. Обозначим количество имеющихся драконов через [latex]D[/latex], а количество многоножек как [latex]M[/latex]. Внесем имеющиеся данные в таблицу для удобства построения решения.

Дракон Многоножка
 Один Несколько  Одна  Несколько
 Голов Ног  Голов Ног Голов  Ног  Голов  Ног
[latex]K[/latex] [latex]N[/latex] [latex]KD[/latex] [latex]ND[/latex] [latex]1[/latex] [latex]S[/latex] [latex]M[/latex] [latex]SM[/latex]

Воспользуемся полученной таблицей и промоделируем сложившуюся ситуацию в виде системы уравнений:
[latex] \left\{\begin{matrix}
KD + M = A & \\
ND + SM = B &
\end{matrix}\right.[/latex]

Выразим из первого уравнения количество многоножек и подставим во второе уравнение:
[latex] \left\{\begin{matrix}
A — KD = M & \\
ND + S(A — KD) = B &
\end{matrix}\right.[/latex]

Раскрыв скобки, преобразуем выражение во втором уравнении:
[latex] \left\{\begin{matrix}

A — KD = M & \\
B — SA = D(N — SK) &
\end{matrix}\right.[/latex]

Теперь мы можем выразить количество драконов:
[latex] \left\{\begin{matrix}

A — KD = M & \\
\frac{B — SA}{N — SK} = D &
\end{matrix}\right.[/latex]

Учитывая тот факт, что мы работаем не просто с системой уравнений, а с величинами имеющими определенный логический смысл, проведем анализ полученного результата:

  1. [latex]D[/latex] — количество драконов, следовательно, это положительное целое число.
  2. Выполняя деление мы предполагаем, что [latex]N — SK[/latex] [latex]\neq[/latex] [latex]0[/latex]. Следует проверить имеет ли данный случай смысл и решение в контексте условия задачи.
    Вернемся к системе считая, что  [latex]N = SK[/latex]:
    [latex] \left\{\begin{matrix}A — KD = M & \\
    ND + S(A — KD) = B &
    \end{matrix}\right.[/latex][latex] \left\{\begin{matrix}A — KD = M & \\
    SKD + SA — SKD = B &
    \end{matrix}\right.[/latex][latex] \left\{\begin{matrix}A — KD = M & \\
    SA = B &
    \end{matrix}\right.[/latex]
    Приходим к выводу, что, при условии [latex]SA = B[/latex], задача гарантировано имеет решение вида [latex]N = SK[/latex].
  3. Теперь оценим знак полученного нами выражения:
    [latex]\frac{B — SA}{N — SK}[/latex] [latex]> 0[/latex] [latex] \Rightarrow[/latex] [latex](B — SA > 0[/latex] [latex]\wedge[/latex] [latex]N — SK > 0)[/latex]  [latex]\vee[/latex] [latex](B — SA < 0[/latex] [latex]\wedge[/latex] [latex]N — SK < 0)[/latex].
    Оценим значение [latex]B — SA [/latex]:
    [latex]B — SA = ND +SM — SA = ND +S(M — A) [/latex]
    [latex]M[/latex] — количество голов у одной многоножки, [latex]A[/latex] — общее количество голов [latex] \Rightarrow[/latex] [latex]M — A <= 0[/latex] , делаем вывод, что
    [latex]B — SA <= 0[/latex]  [latex]\forall[/latex] [latex]B, S, A[/latex] [latex] \Rightarrow[/latex] [latex]N — SK <= 0[/latex] [latex] \Rightarrow[/latex] [latex]N <= SK [/latex]

Анализ условия задачи окончен. Перейдем к реализации решения, принимая во внимание все  условия и ограничения полученные в процессе размышлений.
Запустим цикл от [latex]0[/latex] до [latex]SK[/latex] (выполнять цикл далее не имеет смысла, так как там не будет найдено ни одного решения), который перебирает количество ног дракона. Объединим все получившиеся ограничения:

  1. Прежде всего выполняем проверку для избежания деления на [latex]0[/latex]. (Условие проверки : [latex]SA = B[/latex]  [latex] \Rightarrow[/latex]  выводим результат [latex]N = SK [/latex] и заканчиваем работу программы).
  2. Иначе выполняем ряд последовательных проверок для текущего [latex]N[/latex] в цикле:
    • [latex]\frac{B — SA}{N — SK}[/latex] — целая величина. (Условие проверки : [latex]B — SA[/latex] делится нацело на [latex]N — SK[/latex])
    • Количество ног драконов не превышает общее количество ног минус количество ног одной многоножки (имеется хотя бы одна многоножка, которая имеет [latex]S[/latex] ног). (Условие проверки: [latex]B — S >= DN[/latex])
    • Количество голов драконов меньше чем общее количество голов (имеется хотя бы [latex]1[/latex] многоножка с [latex]1[/latex] головой). (Условие проверки: [latex]A > DK[/latex])

Как только выполняются все вышеописанные условия из пункта 2, выполняем вывод текущего количества ног дракона и заканчиваем работу программы, в противном случае выводим [latex]-1[/latex], так как данные противоречивы.

Примечание: в ходе решения выяснилось, что автор задачи предполагает существование 0 — ногих драконов, 0 — ногих многожек и т.д. Эти условия повлияли на вид некоторых неравенств.

Код программы:

Код программы
Засчитанное решение

Mif 17.20

Задача. Принадлежит ли точка [latex](x, y)[/latex] фигуре на рисунке?

1

Входные данные

Координаты точки в формате [latex](x, y)[/latex] ([latex]x, y[/latex] — действительные числа).

Выходные данные 

Вывести «YES», если точка принадлежит фигуре, и «NO» в противоположном случае.
(Точку, которая находится на контуре, также считаем принадлежащей данной фигуре).

Тесты

[latex]x[/latex] [latex]y[/latex]    Результат
0 0 YES
-5 -5 YES
0 2.5 YES
3.5 4.2 YES
-4 -2.7 YES
3 -4 NO
-2 -1.5 NO
1 6 NO
3.5 0.5 NO
1000 2 NO

 

Решение

Проанализировав фигуру, можно определить, что она не симметрична, хотя данное свойство было бы нам полезно. Однако мы имеем полное право выполнить параллельный перенос фигуры на [latex]0.5[/latex] единиц влево. Рассмотрим текущее расположение фигуры.

201Работать с фигурой стало проще, благодаря симметричности относительно начала координат [latex]O[/latex]. Для того чтобы не противоречить данному условию из-за выполненного сдвига, как только считываем координаты, уменьшаем абсциссу на [latex]0.5[/latex] единиц.
(На рисунке выделены основные данные, обозначенные определенными константами, которые понадобятся нам в ходе решения).

Для определения принадлежности точки фигуре будем постепенно убирать те области, в которых точка явно не может принадлежать фигуре:

  1. В первую очередь исключим все точки, у которых модули значений координат превышают [latex]5.5[/latex] по оси абсцисс или [latex]5[/latex] по оси ординат.
    (Условие проверки :  [latex]|y| > c [/latex]  [latex]\vee[/latex]  [latex]|x| > d [/latex] )
  2. Осталось рассмотреть две области, в которых точка не принадлежит фигуре тогда и только тогда, когда лежит ниже чем прямая [latex]y = 2[/latex] и правее [latex]x = 1.5[/latex] или же выше чем [latex]y = -2[/latex] и левее [latex]x =- 1.5[/latex].
    (Условие проверки :  [latex](x < -b[/latex]   [latex]\wedge[/latex]  [latex]y > -a)[/latex]  [latex]\vee[/latex]  [latex](x > b[/latex]  [latex]\wedge[/latex]  [latex]y < a)[/latex])
  3. Если хотя бы одно из предыдущих условий выполнилось, приходим к заключению, что точка не принадлежит данной фигуре. Выводим «NO».
    В противном случае выводим «YES».

Код программы:

 

Код программы

Ю2.15

Задача.  Общая точка

Два отрезка на плоскости заданы координатами своих концов. Определить имеют ли эти отрезки общие точки.

Замечание. Необходимо рассмотреть различные случаи взаимной ориентации отрезков: на одной прямой, на параллельных или пересекающихся прямых. Тестирование должно предусмотреть все такие ситуации.

Входные данные

Координаты концов двух отрезков [latex]AB, CD [/latex]  в формате [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex] ([latex]x_i, y_i[/latex] — действительные числа).

Выходные данные

Расположение отрезков, а именно:

  • «Intersect at point [latex](x, y)[/latex]»
  • «Don’t intersect» 
  • «Paralell» 
  • «On the same line, but don’t intersect»
  • «Overlap»  (Находятся на одной прямой и хотя бы одна из точек совпадает)

Тесты

 Координаты [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex]   Расположение отрезков
1 1 5 4 1 3 5 3 Intersect at point (3.66667, 3)
-7 2 -4 2 -6 3 -3 3 Paralell
1 2 3 2 2 2 6 2 Overlap
1 2 4 2 5 2 7 2 On the same line, but don’t intersect
1 2 4 4 2 1 5 3 Paralell
1 1 4 2 7 3 10 4 On the same line, but don’t intersect
1 1 5 3 5 3 7 4 Overlap
1 1 5 4 1 4 5 2 Intersect at point (3.4, 2.8)
1 1 2 4 3 2 6 4 Don’t intersect

 

 Координаты [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex]   Расположение отрезков
1 1 1 5 3 2 3 4 Paralell
1 2 4 5 2 2 2 5 Intersect at point (2, 3)
2 1 2 2 2 4 2 6 On the same line, but don’t intersect
2 1 2 5 1 2 4 2 Intersect at point (2, 2)
1 2 4 2 2 3 2 5 Don’t intersect

 

Алгоритм решения

Представленный в данной программе алгоритм достаточно объемный и содержит в себе большое количество вариантов поведения программы, поэтому разбирать его будем постепенно.
Начнем с функций, которые понадобятся в дальнейшем ходе решения:

  1. areCollinear — функция, принимающая координаты векторов, задаваемых отрезками, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае.
    ( Основная формула:  [latex]\frac{x_1}{x_2}[/latex] [latex]=[/latex] [latex]\frac{y_1}{y_2}[/latex] )
  2. getMin — возвращает минимум двух чисел.
  3. getMax —  возвращает максимум двух чисел.
  4. projectionsIntersect — функция, принимающая абсциссы или ординаты двух векторов и возвращающая логическое значение true, если проекции отрезков на соответствующую ось пересекаются, и false в противном случае.
  5. getSlope — функция, принимающая координаты отрезка и возвращающая угол наклона прямой, на которой он расположен.
    ( Основная формула:  [latex]\frac{y_2 — y_1}{x_2 — x_1}[/latex] )
  6. getYIntercept — функция, принимающая координаты отрезка и возвращающая свободный член уравнения прямой, на которой он расположен.
    ( Основная формула:  [latex]\frac{x_2y_1 — x_1y_2}{x_2 — x_1}[/latex] )
  7. getCos — функция, принимающая координаты двух векторов и возвращающая косинус угла между ними.
    ( Основная формула:  [latex]\frac{x_1x_2 + y_1y_2}{\sqrt(x_1^2 + y_1^2) + \sqrt(x_2^2 + y_2^2)}[/latex] )

Перейдем к основной части программы. Сразу следует оговорить, что последующее решение будет базироваться на векторах и работе с уравнением прямой вида [latex] y = kx + b [/latex], поэтому для удобства отдельно заведем переменные для координат векторов соответствующих отрезкам и значений вычисленных коэффициентов и свободных членов уравнений прямых.  Одной из главных проблем на пути решения стали отрезки располагающиеся на прямых вида [latex]x = a [/latex], ведь если обратится к пунктам 5, 6 можно заметить, что в таких случаях мы получим исключение из-за деления на ноль. Этим вызвано вынужденное разделение программы на два блока — где ни один из отрезков не располагается параллельно оси ординат и когда хотя бы один из них параллелен.  Это удается достичь благодаря инициализации логических переменных, принимающих значение true, когда отрезок расположен на прямой [latex]x = a[/latex]. Также изначально подсчитываем значения переменных yIntercept1, yIntercept2, slope1, slope2 тогда, когда это возможно, так как они будут задействованы в дальнейшем.

Теперь мы можем приступить к общему рассмотрению сложившейся ситуации, когда прямые параллельные оси ординат отсутствуют:

  1. Решим систему уравнений для двух заданных прямых и таким образом найдем точку их пересечения.
    [latex] \left\{\begin{matrix}
    k_1x + b_1 = y & \\
    k_2x + b_2 = y &
    \end{matrix}\right.[/latex]
  2. Найдя точку с координатами [latex](xIntersection,yIntersection)[/latex], следующим шагом станет проверка : принадлежит ли найденная точка имеющимся отрезкам. Для этого воспользуемся формулой скалярного произведения и определим косинус угла между векторами с началом в точке [latex](xIntersection, yIntersection)[/latex] и концами в соответствующих концах отрезка. Выполняем ее для двух отрезков. Если в обоих случаях найденный косинус будет [latex] \le[/latex] [latex]0[/latex], то точка находится на двух отрезках одновременно и  является их пересечением. Выводим сообщение «Intersect at point [latex](xIntersection, yIntersection)[/latex]«.
  3. В случае, если такая точка не найдена в следствие определенных причин, рассмотрим следующие возможные ситуации:
    а) При условии, что равны свободные члены уравнения прямых и точка не была найдена, можем проверить утверждение, что рассматриваемые прямые совпадают, а заданные отрезки находятся на ней. Здесь требуют рассмотрения  два варианта: отрезки накладываются, если проекции отрезков на ось абсцисс накладываются друг на друга, или же отрезки находятся на одной прямой и не пересекаются. Выводим соответствующее сообщение : «Overlap»/»On the same line, but don’t intersect».
    б) 
    Если свободные члены не равны и не выполнилось ни одно из предыдущих утверждений, приходим к выводу, что возможно отрезки, которые задают вектора, параллельны. Выполняем проверку на коллинеарность , в случае подтверждения предположения выводим сообщение : «Parallel».
    в) 
    Пройдя через все вышеупомянутые проверки и не получив логического значения true, определяем, что данные отрезки не пересекаются и не удовлетворяют ни одному из особенных случаев. Выводим сообщение : «Don’t intersect».Таким образом рассмотрение общего случая окончено. Перейдем ко второй ситуации:
  1. Если оба отрезка расположены на прямых вида [latex]x = a[/latex], то имеем следующие варианты:
    а) Если отрезки расположены на одной прямой и их проекции на ось ординат пересекаются, выводим сообщение : «Overlap».
    б) 
    Если отрезки расположены на одной прямой и их проекции на ось ординат не пересекаются, выводим сообщение : «On the same line, but don’t intersect».
    в) Если отрезки расположены не на одной прямой, выводим сообщение «Paralell».
  2. При условии, что только одна из прямых имеет вид [latex]x = a[/latex], рассмотрим следующие ситуации:
    а)Только одна из прямых имеет вид [latex]x = a[/latex] и обе имеют коэффициент угла наклона равный [latex]0[/latex]. Перед нами две прямые вида: [latex] y = b[/latex] и  [latex]x = a [/latex]. Выполняем смену между соответствующими координатами, чтобы не дублировать код для двух аналогичных ситуаций и рассматриваем только одну из них. Нетрудно заметить, что единственным решением является точка [latex](x_3/x_4, y_1/y_2)[/latex] . Используя метод getCos, выполняем уже описанную выше проверку на принадлежность точки отрезку. Если да — выводим сообщение : «Intersect at point [latex](x_3, y_1)[/latex]», в противном случае : «Don’t intersect».
    б) Однако, ни одна из предыдущих проверок могла не выполниться, так как существует еще одно расположение отрезков на прямых [latex] y = kx + b [/latex] и [latex]x = a [/latex]. Выполняем аналогичную операцию по смене координат во избежание дублирования кода. Единственным решением данной системы может являться точка [latex](x3/x4 + yIntercept1, x3/x4)[/latex]. Повторяем операции аналогичные последним из пункта б). Выводим сообщение: «Intersect at point [latex](x3 + yIntercept1, x3)[/latex]» или «Don’t intersect».
    (В последних двух пунктах несколько раз координаты были записаны через черту, что , вероятно, требует пояснения: в этих ситуациях наблюдалось равенство и какую координату мы выберем не существенно).

Код программы:

Код программы

Аналогичная задача на сайте e-olymp:
839. Пересечение отрезков (Засчитанное решение)

e-olymp 22. «Зеркально простые» числа

Назовем число «зеркально простым», если само число является простым, и простым является число, записанное теми же цифрами в обратном порядке.

Найти количество «зеркально простых» чисел на промежутке от [latex]a[/latex] до [latex]b[/latex].

Входные данные

Два числа [latex]a[/latex] и [latex]b[/latex] ( [latex]1[/latex][latex]\le[/latex] [latex]a[/latex], [latex]b[/latex] [latex]\le[/latex] [latex]10000[/latex]).

Выходные данные

Вывести количество «зеркально простых» чисел на промежутке от [latex]a[/latex] до [latex]b[/latex] включительно.

Задача взята с сайта e-olymp.

Тесты

 Границы промежутка   Количество «зеркально простых» чисел
1  10 4
100  200 12
1008 1230 19
3340  3950 31
9900 10000 4

 

Алгоритм

Перед нами была поставлена задача реализовать поиск всех «зеркально простых» чисел на заданном промежутке. Проверив в правильном ли порядке введены границы промежутка, организуем последовательный анализ для каждого числа из промежутка в теле главного цикла :

  1. Инициализируем две логические переменные, значение которых отвечает за прохождение теста на простоту самим числом и «зеркальным» соответственно.
  2. Методом последовательного перебора делителей определяем является ли данное число простым. Если данное утверждение истинно, переходим к последующим пунктам. В противном случае переходим на новый виток главного цикла.
  3. Выполняем последовательную сборку числа, записанного в обратном порядке.
  4. Проводим аналогичную проверку на простоту для «зеркального» числа.
  5. При условии, что это число также является простым, инкрементируем счетчик.

Достигнув верхней границы промежутка, выводим количество «зеркально простых» чисел.

Код программы:

Код программы

Засчитанное решение

ML19

Задача. Известна длина окружности. Найти площадь круга, ограниченного этой окружностью.

Тесты

Длина окружности Точность  Результат работы программы
0 3 Невозможно выполнить для вырожденной окружности
-1 8 Ошибка ввода данных
34 -5 Ошибка ввода данных
25 18 Вывод с заданной точностью невозможен. Максимально возможная точность 13
25 13 49.7359197162173
83 5 548.20920
113.42 3 1 023.692
12 345 678 3 Вывод с заданной точностью невозможен. Максимально возможная точность 1
12 345 678 1 12 128 861 224 697.9
1 000 000 000 0 Число содержит больше 15 значащих цифр. Точный вывод невозможен

Алгоритм

Перед нами была поставлена задача вычислить площадь круга при условии, что известна длина окружности. Так как в условии не оговорена точность вычислений, выводить результат будем с количеством знаков после запятой, которое задано пользователем.

Для удобства преобразуем известные нам формулы:

[latex]L = 2 \pi \cdot R[/latex]   [latex]S = \pi \cdot R^2 [/latex]  [latex] \longrightarrow[/latex]  [latex]R= \frac{L}{2\pi}[/latex]  [latex]\longrightarrow[/latex]  [latex]S = \frac{L^2}{4\pi}[/latex];

Воспользовавшись данной формулой находим искомую величину. Однако реализуя вывод с заданной точностью, требуется проверить сможет ли используемый нами тип данных double его обеспечить. Принимая во внимание факт, что данный тип хранит не более чем [latex]15[/latex] значащих десятичных цифр осуществляем следующую последовательность действий:

  1. Находим значение переменной possibleAccuracy как разность между максимально возможным количеством значащих цифр (maxAccuracy = [latex]15[/latex]) и имеющемся в данном числе .
  2. Отрицательное значение переменной possibleAccuracy сигнализирует о том, что найденная площадь круга превышает [latex] 10^{15} [/latex]. Следовательно, выводим предупреждение о том, что точный подсчет невозможен даже с нулевой точностью после запятой.
  3. При условии, что запрашиваемая точность превышает максимальную, выводим уведомление и значение максимальной точности.
  4. При ложности  пункта 2 и 3, используя манипулятор setprecision, выводим нужное количество знаков.

Код программы:

 

Код программы

e-olymp 29. Уровень палиндромности

Задано натуральное [latex]M[/latex]. Если число не палиндром – записываем его в обратном порядка и слагаем с заданным. Действия повторяем до тех пор, пока не получим число-палиндром. Количество выполненных операций назовем уровнем палиндромности заданного числа.

Найти уровень палиндромности заданного числа [latex]M[/latex].

Входные данные

Единственное число [latex]M[/latex] ([latex]0[/latex] [latex] <[/latex] [latex]M[/latex] [latex] <[/latex] [latex]10000[/latex]).

Выходные данные

Единственное число – уровень палиндромности.

Задача взята с сайта e-olymp.

Тесты

  Входные данные   Выходные данные
1 0
79 6
101 0
198 5
865 2
9998 6

Алгоритм

В данной задаче для заданного числа требуется определить  уровень его палиндромности — количество раз, которое придется просуммировать его с обратным ему числом до получения палиндрома.

  1. Для начала инициализируем счетчик, который хранит в себе текущее значение уровня палиндромности, и логическую переменную, значение которой ложно до тех пор пока палиндром не найден. Данное условие и будет критерием для выполнения тела основного цикла.
  2. Присвоив значения переменным в цикле, выполняем последовательный разбор введенного числа на цифры и сборку «зеркального» числа.
  3. Проверяем равенство числа и ему обратного.
  4. Выполнение условного оператора сигнализирует о том, что палиндром найден, следовательно выводим «уровень», изменяем значение логической переменной на противоположное и выходим из цикла.
  5. В противном случае суммируем текущее число и «зеркальное», инкрементируем счетчик.
  6. Повторяем пункты 2, 3, 5 до истинности пункта и перехода к 4.

Код программы:

 

Код программы

Засчитанное решение

e-olymp 126. Номер квартиры

Задача. Многоквартирный дом имеет [latex]N[/latex] квартир, [latex]P[/latex] подъездов и [latex]Q[/latex] этажей, причем на каждом этаже каждого подъезда имеется одинаковое количество квартир. Определить в каком подъезде и на каком этаже находится квартира с заданным номером [latex]K[/latex].

Входные данные

В единственной строке файла записаны значения [latex]N[/latex], [latex]P[/latex], [latex]Q[/latex], [latex]K[/latex]. [latex]1[/latex] ≤ [latex]K[/latex] ≤ [latex]N[/latex] ≤ [latex]1000[/latex], [latex]P\cdot Q[/latex] ≤ [latex]N[/latex].

Выходные данные

В единственную строку файла нужно вывести номер подъезда и этаж, на котором находится квартира с номером [latex]K[/latex].

Задача взята с сайта e — olymp.

Тесты

  Входные данные    Выходные данные
      250   5    5     1                  1  1
        30   2    5     27                  2  4
      300  3    10   111                  2  2
        80  5     4     77                  5  4
        98  7     2     39                  3  2
        90  3     15   90                  3  15

Перед нами была поставлена задача определить в доме с заданным количеством квартир, подъездов и этажей положение конкретной квартиры, а именно указать номер подъезда и этаж. Для дальнейшего хода решения определим две целочисленные переменные — flatEntrance (количество квартир в одном подъезде) и flatFloor (количество квартир на одном этаже). Найдем номер подъезда получив целую часть от деления номера квартиры на количество квартир в одном подъезде. Далее выполняем проверку остатка от деления, если он отличен от нуля, то это указывает на то, что квартира находится уже в следующем подъезде. В таком случае инкрементируем переменную entrance.

Для нахождения номера этажа поступим аналогично. Однако следует проверить не делится ли номер квартиры на количество квартир в одном подъезде нацело, если да — она располагается на последнем этаже. Если этого не сделать, то в последующей формуле получим [latex]0[/latex]. В общем случае номер этажа находим поделив остаток от деления номера квартиры на количество квартир в подъезде на количество квартир на этаже (учитываем, что каждый новый подъезд предполагает продолжение нумерации с первого этажа). И снова выполняем проверку остатка от деления. При надобности инкрементируем переменную floor.

Код программы:

Следует отметить, что упростить программу и избавиться от двух условных операторов можно подключив библиотеку math.h и воспользовавшись функцией ceil() — округлением до ближайшего большего целого числа. Тогда код программы выглядит так:

Код программы
Засчитанное решение