Определить минимальный по сумме уплаченных взяток допустимый порядок получения подписей

@elenaiv0101 · Регистрация: 03.11.2022

Студворк — интернет-сервис помощи студентам

Ломаю голову и не пойму как написать программу вот такого условия: Есть министерство из N чиновников, где N натуральное число. У каждого из чиновников могут быть как подчиненные, так и начальники, причем справедливы правила: подчиненные моего подчиненного мои подчиненные, начальники моего начальника - мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника не более одного непосредственного начальника.
Для того чтобы получить лицензию на вывоз меди необходимо получить подпись 1-ого чиновника - начальника всех чиновников. Проблема осложняется тем, что каждый чиновник, вообще говоря, может потребовать "визы", т.е. подписи некоторых своих непосредственных подчиненных и взятку - известное количество долларов. Для каждого чиновника известен непустой список возможных наборов "виз" и соответствующая каждому набору взятка. Пустой набор означает, что данный чиновник не требует виз в данном случае. Чиновник ставит свою подпись лишь после того, как ему представлены все подписи одного из наборов "виз" и уплачена соответствующая взятка.
Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость.

Может кто-нибудь сможет подсказать, может у кого есть идея.

@KSergey9 · 22.09.2023, 10:13

Сообщение от elenaiv0101

Вот и разбираюсь, где можно сама.

Пока этого мы не видим.
Приведите то, что вы сделали и уточните где именно возникла проблема.

Алексей1153 · 22.09.2023, 10:43

Сообщение от elenaiv0101

Так же использовать только библиотеку #include <iostream>.

это же не библиотека, а заголовочный файл

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

@SmallEvil · 22.09.2023, 15:49

Сообщение от Алексей1153

можно сначала сделать прототип на том же стандартном векторе

Вот вот. Там как раз нужен динамический массив (он же std::vector() в удобной обертке) для набора Виз и указателей на подчиненных.
Если принять такой жесткий формат ввода как я привел, можно и обычными дин. массивами обойтись, но при этом ещё нужно заботиться об их освобождении.

Добавлено через 3 часа 20 минут
Что бы не быть совсем голословным, вот каркас :
Полностью готовое дерево и все связи между чиновниками.
К формату ввода добавил VN - количество виз в наборе.
1. Написать саму рекурсивную функцию поиска мин суммы, аля пост №2 + проверку мемоизации и ее заполнение.
2. И функцию раскрутки участвующих чиновников, и вывод их снизу вверху, в порядке их подписей на разрешение.
Все.

C++
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 <iostream>
#include <vector>
#include <stack>
#include <queue>
 
struct Node; // предварительное объявление узла дерева, для установления связей 
using visas_list_t = std::vector<Node*>; // тип : список виз
// набор виз и цена набора
struct VisaPack{
    visas_list_t vlist;
    int price;
}; 
 
using visas_pack_list_t = std::vector<VisaPack>; // тип : список наборов виз
using clerks_t = std::vector<Node*>; // тип : список чиновников
struct Clerk{
    int pn; // PN чиновника, нужен для мемоизации
    visas_pack_list_t vplist; // список наборов виз
};
struct Node{
    Clerk *clerk{};    // указатель на чиновника
    clerks_t subclerks{}; // список подчиненных
};
 
// стурктура для сохранения наименьшей суммы и соответствующего набора виз
struct Memo{
    int sum{}; // 0 - не требует взятки
    int vlist{}; // 0 - нет списка виз
};
 
// как бы дерево ;)
class PseudoTree{
public  :
    // clerk - начальник всех начальников, n - количество чиновников
    PseudoTree(Node* clerk, int n)
        : root{clerk}, mem(n){
    }
    void print(){
        if (root)
            print(root);
    }
private :   
    Node* root; // корень дерева
    std::vector<Memo> mem;  // массив промежуточных результатов для каждого обработанного чиновника
    void print(const Node* h, int level=0) {
        for (int i = 0; i < level; i++)
            std::cout << "    ";
        std::cout << h->clerk->pn << std::endl;
        for (int i = 0; i < h->subclerks.size(); i++)
            print(h->subclerks[i], level + 1);
    }
};
 
 
int main(){
    using std::cin;
    int n;
    cin >> n;
    std::vector<Clerk> clerks(n);
    std::vector<Node> nodes(n);
 
    for(int in = 0; in!= n; ++in){
        int pn, k, v;
        cin >> pn >> k >> v;
        clerks[pn].pn = pn;
        clerks[pn].vplist.resize(v);
        nodes[pn].clerk = &clerks[pn];
        nodes[pn].subclerks.resize(k);
        for(int ik = 0; ik!= k; ++ik){
            int kpn;
            cin >> kpn;
            nodes[pn].subclerks[ik] = &nodes[kpn];
        }
 
        for(int iv = 0; iv!= v; ++iv){
            int vn;
            cin >> vn;
            clerks[pn].vplist[iv].vlist.resize(vn);
            for(int ivn = 0; ivn != vn; ++ivn){
                int ivpn;
                cin >> ivpn;
                clerks[pn].vplist[iv].vlist[ivn] = &nodes[ivpn];
            }
            cin >> clerks[pn].vplist[iv].price;
        }
    }
    PseudoTree tree(&nodes[0], n);
    tree.print();
}

Формат ввода :

Code
1
2
3
4
5
6
7
8
9
N
PN K V
<список подчиненных>
<список виз>
   VN
   <список подчиненных в визе>
   <цена визы>
   ...
...

Пример ввода (8 чиновников):

elenaiv0101, хоть что то прояснилось ?
Будут вопросы, задавайте.

@elenaiv0101 · 22.09.2023, 17:18 **[ТС]**

Это нам про Стек рассказали

C++
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
90
91
92
93
94
#include <iostream>
using namespace std;
 
 
struct Node {
 
    int elem;
    Node* next;
 
    Node(int n) // конструктор
    {
        this->elem = n;
        this->next = nullptr;
    }
};
 
struct Stack {
    Node* head;
    Stack()
    {
        head = nullptr;
    }
 
    ~Stack() // деструктор
    {
        empty();
    }
    void push(int elem) //добавление элемента
    {
        Node* temp = new Node(elem);
        if (!temp) {
            cout << "Переполнение стека" << endl;
            return;
        }
        temp->elem = elem;
        temp->next = head;
        head = temp;
    }
 
    void pop() //удаление элеиента
    {
        Node* temp;
        if (head == NULL)
        {
            cout << "Стек пуст!" << endl;
            return;
        }
        else
        {
            temp = head;
            head = head->next;
            free(temp);
        }
    }
 
    void print()// вывод 
    {
        if (head == nullptr) {
            cout << "Стек пуст!" << endl;
            return;
        }
        else
        {
            Node* temp;
            temp = head;
            while (temp)
            {
                cout << temp->elem << ' ';
                temp = temp->next;
            }
            cout << endl;
        }
    }
 
    void empty() //очистка
    {
        Node* p = head;
        Node* p2;
        while (p != nullptr)
        {
            p2 = p;
            p = p->next;
            delete p2;
        }
        head = nullptr;
    }
     bool is_empty()
    {
        if (head == nullptr)
            return true;
        else 
            return false;
    }
};

А это нам про Очередь рассказали

C++
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
90
91
92
93
94
#include <iostream>
using namespace std;
 
 
struct Node {
 
    int elem;
    Node* next;
 
    Node(int n) // конструктор
    {
        this->elem = n;
        this->next = nullptr;
    }
};
 
struct FIFO {
    Node* tail, * head;
    FIFO()
    {
        tail = nullptr;
        head = nullptr;
    }
 
    ~FIFO() // деструктор
    {
        empty();
    }
    void push(int elem) //добавление элемента
    {
        Node* temp = new Node(elem);
        if (is_empty())
        {
            head = tail = temp;
        }
        else {
            tail->next = temp;
            tail = temp;
        }
    }
 
    void pop() //удаление элеиента
    {
        if (is_empty())
        {
            cout << "Очередь пуста!" << endl;
            return;
        }
        Node* temp = head;
        temp = temp->next;
        delete head;
        head = temp;
    }
 
    void print()// вывод 
    {
        if (head == nullptr) {
            cout << "Очередь пуста!" << endl;
            return;
        }
        else
        {
            Node* temp;
            temp = head;
            while (temp)
            {
                cout << temp->elem << ' ';
                temp = temp->next;
            }
            cout << endl;
        }
    }
 
    void empty() //очистка
    {
        Node* p = head;
        Node* p2;
        while (p != nullptr)
        {
            p2 = p;
            p = p->next;
            delete p2;
        }
        head = nullptr;
    }
 
    bool is_empty()
    {
        if (head == nullptr)
            return true;
        else
            return false;
    }
};

@SmallEvil · 22.09.2023, 19:40

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

C++
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
// предварительное объявление узла дерева, 
// для установления связей 
struct Node; 
using visas_list_t = std::vector<Node*>; // тип : список виз
// набор виз и цена набора
struct VisaPack{
    visas_list_t vlist;
    int price;
}; 
 
using visas_pack_list_t = std::vector<VisaPack>; // тип : список наборов виз
using clerks_t = std::vector<Node*>; // тип : список чиновников
struct Clerk{
    int pn; // PN чиновника, нужен для мемоизации
    visas_pack_list_t vplist; // список наборов виз
};
struct Node{
    Clerk *clerk{};    // указатель на чиновника
    clerks_t subclerks{}; // список подчиненных
};
 
// стурктура дл¤ сохранения наименьшей суммы и 
// соответствующего набора виз
struct Memo{
    int sum{-1}; // -1 - не требует взятки
    int vplisti{-1}; // индекс набора виз, -1 - нет список наборов виз пуст
};
 
// как бы дерево ;)
class PseudoTree{
public  :
    // clerk - начальник всех начальников, n - количество чиновников
    PseudoTree(Node* clerk, const std::vector<Clerk>& clerks, int n)
        : root{clerk}, clerks{clerks}, mem(n){
    }
    void print(){
        if (root)
            print(root);
    }
    int FindMinSumAndPrint(){
        if(root){
            int min_sum = get_min_contract(root);
 
            // стек PN всех чиновников поставивших подписи,
            // начиная с самых нижних уровней
            std::stack<std::queue<int>> sq;
            std::queue<int> subclerks;
            // добавили главного чиновника
            subclerks.push(root->clerk->pn);
            do{
                sq.push({}); // добавили пустую очередь
                int n = subclerks.size();
                for(int i = 0; i != n; ++i){
                    auto clerk_pn = subclerks.front();
                    subclerks.pop();
                    sq.top().push(clerk_pn);
                    if (mem[clerk_pn].vplisti != -1){
                        auto& clerk_vlist = (clerks[clerk_pn].vplist[mem[clerk_pn].vplisti]).vlist;
                        int end = clerk_vlist.size();
                        for(int k = 0; k != end; ++k)
                            subclerks.push(clerk_vlist[k]->clerk->pn);
                    }
                }
            }while(!subclerks.empty());
 
            // print clerks 
            while(!sq.empty()){
                auto& q = sq.top();
                while(!q.empty()){
                    std::cout << q.front() << ' ';
                    q.pop();
                }
                std::cout << std::endl;
                sq.pop();
            }
            return min_sum;
        }
        return -1;
    }
private :   
    Node* root; // корень дерева
    // массив промежуточных результатов для каждого 
    // обработанного чиновника
    std::vector<Memo> mem;
    const std::vector<Clerk>& clerks;
    
    void print(const Node* h, int level=0) {
        for (int i = 0; i < level; i++)
            std::cout << "    ";
        std::cout << h->clerk->pn << std::endl;
        for (int i = 0; i < h->subclerks.size(); i++)
            print(h->subclerks[i], level + 1);
    }
    
    int get_min_contract(Node* h){
        if (mem[h->clerk->pn].sum == -1){
            std::vector<int> prices;
            for(auto& contract : h->clerk->vplist){
                int total_price = contract.price;
                for(auto& clerk : contract.vlist)
                    total_price += get_min_contract(clerk);
                prices.push_back(total_price);
            }
            auto min_price_it = std::min_element(prices.begin(), prices.end());
            mem[h->clerk->pn].sum = (min_price_it == prices.end() ? 0 : *min_price_it);
            mem[h->clerk->pn].vplisti = (min_price_it == prices.end() ? -1 : (min_price_it - prices.begin()));
        }
        return mem[h->clerk->pn].sum;
    }
};
 
int main(){
    using std::cin;
    int n;
    cin >> n;
    std::vector<Clerk> clerks(n);
    std::vector<Node> nodes(n);
 
    for(int in = 0; in!= n; ++in){
        int pn, k, v;
        cin >> pn >> k >> v;
        clerks[pn].pn = pn;
        clerks[pn].vplist.resize(v);
        nodes[pn].clerk = &clerks[pn];
        nodes[pn].subclerks.resize(k);
        for(int ik = 0; ik!= k; ++ik){
            int kpn;
            cin >> kpn;
            nodes[pn].subclerks[ik] = &nodes[kpn];
        }
 
        for(int iv = 0; iv!= v; ++iv){
            int vn;
            cin >> vn;
            clerks[pn].vplist[iv].vlist.resize(vn);
            for(int ivn = 0; ivn != vn; ++ivn){
                int ivpn;
                cin >> ivpn;
                clerks[pn].vplist[iv].vlist[ivn] = &nodes[ivpn];
            }
            cin >> clerks[pn].vplist[iv].price;
        }
    }
    PseudoTree tree(&nodes[0], clerks, n);
    tree.print();
    int min_sum = tree.FindMinSumAndPrint();
    std::cout << "Total amount to pay : " << min_sum << std::endl;
}

Добавлено через 3 минуты
Вывод на предоставленном мной примере входных данных :

Code
1
2
3
4
5
6
7
8
9
10
11
12
0
    1
    2
    3
        6
    4
        7
    5
6 7 
3 4 
0 
Total amount to pay : 5

Добавлено через 15 минут
p.s. на графе было бы проще.

@elenaiv0101 · 25.09.2023, 13:28 **[ТС]**

написала программу, а она не работает (в 40 и 67 ругается на n), не знаю как исправить и правильная она, может кто-нибудь проверит, если знает

C++
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
 
using namespace std;
 
// Структура, представляющая чиновника
struct Official {
    int boss; // id начальника
    bool signed_; // подписана ли уже его подпись
    int bribe; // взятка, которую он требует
    // Структура, представляющая визу
    struct Visa {
        bool signed_; // подписана ли уже виза
        int bribe; // взятка, которую требует виза
        Visa* next; // указатель на следующую визу в списке
        Visa(bool signed_, int bribe, Visa* next = nullptr)
            : signed_(signed_), bribe(bribe), next(next) {}
    };
    Visa* visas; // список виз, которые требует чиновник
    Official(int boss = 0, bool signed_ = false, int bribe = 0, Visa* visas = nullptr)
        : boss(boss), signed_(signed_), bribe(bribe), visas(visas) {}
};
 
// Функция для добавления визы в список виз чиновника
void addVisa(Official& official, bool signed_, int bribe) {
    official.visas = new Official::Visa(signed_, bribe, official.visas);
}
 
// Функция для удаления списка виз чиновника
void deleteVisas(Official& official) {
    while (official.visas != nullptr) {
        Official::Visa* visa = official.visas;
        official.visas = visa->next;
        delete visa;
    }
}
 
int main() {
    int n;
    cin >> n; // Считываем количество чиновников
    Official officials[n+1]; // Создаем массив чиновников
    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k; // Считываем количество виз, которые требует чиновник
        Official official;
        for (int j = 0; j < k; ++j) {
            int m;
            cin >> m; // Считываем количество виз, которые требует текущая виза
            Official::Visa* visas = nullptr;
            for (int l = 0; l < m; ++l) {
                int visa;
                cin >> visa; // Считываем id чиновников, которые могут подписать визу
                visas = new Official::Visa(false, 0, visas);
            }
            int bribe;
            cin >> bribe; // Считываем взятку, которую требует чиновник за подписание визы
            addVisa(official, false, bribe); // Добавляем визу в список виз чиновника
            deleteVisas(official); // Удаляем список виз, если он был создан ранее
            official.visas = visas; // Присваиваем список виз чиновнику
        }
        officials[i] = official; // Добавляем чиновника в массив чиновников
    }
    for (int i = 1; i <= n; ++i) {
        int boss;
        cin >> boss; // Считываем id начальника чиновника
        officials[i].boss = boss; // Присваиваем начальника чиновнику
    }
    int toSign[n+1]; // Создаем массив для хранения id чиновников, которые нужно подписать
    int top = 0; // Индекс верхнего элемента в массиве toSign
    toSign[top++] = 1; // Добавляем в стек начальника всех чиновников
    int totalBribe = 0; // Общая сумма взяток
    while (top > 0) { // Пока стек не пуст
        int id = toSign[--top]; // Извлекаем из стека верхний элемент
        Official& official = officials[id]; // Получаем ссылку на чиновника
        if (official.signed_) { // Если подпись уже подписана, пропускаем чиновника
            continue;
        }
        bool allVisasSigned = true; // Флаг, указывающий, подписаны ли все визы чиновника
        Official::Visa* visa = official.visas; // Получаем указатель на первую визу в списке виз чиновника
        while (visa != nullptr) { // Пока есть визы в списке
            if (!visa->signed_) { // Если виза еще не подписана, выставляем флаг allVisasSigned в false
                allVisasSigned = false;
                break;
            }
            visa = visa->next; // Переходим к следующей визе
        }
        if (allVisasSigned) { // Если все визы подписаны
            official.signed_ = true; // Подписываем подпись чиновника
            totalBribe += official.bribe; // Добавляем взятку к общей сумме
            if (official.boss != 0) { // Если у чиновника есть начальник, добавляем его в стек
                toSign[top++] = official.boss;
            }
        }
        else { // Если не все визы подписаны
            toSign[top++] = id; // Добавляем чиновника в стек
            visa = official.visas; // Получаем указатель на первую визу в списке виз чиновника
            while (visa != nullptr) { // Пока есть визы
                if (!visa->signed_) { // Если виза еще не подписана
                    Official& visaOfficial = officials[visa->bribe]; // Получаем ссылку на чиновника, который требует взятку за подписание визы
                    if (visaOfficial.signed_) { // Если чиновник уже подписал подпись
                        visa->signed_ = true; // Подписываем визу
                    }
                    else { // Если чиновник еще не подписал подпись
                        toSign[top++] = visa->bribe; // Добавляем чиновника в стек
                    }
                }
                visa = visa->next; // Переходим к следующей визе
            }
        }
    }
    cout << totalBribe << endl; // Выводим общую сумму взяток
    return 0;
}

@SmallEvil · 25.09.2023, 13:40

Сообщение от elenaiv0101

C++
1
2
cin >> n; // Считываем количество чиновников
    Official officials[n+1]; // Создаем массив чиновников

Размер массива должен быть известным на этапе компиляции.
Вам придется воспользоваться "динамическим массивом".

C++
1
int *officials= new int[n+1];

Со всеми вытекающими последствиями.

@elenaiv0101 · 25.09.2023, 16:00 **[ТС]**

я исправила под динамический массив, это так или нет

C++
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
 
using namespace std;
 
// Структура, представляющая чиновника
struct Official {
    int boss; // id начальника
    bool signed_; // подписана ли уже его подпись
    int bribe; // взятка, которую он требует
    // Структура, представляющая визу
    struct Visa {
        bool signed_; // подписана ли уже виза
        int bribe; // взятка, которую требует виза
        Visa* next; // указатель на следующую визу в списке
        Visa(bool signed_, int bribe, Visa* next = nullptr)
            : signed_(signed_), bribe(bribe), next(next) {}
    };
    Visa* visas; // список виз, которые требует чиновник
    Official(int boss = 0, bool signed_ = false, int bribe = 0, Visa* visas = nullptr)
        : boss(boss), signed_(signed_), bribe(bribe), visas(visas) {}
};
 
// Функция для добавления визы в список виз чиновника
void addVisa(Official& official, bool signed_, int bribe) {
    official.visas = new Official::Visa(signed_, bribe, official.visas);
}
 
// Функция для удаления списка виз чиновника
void deleteVisas(Official& official) {
    while (official.visas != nullptr) {
        Official::Visa* visa = official.visas;
        official.visas = visa->next;
        delete visa;
    }
}
 
int main() {
    int n;
    cin >> n; // Считываем количество чиновников
    Official* officials = new Official[n + 1]; // Создаем динамический массив чиновников
    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k; // Считываем количество виз, которые требует чиновник
        Official official;
        for (int j = 0; j < k; ++j) {
            int m;
            cin >> m; // Считываем количество виз, которые требует текущая виза
            Official::Visa* visas = nullptr;
            for (int l = 0; l < m; ++l) {
                int visa;
                cin >> visa; // Считываем id чиновников, которые могут подписать визу
                visas = new Official::Visa(false, visa, visas);
            }
            int bribe;
            cin >> bribe; // Считываем взятку, которую требует чиновник за подписание визы
            addVisa(official, false, bribe); // Добавляем визу в список виз чиновника
            deleteVisas(official); // Удаляем список виз, если он был создан ранее
            official.visas = visas; // Присваиваем список виз чиновнику
        }
        officials[i] = official; // Добавляем чиновника в массив чиновников
    }
    for (int i = 1; i <= n; ++i) {
        int boss;
        cin >> boss; // Считываем id начальника чиновника
        officials[i].boss = boss; // Присваиваем начальника чиновнику
    }
    int* toSign = new int[n + 1]; // Создаем динамический массив для хранения id чиновников, которые нужно подписать
    int top = 0; // Индекс верхнего элемента в массиве toSign
    toSign[top++] = 1; // Добавляем в стек начальника всех чиновников
    int totalBribe = 0; // Общая сумма взяток
    while (top > 0) { // Пока стек не пуст
        int id = toSign[--top]; // Извлекаем из стека верхний элемент
        Official& official = officials[id]; // Получаем ссылку на чиновника
        if (official.signed_) { // Если подпись уже подписана, пропускаем чиновника
            continue;
        }
        bool allVisasSigned = true; // Флаг, указывающий, подписаны ли все визы чиновника
        Official::Visa* visa = official.visas; // Получаем указатель на первую визу в списке виз чиновника
        while (visa != nullptr) { // Пока есть визы в списке
            if (!visa->signed_) { // Если виза еще не подписана, выставляем флаг allVisasSigned в false
                allVisasSigned = false;
                break;
            }
            visa = visa->next; // Переходим к следующей визе
        }
        if (allVisasSigned) { // Если все визы подписаны
            official.signed_ = true; // Подписываем подпись чиновника
            totalBribe += official.bribe; // Добавляем взятку к общей сумме
            if (official.boss != 0) { // Если у чиновника есть начальник, добавляем его в стек
                toSign[top++] = official.boss;
            }
        }
        else { // Если не все визы подписаны
            toSign[top++] = id; // Добавляем чиновника в стек
            visa = official.visas; // Получаем указатель на первую визу в списке виз чиновника
            while (visa != nullptr) { // Пока есть визы
                if (!visa->signed_) { // Если виза еще не подписана
                    Official& visaOfficial = officials[visa->bribe]; // Получаем ссылку на чиновника, который требует взятку за подписание визы
                    if (visaOfficial.signed_) { // Если чиновник уже подписал подпись
                        visa->signed_ = true; // Подписываем визу
                    }
                    else { // Если чиновник еще не подписал подпись
                        toSign[top++] = visa->bribe; // Добавляем чиновника в стек
                    }
                }
                visa = visa->next; // Переходим к следующей визе
            }
        }
    }
    cout << totalBribe << endl; // Выводим общую сумму взяток
    delete[] officials; // Освобождаем память, выделенную под массив
 
return 0;
}

Добавлено через 1 час 38 минут
еще исправила, но не работает

C++
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
 
using namespace std;
 
// Структура, представляющая чиновника
struct Official
{
    int boss; // id начальника
    bool signed_; // подписана ли уже его подпись
    int bribe; // взятка, которую он требует
    // Структура, представляющая визу
    struct Visa 
    {
        bool signed_; // подписана ли уже виза
        int bribe; // взятка, которую требует виза
        Visa* next; // указатель на следующую визу в списке
        Visa(bool signed_, int bribe, Visa* next = nullptr): signed_(signed_), bribe(bribe), next(next) {}
    };
    Visa* visas; // список виз, которые требует чиновник
    Official(int boss = 0, bool signed_ = false, int bribe = 0, Visa* visas = nullptr): boss(boss), signed_(signed_), bribe(bribe), visas(visas) {}
};
 
// Функция для добавления визы в список виз чиновника
void addVisa(Official& official, bool signed_, int bribe)
{
    official.visas = new Official::Visa(signed_, bribe, official.visas);
}
 
// Функция для удаления списка виз чиновника
void deleteVisas(Official& official)
{
    while (official.visas != nullptr)
    {
        Official::Visa* visa = official.visas;
        official.visas = visa->next;
        delete visa;
    }
}
 
int main() 
{
    setlocale(LC_ALL, "Russian");
    int n;
    cout << "Введите количество чиновников";
    cin >> n; // Считываем количество чиновников
    Official* officials = new Official[n + 1]; // Создаем динамический массив чиновников
    for (int i = 1; i <= n; ++i)
    {
        int k;
        cout << "Введите количество виз, которые требует чиновник";
        cin >> k; // Считываем количество виз, которые требует чиновник
        Official official;
        for (int j = 0; j < k; ++j)
        {
            int m;
            cout << "Введите количество виз, которые требует текущая виза";
            cin >> m; // Считываем количество виз, которые требует текущая виза
            Official::Visa* visas = nullptr;
            for (int l = 0; l < m; ++l) 
            {
                int visa;
                cout << "Введите id чиновников, которые могут подписать визу";
                cin >> visa; // Считываем id чиновников, которые могут подписать визу 
                visas = new Official::Visa(false, visa, visas);
            }
            int bribe;
            cout << "Введите взятку, которую требует чиновник за подписание визы";
            cin >> bribe; // Считываем взятку, которую требует чиновник за подписание визы
            addVisa(official, false, bribe); // Добавляем визу в список виз чиновника
            deleteVisas(official); // Удаляем список виз, если он был создан ранее
            official.visas = visas; // Присваиваем список виз чиновнику
        }
        officials[i] = official; // Добавляем чиновника в массив чиновников
    }
    for (int i = 1; i <= n; ++i)
    {
        int boss;
        cin >> boss; // Считываем id начальника чиновника
        officials[i].boss = boss; // Присваиваем начальника чиновнику
    }
    int* toSign = new int[n + 1]; // Создаем динамический массив для хранения id чиновников, которые нужно подписать
    int top = 0; // Индекс верхнего элемента в массиве toSign
    toSign[top++] = 1; // Добавляем в стек начальника всех чиновников
    int totalBribe = 0; // Общая сумма взяток
    while (top > 0) { // Пока стек не пуст
        int id = toSign[--top]; // Извлекаем из стека верхний элемент
        Official& official = officials[id]; // Получаем ссылку на чиновника
        if (official.signed_)  // Если подпись уже подписана, пропускаем чиновника
        {
            continue;
        }
        bool allVisasSigned = true; // Флаг, указывающий, подписаны ли все визы чиновника
        Official::Visa* visa = official.visas; // Получаем указатель на первую визу в списке виз чиновника
        while (visa != nullptr)  // Пока есть визы в списке
        {
            if (!visa->signed_)  // Если виза еще не подписана, выставляем флаг allVisasSigned в false
            {
                allVisasSigned = false;
                break;
            }
            visa = visa->next; // Переходим к следующей визе
        }
        if (allVisasSigned) // Если все визы подписаны
        {
            official.signed_ = true; // Подписываем подпись чиновника
            totalBribe += official.bribe; // Добавляем взятку к общей сумме
            if (official.boss != 0)  // Если у чиновника есть начальник, добавляем его в стек
            {
                toSign[top++] = official.boss;
            }
        }
        else { // Если не все визы подписаны
            toSign[top++] = id; // Добавляем чиновника в стек
            visa = official.visas; // Получаем указатель на первую визу в списке виз чиновника
            while (visa != nullptr)  // Пока есть визы
            {
                if (!visa->signed_)  // Если виза еще не подписана
                {
                    Official& visaOfficial = officials[visa->bribe]; // Получаем ссылку на чиновника, который требует взятку за подписание визы
                    if (visaOfficial.signed_)  // Если чиновник уже подписал подпись
                    {
                        visa->signed_ = true; // Подписываем визу
                    }
                    else  // Если чиновник еще не подписал подпись
                    {
                        toSign[top++] = visa->bribe; // Добавляем чиновника в стек
                    }
                }
                visa = visa->next; // Переходим к следующей визе
            }
        }
    }
    cout << totalBribe << endl; // Выводим общую сумму взяток
    delete[] officials; // Освобождаем память, выделенную под динамический массив чиновников
    delete[] toSign; // Освобождаем память, выделенную под динамический массив id чиновников, которые нужно подписать
    return 0;
}

@elenaiv0101 · 25.09.2023, 23:40 **[ТС]**

А как этот Ваш код без дерева сделать, препод говорит граф, а дерево не использовать, моя программа так и не заработала. Уже неделю сижу с программой, не пойму как, кто знает не скажет как? Говорит используй динамический или концевой список, стек или очередь.

C++
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
// предварительное объявление узла дерева, 
// для установления связей 
struct Node; 
using visas_list_t = std::vector<Node*>; // тип : список виз
// набор виз и цена набора
struct VisaPack{
    visas_list_t vlist;
    int price;
}; 
 
using visas_pack_list_t = std::vector<VisaPack>; // тип : список наборов виз
using clerks_t = std::vector<Node*>; // тип : список чиновников
struct Clerk{
    int pn; // PN чиновника, нужен для мемоизации
    visas_pack_list_t vplist; // список наборов виз
};
struct Node{
    Clerk *clerk{};    // указатель на чиновника
    clerks_t subclerks{}; // список подчиненных
};
 
// стурктура дл¤ сохранения наименьшей суммы и 
// соответствующего набора виз
struct Memo{
    int sum{-1}; // -1 - не требует взятки
    int vplisti{-1}; // индекс набора виз, -1 - нет список наборов виз пуст
};
 
// как бы дерево ;)
class PseudoTree{
public  :
    // clerk - начальник всех начальников, n - количество чиновников
    PseudoTree(Node* clerk, const std::vector<Clerk>& clerks, int n)
        : root{clerk}, clerks{clerks}, mem(n){
    }
    void print(){
        if (root)
            print(root);
    }
    int FindMinSumAndPrint(){
        if(root){
            int min_sum = get_min_contract(root);
 
            // стек PN всех чиновников поставивших подписи,
            // начиная с самых нижних уровней
            std::stack<std::queue<int>> sq;
            std::queue<int> subclerks;
            // добавили главного чиновника
            subclerks.push(root->clerk->pn);
            do{
                sq.push({}); // добавили пустую очередь
                int n = subclerks.size();
                for(int i = 0; i != n; ++i){
                    auto clerk_pn = subclerks.front();
                    subclerks.pop();
                    sq.top().push(clerk_pn);
                    if (mem[clerk_pn].vplisti != -1){
                        auto& clerk_vlist = (clerks[clerk_pn].vplist[mem[clerk_pn].vplisti]).vlist;
                        int end = clerk_vlist.size();
                        for(int k = 0; k != end; ++k)
                            subclerks.push(clerk_vlist[k]->clerk->pn);
                    }
                }
            }while(!subclerks.empty());
 
            // print clerks 
            while(!sq.empty()){
                auto& q = sq.top();
                while(!q.empty()){
                    std::cout << q.front() << ' ';
                    q.pop();
                }
                std::cout << std::endl;
                sq.pop();
            }
            return min_sum;
        }
        return -1;
    }
private :   
    Node* root; // корень дерева
    // массив промежуточных результатов для каждого 
    // обработанного чиновника
    std::vector<Memo> mem;
    const std::vector<Clerk>& clerks;
    
    void print(const Node* h, int level=0) {
        for (int i = 0; i < level; i++)
            std::cout << "    ";
        std::cout << h->clerk->pn << std::endl;
        for (int i = 0; i < h->subclerks.size(); i++)
            print(h->subclerks[i], level + 1);
    }
    
    int get_min_contract(Node* h){
        if (mem[h->clerk->pn].sum == -1){
            std::vector<int> prices;
            for(auto& contract : h->clerk->vplist){
                int total_price = contract.price;
                for(auto& clerk : contract.vlist)
                    total_price += get_min_contract(clerk);
                prices.push_back(total_price);
            }
            auto min_price_it = std::min_element(prices.begin(), prices.end());
            mem[h->clerk->pn].sum = (min_price_it == prices.end() ? 0 : *min_price_it);
            mem[h->clerk->pn].vplisti = (min_price_it == prices.end() ? -1 : (min_price_it - prices.begin()));
        }
        return mem[h->clerk->pn].sum;
    }
};
 
int main(){
    using std::cin;
    int n;
    cin >> n;
    std::vector<Clerk> clerks(n);
    std::vector<Node> nodes(n);
 
    for(int in = 0; in!= n; ++in){
        int pn, k, v;
        cin >> pn >> k >> v;
        clerks[pn].pn = pn;
        clerks[pn].vplist.resize(v);
        nodes[pn].clerk = &clerks[pn];
        nodes[pn].subclerks.resize(k);
        for(int ik = 0; ik!= k; ++ik){
            int kpn;
            cin >> kpn;
            nodes[pn].subclerks[ik] = &nodes[kpn];
        }
 
        for(int iv = 0; iv!= v; ++iv){
            int vn;
            cin >> vn;
            clerks[pn].vplist[iv].vlist.resize(vn);
            for(int ivn = 0; ivn != vn; ++ivn){
                int ivpn;
                cin >> ivpn;
                clerks[pn].vplist[iv].vlist[ivn] = &nodes[ivpn];
            }
            cin >> clerks[pn].vplist[iv].price;
        }
    }
    PseudoTree tree(&nodes[0], clerks, n);
    tree.print();
    int min_sum = tree.FindMinSumAndPrint();
    std::cout << "Total amount to pay : " << min_sum << std::endl;
}

@SmallEvil · 25.09.2023, 23:50

Сообщение от elenaiv0101

а как этот Ваш код без дерева сделать, препод говорит граф, а дерево не использовать

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

Сообщение от elenaiv0101

моя программа так и не заработала

Ну, разбираться я в ней точно не буду.

Добавлено через 4 минуты

Сообщение от elenaiv0101

препод говорит граф

Думаю на граф я легко переделаю, но не сегодня уже.

@elenaiv0101 · 26.09.2023, 10:14 **[ТС]**

Разбиралась с Вашей задачей, что-то мы вектор проходили, но на простом уровне и не в списках. А как эту задачу сделать без вектора пыталась, но не получилось, не работает.

Добавлено через 43 минуты
А выводится я поняла общая сумма, а не минимальная или я неправильно разобралась. Потому что по условию минимальная

Добавлено через 17 минут
А поняла, что мин сумма, но без вектора пробовала, не получается. Как без вектора, кто знает

Добавлено через 11 минут
убираю std в using std::cin, выдает ошибку; или на что заменить, мы такого не проходили, убираю std, я в начало поставила using namespace std, вот посмотрите

C++
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
 
using namespace std;
 
// предварительное объявление узла дерева, 
// для установления связей 
struct Node;
using visas_list_t = vector<Node*>; // тип : список виз
// набор виз и цена набора
struct VisaPack {
    visas_list_t vlist;
    int price;
};
 
using visas_pack_list_t = vector<VisaPack>; // тип : список наборов виз
using clerks_t = vector<Node*>; // тип : список чиновников
struct Clerk {
    int pn; // PN чиновника, нужен для мемоизации
    visas_pack_list_t vplist; // список наборов виз
};
struct Node 
{
    Clerk* clerk{};    // указатель на чиновника
    clerks_t subclerks{}; // список подчиненных
};
 
// стурктура дл¤ сохранения наименьшей суммы и 
// соответствующего набора виз
struct Memo 
{
    int sum{ -1 }; // -1 - не требует взятки
    int vplisti{ -1 }; // индекс набора виз, -1 - нет список наборов виз пуст
};
 
// как бы дерево ;)
class PseudoTree 
{
public:
    // clerk - начальник всех начальников, n - количество чиновников
    PseudoTree(Node* clerk, const vector<Clerk>& clerks, int n): root{ clerk }, clerks{ clerks }, mem(n) {
    }
    void print() 
    {
        if (root)
            print(root);
    }
    int FindMinSumAndPrint() 
    {
        if (root)
        {
            int min_sum = get_min_contract(root);
 
            // стек PN всех чиновников поставивших подписи,
            // начиная с самых нижних уровней
            stack<queue<int>> sq;
            queue<int> subclerks;
            // добавили главного чиновника
            subclerks.push(root->clerk->pn);
            do
            {
                sq.push({}); // добавили пустую очередь
                int n = subclerks.size();
                for (int i = 0; i != n; ++i) 
                {
                    auto clerk_pn = subclerks.front();
                    subclerks.pop();
                    sq.top().push(clerk_pn);
                    if (mem[clerk_pn].vplisti != -1) 
                    {
                        auto& clerk_vlist = (clerks[clerk_pn].vplist[mem[clerk_pn].vplisti]).vlist;
                        int end = clerk_vlist.size();
                        for (int k = 0; k != end; ++k)
                            subclerks.push(clerk_vlist[k]->clerk->pn);
                    }
                }
            } while (!subclerks.empty());
 
            // print clerks 
            while (!sq.empty()) 
            {
                auto& q = sq.top();
                while (!q.empty())
                {
                    std::cout << q.front() << ' ';
                    q.pop();
                }
                cout << endl;
                sq.pop();
            }
            return min_sum;
        }
        return -1;
    }
private:
    Node* root; // корень дерева
    // массив промежуточных результатов для каждого 
    // обработанного чиновника
    std::vector<Memo> mem;
    const std::vector<Clerk>& clerks;
 
    void print(const Node* h, int level = 0) 
    {
        for (int i = 0; i < level; i++)
            std::cout << "    ";
        std::cout << h->clerk->pn << std::endl;
        for (int i = 0; i < h->subclerks.size(); i++)
            print(h->subclerks[i], level + 1);
    }
 
    int get_min_contract(Node* h)
    {
        if (mem[h->clerk->pn].sum == -1) 
        {
            std::vector<int> prices;
            for (auto& contract : h->clerk->vplist) 
            {
                int total_price = contract.price;
                for (auto& clerk : contract.vlist)
                    total_price += get_min_contract(clerk);
                prices.push_back(total_price);
            }
            auto min_price_it = std::min_element(prices.begin(), prices.end());
            mem[h->clerk->pn].sum = (min_price_it == prices.end() ? 0 : *min_price_it);
            mem[h->clerk->pn].vplisti = (min_price_it == prices.end() ? -1 : (min_price_it - prices.begin()));
        }
        return mem[h->clerk->pn].sum;
    }
};
 
int main()
{
    setlocale(LC_ALL, "Russian");
    using std::cin;
    int n;
    cin >> n;
    vector<Clerk> clerks(n);
    vector<Node> nodes(n);
 
    for (int in = 0; in != n; ++in)
    {
        int pn, k, v;
        cin >> pn >> k >> v;
        clerks[pn].pn = pn;
        clerks[pn].vplist.resize(v);
        nodes[pn].clerk = &clerks[pn];
        nodes[pn].subclerks.resize(k);
        for (int ik = 0; ik != k; ++ik) 
        {
            int kpn;
            cin >> kpn;
            nodes[pn].subclerks[ik] = &nodes[kpn];
        }
 
        for (int iv = 0; iv != v; ++iv) 
        {
            int vn;
            cin >> vn;
            clerks[pn].vplist[iv].vlist.resize(vn);
            for (int ivn = 0; ivn != vn; ++ivn) 
            {
                int ivpn;
                cin >> ivpn;
                clerks[pn].vplist[iv].vlist[ivn] = &nodes[ivpn];
            }
            cin >> clerks[pn].vplist[iv].price;
        }
    }
    PseudoTree tree(&nodes[0], clerks, n);
    tree.print();
    int min_sum = tree.FindMinSumAndPrint();
    cout << " : " << min_sum << endl;
    return 0;
}

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

@SmallEvil · 26.09.2023, 12:26

Сообщение от elenaiv0101

Как без вектора, кто знает

Так всего то без вектора. На граф не нужно переводить ?
Заменить своим типом с конструктором, деструктором и индексатором.

Сообщение от elenaiv0101

окно работы программы сворачивалось

В конце программы.

C++
1
    cin.get(); // press enter to exit

@elenaiv0101 · 26.09.2023, 13:37 **[ТС]**

А мемоизация - это для к запоминанию n значений, у нас такого слова не было, я просто не знаю

Добавлено через 2 минуты
я уже немного с vector разобралась, а так у нас было template

Добавлено через 5 минут
Я вставила cin.get(); // press enter to exit, все равно (у меня такого не было) окно работы программы уходит за окно программы, а не остается на переднем плане, как всегда

return убрала, тоже так

@SmallEvil · 26.09.2023, 13:47

Там остался '\n' с последнего ввода.
Либо еще раз cin.get(), либо запросите явную команду на выход.

C++
1
2
3
std::string word;
while(cin>>word && word!="exit")
   cout << "Input \"exit\" for quit -> ";

Ну и на крайний случай, как костыль :

C++
1
system("pause");

Хотя мне непонятен вопрос про задний план ...

@elenaiv0101 · 26.09.2023, 13:50 **[ТС]**

Извините меня, а что обозначает kpn, ivpn, vn

@SmallEvil · 26.09.2023, 14:07

Сообщение от elenaiv0101

что обозначает kpn, ivpn, vn

kpn - порядковый номер чиновника, данные о котором сейчас вводятся
vn - количество наборов виз текущего чиновника (kpn)
ivpn - порядковый номер чиновника, подпись которого требуется по данной визе

Добавлено через 7 минут

Сообщение от SmallEvil

kpn - порядковый номер чиновника, данные о котором сейчас вводятся

Нет, ошибся.
kpn - это порядковые номера подчиненных данного чиновника.

@elenaiv0101 · 26.09.2023, 14:10 **[ТС]**

а что такое - h

@SmallEvil · 26.09.2023, 14:21

Сообщение от elenaiv0101

а что такое - h

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

Добавлено через 1 минуту

Сообщение от SmallEvil

Но переписывать придется много.

А может и нет ...

@elenaiv0101 · 26.09.2023, 15:08 **[ТС]**

Ввожу ваши данные, а у меня выходит ошибка, и почему сначала 0, это же количество чиновников? Почему дважды повторяется про порядковый номер чиновников. Непонятно.

@SmallEvil · 26.09.2023, 15:14

0 - это просто идентификатор
Я же приводил формат и пример ввода.

Сообщение от elenaiv0101

Почему дважды повторяется про порядковый номер чиновников.

Где ?

Добавлено через 2 минуты
Вы ввели данные о чиновние :
1 2 1
1 - его порядковый номер (так как я для простоты начал отсчет с 0, то больше подходит ID), 2 - количество подчиненных, 1 - количество наборов виз

Новые блоги и статьи Все статьи Все блоги /
Транслитерация текста с кириллицы на латиницу (вариант №3) Maks 15.11.2026 Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .	Транслитерация текста с кириллицы на латиницу (вариант №2) Maks 13.11.2026 Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .	Часы с термометром и праздничным календарем yariko 12.11.2026 Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .	Транслитерация текста с кириллицы на латиницу (вариант №1) Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .

@elenaiv0101 0 / 0 / 0 Регистрация: 03.11.2022 Сообщений: 140

	Определить минимальный по сумме уплаченных взяток допустимый порядок получения подписей 20.09.2023, 22:46. Показов 4947. Ответов 73 Метки нет (Все метки) Ломаю голову и не пойму как написать программу вот такого условия: Есть министерство из N чиновников, где N натуральное число. У каждого из чиновников могут быть как подчиненные, так и начальники, причем справедливы правила: подчиненные моего подчиненного мои подчиненные, начальники моего начальника - мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника не более одного непосредственного начальника. Для того чтобы получить лицензию на вывоз меди необходимо получить подпись 1-ого чиновника - начальника всех чиновников. Проблема осложняется тем, что каждый чиновник, вообще говоря, может потребовать "визы", т.е. подписи некоторых своих непосредственных подчиненных и взятку - известное количество долларов. Для каждого чиновника известен непустой список возможных наборов "виз" и соответствующая каждому набору взятка. Пустой набор означает, что данный чиновник не требует виз в данном случае. Чиновник ставит свою подпись лишь после того, как ему представлены все подписи одного из наборов "виз" и уплачена соответствующая взятка. Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость. Может кто-нибудь сможет подсказать, может у кого есть идея. 0

@elenaiv0101 0 / 0 / 0 Регистрация: 03.11.2022 Сообщений: 140
	26.09.2023, 13:37 [ТС]
	А мемоизация - это для к запоминанию n значений, у нас такого слова не было, я просто не знаю Добавлено через 2 минуты я уже немного с vector разобралась, а так у нас было template Добавлено через 5 минут Я вставила cin.get(); // press enter to exit, все равно (у меня такого не было) окно работы программы уходит за окно программы, а не остается на переднем плане, как всегда return убрала, тоже так Миниатюры 0

@elenaiv0101 0 / 0 / 0 Регистрация: 03.11.2022 Сообщений: 140
	26.09.2023, 13:50 [ТС]
	Извините меня, а что обозначает kpn, ivpn, vn 0

@elenaiv0101 0 / 0 / 0 Регистрация: 03.11.2022 Сообщений: 140
	26.09.2023, 14:10 [ТС]
	а что такое - h 0

@elenaiv0101 0 / 0 / 0 Регистрация: 03.11.2022 Сообщений: 140
	26.09.2023, 15:08 [ТС]
	Ввожу ваши данные, а у меня выходит ошибка, и почему сначала 0, это же количество чиновников? Почему дважды повторяется про порядковый номер чиновников. Непонятно. Миниатюры 0