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 |
Illustration for the test №3
Illustration for the test №4
Illustration 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 &order, unsigned int &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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include <ctime> #include <string> #include <vector> #include <iostream> #include <algorithm> using namespace std; const char DELIMITER = '/'; // Delimiter character for the correct accumulation of order struct Visa { vector <unsigned int> listOfSubordinatesForBribe; // Storage of subordinates' indices whose signature is required double bribe; // Required bribe }; struct Official { unsigned int id; // Official id (sequence number in the input stream, starting at one) vector <Visa> listOfRequiredVisas; // Storage of possible variants of visas }; bool isBypassed(Official currentOfficial, string order) { // Return true, if this official is already bypassed bool isBypassed = false; for (auto currentVisa : currentOfficial.listOfRequiredVisas) { for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) { if (order.find(to_string(currentSubordinate) + DELIMITER) != string::npos) { // We are looking we are looking for the presence of at least one subordinate including a separator isBypassed = true; // In the string of previously accumulated order of bypass break; } } } return isBypassed; } void findCheapestWay(Official *listOfOfficials, Official currentOfficial, string &order, unsigned int &minimumBribe) { vector <unsigned int> possibleSumsOfBribes; // Stores all the possible sums of bribes for the current official vector <string> possibleOrdersOfBypassing; // Stores all the possible orders for the current of if (!currentOfficial.listOfRequiredVisas.empty() && !isBypassed(currentOfficial, order)) { int currentSumOfBribes = 0; // Current sum of bribes for current official for (auto currentVisa : currentOfficial.listOfRequiredVisas) { for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) { findCheapestWay(listOfOfficials, listOfOfficials[currentSubordinate], order, minimumBribe); // Recursively call the function for finding the minimum required bribe currentSumOfBribes = minimumBribe; // Store the detected minimum as a current } // For each official we get down to the lower level string currentOrder; // Remember all the officials, that we bypassed to the current bribe currentSumOfBribes = currentVisa.bribe; // Remember the bribe required by the current official as the current sum of bribes for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) { currentOrder += to_string(currentSubordinate) + DELIMITER; } // Remember the current oder for each visa (isn't necessary an order to get the minimum sum of bribes) with delimiter possibleOrdersOfBypassing.push_back(order + currentOrder); // Adding one of the possible orders, including previously accumulated value possibleSumsOfBribes.push_back(minimumBribe + currentSumOfBribes); // Adding one of the possible sums, including value that we get from lower level } // Executes processing for each visa in visas list vector<unsigned int>::iterator iteratorToCurrentMinBribe = min_element(possibleSumsOfBribes.begin(), possibleSumsOfBribes.end()); unsigned int indexOfCurrentMinBribe = distance(possibleSumsOfBribes.begin(), iteratorToCurrentMinBribe);// Find the index of the lowest possible variant in the resulting vector minimumBribe = possibleSumsOfBribes[indexOfCurrentMinBribe]; // This variant will be the smallest by sum of bribes, remember it order = possibleOrdersOfBypassing[indexOfCurrentMinBribe]; // And remember corresponding to minimum bribe order } // Executes processing only if the list of visas isn't empty and the official isn't bypassed } int main() { string order; // The order of bypass, that we're looking for string typeOfCommand; // Technical variable for processing the input stream unsigned int quantityOfOfficials; // User-defined number of officials unsigned int minimumBribe = 0; // Minimum sum of bribes to get a license cin >> quantityOfOfficials; Official *listOfOfficials = new Official[quantityOfOfficials + 1]; // Keeps all the officials in the array with the corresponding index unsigned int indexOfOfficial = 1; while (cin >> typeOfCommand) { Official currentOfficial; while (typeOfCommand != "next_official") { Visa currentVisa; vector <unsigned int> requiredSubordinates; while (typeOfCommand != "bribe") { requiredSubordinates.push_back(atoi(typeOfCommand.c_str())); // Before recording convert the input string to the number cin >> typeOfCommand; } // Read the current visa (indices of subbordinates for bribe) currentVisa.listOfSubordinatesForBribe = requiredSubordinates; cin >> typeOfCommand; // Read directly bribe currentVisa.bribe = atoi(typeOfCommand.c_str()); // Before recording convert the input string to the number currentOfficial.listOfRequiredVisas.push_back(currentVisa); // Add current visa to the current official visas list cin >> typeOfCommand; } // Read the current official currentOfficial.id = indexOfOfficial; listOfOfficials[indexOfOfficial] = currentOfficial; // Put all the read data into an array indexOfOfficial++; // Go to read the next official, if present } // Read to the end of the input stream findCheapestWay(listOfOfficials, listOfOfficials[1], order, minimumBribe); // Call the function from main official(first) and accumulate the required values order.push_back('1'); // Add the first official explicitly, cause he hasn't chief, so doesn't participate in the bypassing cout << minimumBribe << endl << order << endl; return 0; } |
Code of the program (here you can analyze the working time of program)
Ok. Accepted.