|
|
Associative Containers
Sets. Set Theory Algorithms
STL5Assoc1°. Given a vector V with an even number of elements. If all values contained in the second half of the vector are included at least once in its first half, output true, otherwise output false. Use the includes algorithm, applying it to two sets (containers of type set), created based on the vector V.
STL5Assoc2°. Given a vector V0, an integer N (> 0) and a set of vectors V1, …, VN. It is known that the size of vector V0 does not exceed the size of any of the vectors V1, …, VN. Find the number of vectors VI, I = 1, …, N, that contain all elements of the vector V0 (ignoring their repetitions). Use the includes algorithm, applying it in a loop to two sets, one of which is created based on the vector V0, and the other on the current iteration contains the elements of the current vector VI, I = 1, …, N.
STL5Assoc3°. Given a vector V0, an integer N (> 0) and a set of vectors V1, …, VN. It is known that the size of vector V0 does not exceed the size of any of the vectors V1, …, VN. Find the number of vectors VI, I = 1, …, N, that contain all elements of the vector V0 (taking their repetitions into account). Use the includes algorithm, applying it in a loop to two multisets (containers of type multiset), one of which is created based on the vector V0, and the other on the current iteration contains the elements of the current vector VI, I = 1, …, N.
STL5Assoc4°. Given a string Name and a vector V with an even number of elements. Find all distinct numbers that are included in both the first and the second half of the initial vector, and write them to a text file named Name in ascending order, adding a space character after each number. Use the set_intersection algorithm for two auxiliary sets and an ostream_iterator iterator.
STL5Assoc5°. Given a string Name and a vector V with an even number of elements. Find all distinct numbers that are included in the second half of the initial vector and are absent from the first half. Write the found numbers to a text file named Name in descending order, outputting each number on a new line. Use the set_difference algorithm for two auxiliary sets and an ostream_iterator iterator. To ensure the output of numbers in the required order, use the function object greater when creating the sets and in the algorithm.
STL5Assoc6°. Given vectors V1 and V2. Find all numbers (taking repetitions into account) that are included in at least one of the initial vectors, and output them in ascending order; if, for example, a certain number is included in one vector 3 times and in the other 5 times, then it must be output 5 times. Use the set_union algorithm for two auxiliary multisets and a ptout_iterator iterator.
STL5Assoc7°. Given vectors V1 and V2 with different numbers of elements. Find all numbers (taking repetitions into account) that are included in one of the initial vectors and are absent from the other, and output them in descending order; if, for example, a certain number is included in one vector 3 times and in the other 5 times, then it must be output 2 times. Use the set_symmetric_difference algorithm for two auxiliary multisets and a ptout_iterator iterator. To ensure the output of numbers in the required order, use the function object greater when creating the multisets and in the algorithm.
STL5Assoc8°. Given a vector V, containing at least three distinct numbers. Output all its distinct elements, except the maximum and minimum, in descending order. Use an auxiliary set and the copy algorithm with reverse iterators pointing to the penultimate and first elements of the set, and with a ptout_iterator iterator.
STL5Assoc9°. Solve task STL5Assoc8 without using an auxiliary set. Instead, sequentially use for the initial vector the algorithms sort, unique, and copy.
STL5Assoc10°. Given a vector V, containing at least three distinct numbers. Output all its elements (taking repetitions into account), except the minimum and maximum, in ascending order. Use an auxiliary multiset, its member functions lower_bound and upper_bound, and the copy algorithm with a ptout_iterator iterator.
STL5Assoc11°. Solve task STL5Assoc10 without using an auxiliary multiset. Instead, sequentially use for the initial vector the algorithms sort, lower_bound, upper_bound, and copy.
STL5Assoc12°. Given a vector V. Determine the number of repetitions of each number in the vector V and output all distinct elements of the vector V together with their repetition count (in ascending order of element values); output the repetition count immediately after the value of the corresponding element. Use an auxiliary multiset and a loop in which the member function upper_bound for the multiset and the function distance for its iterators are called.
STL5Assoc13°. Solve task STL5Assoc12 without using an auxiliary multiset and the function distance. Instead, use for the initial vector the algorithm sort and in a loop the algorithm upper_bound and the difference operation for vector iterators.
STL5Assoc14°. Solve task STL5Assoc12 without using the function upper_bound and a loop. Instead, use an auxiliary multiset M and an auxiliary set S (creating them based on the initial vector) and the algorithm for_each for the set S with a parameter — a function object, in which use the member function count of the multiset M.
Maps. Data Grouping and Combining
STL5Assoc15°. Given a vector V. Determine the number of repetitions of each number in the vector V and output all distinct elements of the vector V together with their repetition count (in ascending order of element values); output the repetition count immediately after the value of the corresponding element. Use an auxiliary map M (class map), whose keys are the distinct elements of the vector V, and whose values are the repetition counts of these elements. When filling the map M, do not use conditional constructs (the indexing operation [] and the increment operation are sufficient). Iterate over the elements of the vector V (when filling the map M) and the elements of the map M (when outputting the obtained results) in a loop with an iterator parameter of the corresponding container.
STL5Assoc16°. Solve task STL5Assoc15 using calls to the algorithm for_each for iterating over the elements of the vector V and the map M, or, if the compiler supports the C++11 standard, for loops over container elements.
STL5Assoc17°. Given a vector V, whose elements are English words typed in uppercase letters. Determine the total length of words starting with the same letter, and output all distinct letters from which the elements of the vector V start, together with the total length of these elements (in alphabetical order of letters); output the length immediately after the corresponding letter. Use an auxiliary map M, whose keys are the initial letters of the elements of the vector V, and whose values are the total length of these elements. When filling the map M, do not use conditional constructs (the indexing operation [], the increment operation, and the member function size for strings are sufficient). Iterate over the elements of the vector V (when filling the map M) and the elements of the map M (when outputting the obtained results) in a loop with an iterator parameter of the corresponding container.
STL5Assoc18°. Solve task STL5Assoc17 using calls to the algorithm for_each for iterating over the elements of the vector V and the map M, or, if the compiler supports the C++11 standard, for loops over container elements.
STL5Assoc19°. Given a vector V. Perform grouping of the elements of the vector V, using as the grouping key the last (i.e., rightmost) digit of the element: one group should include all elements of the vector V ending with the same digit (the grouped elements should be arranged in the same order in which they were arranged in the initial vector). Represent the grouping result as a map M, whose keys are the grouping keys, and whose values are vectors containing the grouped elements (thus, the map M should have the type map<int, vector<int>>). Output the obtained map (for each element of the map M, first output the key, and then the elements of the vector associated with it). Use loops with iterator parameters to iterate over container elements.
STL5Assoc20°. Given a vector V, whose elements are English words typed in uppercase letters. Perform grouping of the elements of the vector V, using as the grouping key the first letter of the element: one group should include all elements of the vector V starting with the same letter (the grouped elements should be arranged in alphabetical order taking repetitions into account). Represent the grouping result as a map M, whose keys are the grouping keys, and whose values are multisets containing the grouped elements (thus, the map M should have the type map<char, multiset<string>>). Output the obtained map (for each element of the map M, first output the key, and then the elements of the multiset associated with it). Use the algorithm for_each or, if the compiler supports the C++11 standard, a for loop over container elements to iterate over container elements.
STL5Assoc21°. Given a vector V. Perform grouping of the elements of the vector V, using as the grouping key the last (i.e., rightmost) digit of the element: one group should include all elements of the vector V ending with the same digit (the grouped elements should be arranged in the same order in which they were arranged in the initial vector). Represent the grouping result as a multimap M (class multimap), whose keys are the grouping keys, i.e., the last digits of the elements of the vector V, and whose values are the elements of the vector ending with the corresponding digit (thus, the map M should have the type multimap<int, int>). Output the obtained map (for each element of the map M, first output the key, and then the element of the vector V associated with it; keys may repeat). Use loops with iterator parameters to iterate over container elements.
STL5Assoc22°. Given a vector V, whose elements are English words typed in uppercase letters. Perform grouping of the elements of the vector V, using as the grouping key the last letter of the element: one group should include all elements of the vector V ending with the same letter (the grouped elements should be arranged in the reverse order of their arrangement in the initial vector). Represent the grouping result as a multimap M, whose keys are the grouping keys, i.e., the last letters of the elements of the vector V, and whose values are the elements of the vector ending with the corresponding letter (thus, the map M should have the type multimap<char, string>). Output the obtained map (for each element of the map M, first output the key, and then the element of the vector V associated with it; keys may repeat). Use the algorithm for_each or, if the compiler supports the C++11 standard, a for loop over container elements to iterate over container elements. Remark. To place elements in a group in the reverse order of their arrangement in the vector, it is sufficient to iterate over the elements of the vector V in reverse order (using reverse iterators) when forming the multimap M. The required result can also be obtained with direct iteration over the vector elements if using the variant of the member function M.insert with the first parameter as an iterator ("hint"), specifying as it the return value of the member function M.lower_bound for the corresponding key.
STL5Assoc23°. Given a vector V. In each group of its elements ending with the same digit, find the sum of the values of these elements, excluding the initial element of the group (it is assumed that the elements of the group are arranged in the same order as in the initial vector). If the group consists of a single element, the sum should be 0. For each group, output the corresponding digit and the found sum, ordering the output pairs by increasing digits. Use an auxiliary map M and the grouping variant described in task STL5Assoc19. Use the algorithm accumulate to find the sums.
STL5Assoc24°. Solve task STL5Assoc23 using an auxiliary multimap M and the grouping variant described in task STL5Assoc21. Use the algorithm accumulate to find the sums.
STL5Assoc25°. Solve task STL5Assoc23 without resorting to the preliminary grouping stage. Use a map M with the key — the last digit of the number and the value — the sum of the required numbers (compare with task STL5Assoc15). When forming the map M, use, along with indexing and increment operations, the member function find.
STL5Assoc26°. Given a vector V, whose elements are English words typed in uppercase letters. In each group of its elements ending with the same letter, obtain a string that is the sum of all words from this group, excluding the last word (it is assumed that the elements of the group are arranged in the same order as in the initial vector). When constructing the string, add a space after each word. If the group consists of a single element, the string should remain empty. For each group, output the corresponding letter and the found string, ordering the output pairs in alphabetical order of letters. Use an auxiliary map M and the grouping variant described in task STL5Assoc20. Use the algorithm accumulate to find the sums.
STL5Assoc27°. Solve task STL5Assoc26 using an auxiliary multimap M and the grouping variant described in task STL5Assoc22. Use the algorithm accumulate to find the sums.
STL5Assoc28°. Solve task STL5Assoc26 without resorting to the preliminary grouping stage. Use a map M with the key — the last letter of the word and the value — the sum of the required words (compare with task STL5Assoc17). When forming the map M, organize iteration over the initial vector V from the end and use, along with indexing and increment operations, the member function find.
STL5Assoc29°. Given vectors V1 and V2; all elements in each vector are distinct. Obtain a vector V containing pairs of numbers (of type pair<int, int>), satisfying the following conditions: the first element of the pair belongs to vector V1, the second belongs to vector V2, and both elements end with the same digit. The obtained set of pairs is called the inner join of vectors V1 and V2 by the key defined by the last digits of the initial numbers. The order of the pairs is determined by the original order of the elements of vector V1, and for equal first elements — by the original order of the elements of vector V2. To construct the vector V, perform grouping of the elements of vector V2 by key — the last digit, using the grouping variant with an auxiliary map M, described in task STL5Assoc19, then in a loop over the elements of vector V1, form the required inner join, iterating for each element of vector V1 over the corresponding elements of the map M. Output the size of the obtained vector V and all its elements.
STL5Assoc30°. Solve task STL5Assoc29 by performing grouping of the elements of vector V2 using the method described in task STL5Assoc21 (using an auxiliary multimap M). Use the member function equal_range to search in the multimap M for elements with the required key.
STL5Assoc31°. Given vectors V1 and V2, whose elements are English words typed in uppercase letters, and all words in each vector are distinct. Obtain a vector V that is the inner join of vectors V1 and V2 (see STL5Assoc29), each pair of which contains words of the same length. The order of the pairs is determined by the alphabetical order of the first elements of the pairs, and for equal first elements — by the order of the second elements, which is the reverse of the alphabetical order. To construct the vector V, perform grouping of the elements of vector V2 by key — the length of the word, using the grouping variant with an auxiliary map M of type map<int, set<string>> (compare with task STL5Assoc20), then in a loop over the sorted elements of vector V1, form the required inner join, iterating for each element of vector V1 over the corresponding elements of the map M. Output the size of the obtained vector V and all its elements.
STL5Assoc32°. Given vectors V1 and V2, whose elements are English words typed in uppercase letters, and all words in each vector are distinct. Obtain a vector V that is the inner join of vectors V1 and V2 (see STL5Assoc29), in each pair of which the first word starts with the letter that the second word ends with. The order of the pairs is determined by the alphabetical order of the first elements of the pairs, and for equal first elements — by the order of the second elements, which is the reverse of their order in vector V2. To construct the vector V, perform grouping of the elements of vector V2 by key — the last letter of the word, using the grouping variant with an auxiliary multimap M, described in task STL5Assoc22, then in a loop over the sorted elements of vector V1, form the required inner join, iterating for each element of vector V1 over the corresponding elements of the map M. Output the size of the obtained vector V and all its elements.
STL5Assoc33°. Given vectors V1 and V2; all elements in each vector are distinct and are positive numbers. Obtain a vector V of pairs of type pair<int, vector<int>>, in which the first element of the pair belongs to vector V1, and the second represents the set of those elements of vector V2 that end with the same digit as the first element of the pair (if suitable elements in vector V2 are absent, then the second element of the pair should contain a single element equal to 0). The obtained set of pairs is called the left outer join of vectors V1 and V2 by the key defined by the last digits of the initial numbers. The order of the pairs is determined by the original order of the elements of vector V1; the order of numbers included in the second elements of the pairs is determined by the original order of the elements of vector V2. To construct the vector V, perform grouping of the elements of vector V2 by key — the last digit, using the grouping variant with an auxiliary map M, described in task STL5Assoc19, then in a loop over the elements of vector V1, form the required outer join, iterating for each element of vector V1 over the corresponding elements of the map M. Output the obtained vector V, indicating after the first element of the pair all numbers included in the second element of this pair.
STL5Assoc34°. Given vectors V1 and V2, whose elements are English words typed in uppercase letters, and all words in each vector are distinct. Obtain the left outer join of vectors V1 and V2 (see STL5Assoc33) by key — the length of the word: each element of vector V1 should correspond to the set of all elements of vector V2 having the same length, or a set containing only the empty string if the required elements in vector V2 are absent. The left outer join should be ordered in alphabetical order of elements from vector V1; in each set of elements corresponding to an element from V1, the order should be the reverse of the alphabetical order. Implement the left outer join as a map M with the key — a string and the value — a string set. To construct the map M, perform grouping of the elements of vector V2 by key — the length of the word, using the grouping variant with an auxiliary map M0 of type map<int, set<string, greater<string>>> (compare with task STL5Assoc20), then in a loop over the elements of vector V1, form the required inner join, iterating for each element of vector V1 over the corresponding elements of the map M0. Output the obtained map M, indicating after each of its keys (i.e., an element of vector V1) all words included in the set of values associated with this key (i.e., all corresponding elements of vector V2, or, in their absence, the empty string).
STL5Assoc35°. Given vectors V1 and V2; all elements in each vector are distinct and are positive numbers. Obtain a vector V of pairs of type pair<int, int>, in which the first element of the pair belongs to vector V1, and the second represents the sum of the values of those elements of vector V2 that end with the same digit as the first element of the pair (if suitable elements in vector V2 are absent, then the second element of the pair should be equal to 0). The order of the pairs should be the reverse of the order of the elements of vector V1. When constructing the vector V, use an auxiliary map M, built based on vector V2 and associating each digit with the sum of the elements of vector V2 ending with that digit (regarding variants for constructing the map M, see tasks STL5Assoc23–STL5Assoc25; any variant is allowed).
STL5Assoc36°. Given vectors V1 and V2, whose elements are English words typed in uppercase letters, and all words in each vector are distinct. Obtain a map M in which the key is an element of vector V1, and the value is a string obtained by summing the following set of elements of vector V2: the set includes all words ending with the same letter as the key, excluding the last suitable word. The order of words in the set should correspond to their order in vector V2. When constructing the string, add a space after each word. If the required set is empty, the string should also remain empty. When constructing the map M, use an auxiliary map M0, built based on vector V2 and associating each letter with the sum of the elements of vector V2 ending with that letter, as described above (regarding variants for constructing the map M0, see tasks STL5Assoc26–STL5Assoc28; any variant is allowed).
|
