A. Комерческий калькулятор

Условие

Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берет с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции в долларах равна 5% от числа, которое является результатом операции.

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

Например, пусть нам нужно сложить числа 10, 11, 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в $\$1.05$), потом результат — с 12 ($\$1.65$), и затем — с 13 ($\$2.3$), то всего мы заплатим $\$5$, если же сначала отдельно сложить 10 и 11 ($\$1.05$), потом — 12 и 13 ($\$1.25$) и, наконец, сложить между собой два полученных числа ($\$2.3$), то в итоге мы заплатим лишь $\$4.6$.

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

Идея

Выгоднее всего всегда складывать наименьшие по значению числа. Для этого нам потребуется std::priority_queue, отсортированная по возрастанию (с помощью компаратора std::greater). Из очереди надо брать два верхних числа, а их сумму класть обратно в очередь.

Решение

#include <iostream>
#include <queue>
#include <vector>
#include <iomanip>

#define ull unsigned long long

using namespace std;

int main() {
    priority_queue<ull, vector<ull>, greater<ull>> nums;
    int n;
    ull num;
    double sum, cost = 0;
    cin >> n;
    for (ull i = 0; i < n; ++i) {
        cin >> num;
        nums.push(num);
    }

    while (nums.size() != 1) {
        sum = nums.top();
        nums.pop();
        sum += nums.top();
        nums.pop();

        //Считаем комиссию
        cost += sum * 0.05;

        //Возвращаем результат в очередь
        nums.push(sum);
    }

    cout << fixed << setprecision(2) << cost << endl;
    return 0;
}

B. Берляндская национальная библиотека

Условие

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

Именно сегодня состоялся пилотный запуск автоматизированной системы учёта посетителей читального зала! Сканер системы установлен на входе в читальный зал. Он регистрирует события вида «читатель вошёл в зал», «читатель вышел из зала». Каждому читателю при регистриции в библиотеке присваивается регистрационный номер — уникальное целое число от 1 до $10^6$. Таким образом, система записывает в журнал события двух видов:

  • «$+ r_i$» — читатель с регистрационным номером $r_i$ зашёл в зал;
  • «$- r_i$» — читатель с регистрационным номером $r_i$ вышел из зала.

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

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

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

Идея

Возможны 3 варианта события:

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

Хранить посетителей лучше в std::unordered_set. Решения с std::set, std::map, std::unordered_map также работают.

Решение

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    unordered_set<int> journal;
    int n, reader_num, capacity = 0;
    char event;

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> event;
        cin >> reader_num;

        if (event == '+') {
            // + 1 человек в зале
            // Максимальная вместимость может увеличиться
            journal.insert(reader_num);
            capacity = max(capacity, (int) journal.size());
        } else {
            if (journal.count(reader_num) == 0) {
                // Вышел тот, кого ранее не было в журнале
                // Максимальная вместимость гарантировано увеличивается
                capacity++;
            } else {
                // Вышел тот, кто был в журнале
                // Максимальная вместимость не изменилась
                journal.erase(reader_num);
            }
        }
    }
    cout << capacity << endl;
    return 0;
}

C. Азартная игра

Условие

У каждого из игроков A и B есть по списку, по $𝑛$ целых чисел в каждом. Они оба хотят максимизировать разность между своими очками и очками соперника.

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

В случае если в списке есть несколько одинаковых элементов, только один из них будет задействован в какой-то операции. Например, если список состоит из элементов $\{1,2,2,3\}$ и вы решили выбрать $2$ для следующего хода, только один экземпляр $2$ будет удалён (и добавлен к очкам, если это требуется).

Игру начинает игрок А и игра заканчивается когда оба списка становятся пустыми. Найдите разницу между очками A и B, если оба игрока играют оптимально.

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

Идея

Оптимальная стратегия в данной игре:

  • если максимальное число в твоей очереди больше, чем в очереди соперника, прибавить это число к своим очкам,
  • иначе удалить максимальное число соперника.

Решение

#include <iostream>
#include <queue>

using namespace std;


int main() {

    priority_queue<int> first, second;

    int n, num;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> num;
        first.push(num);
    }
    for (int i = 0; i < n; i++) {
        cin >> num;
        second.push(num);
    }

    long long difference = 0;

    while (!first.empty() or !second.empty()) {

        if (first.empty()) {
            second.pop();
        } else if (!second.empty() and second.top() > first.top()) {
            second.pop();
        } else {
            difference += first.top();
            first.pop();
        }

        if (second.empty()) {
            first.pop();
        } else if (!first.empty() && first.top() > second.top()) {
            first.pop();
        } else {
            difference -= second.top();
            second.pop();
        }
    }
    cout << difference;
    return 0;
}

D. Караблекрушение

Условие

Корабль наткнулся на риф и сейчас терпит крушение. Теперь весь экипаж должен быть срочно эвакуирован. Все $n$ членов экипажа уже выстроились в один ряд (для удобства пронумеруем их всех слева направо натуральными числами от $1$ до $n$) и ждут дальнейших указаний. Однако эвакуировать экипаж полагается не абы как, а в строгом порядке. А именно:

Сначала корабль покидают те члены экипажа, которые являются крысами. Затем корабль покидают женщины и дети (и те, и другие имеют одинаковый приоритет). После этого с корабля эвакуируются все мужчины. Последним тонущий корабль покидает капитан.

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

Для каждого члена экипажа известно, кем он является, а так же его имя. Все члены экипажа имеют различные имена. Определите порядок эвакуации экипажа.

Идея

В этой задаче каждому члену экипажа в зависимости от его роли назначается некоторый приоритет при эвакуации. Приоритет в зависимости от роли выгодно расположить в std::unsorted_map (т.к. скорость доступа $O(1)$).

Далее требуется сформировать приоритетные списки, хранящиеся в std::map<int, std::vector<std::string>> – ассоциативном массиве, где ключ – приоритет, а значение – список имён для эвакуации.

Использовать std::map здесь выгодно благодаря встроенному упорядочиванию ключей

Решение

#include <iostream>
#include <unordered_map>
#include <map>
#include <vector>

using namespace std;

int main() {

    unordered_map<string, int> priority = {{"rat",     0},
                                           {"woman",   1},
                                           {"child",   1},
                                           {"man",     2},
                                           {"captain", 3}};
    int n;
    cin >> n;
    map<int, vector<string>> priority_lists;

    string name, role;
    int p;
    for (int i = 0; i < n; ++i) {
        cin >> name >> role;
        p = priority[role];
        priority_lists[p].push_back(name);
    }


    for (const auto &list : priority_lists)
        for (const auto &element : list.second)
            cout << element << endl;

}

E. Отсортировать строки

Условие

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

Идея

Возможные варианты решений - записать в множество SET, при этом сортировка будет проводиться автоматически после каждой вставки.
Другим вариантом решений является использование очереди с приоритетом, вектора и компаратора greater

Решение

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <set>

#include <string>

using namespace std;

int main() 
{
    priority_queue <string, vector<string>, greater<string>> prq;
    // n - количество строк
    int n;
    // str - сами строки
    string str;

    cin >> n;

    for (int i = 0; i < n; ++i) 
    {
        cin >> str;
        prq.push(str);
    }
    // пока не дойдем до конца (т.к. вытаскиваем элементы, то до момента, когда их не осталось)
    while ( !prq.empty() ) 
    {
        cout << prq.top() << endl;
        prq.pop();
    }


    return 0;
}

F. Суффиксы строки

Условие

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

Идея

Решение задачи выглядит следующим образом.
Берем std::vector или std::set и добавляем в него все суффиксы строки.
Получить из строки суффикс можно с помощью string.substr().
Далее необходимо отсортировать все суффиксы с помощью std::sort для std::vector и вывести полученный результат

Другим вариантом решения является применение очереди с приоритетом и компараторов.

Решение

//#include "pch.h"

#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>

using namespace std;

int main() {
    stack<char> input;

    priority_queue<string> lower;

    priority_queue<string, vector<string>, greater<string>> higher;

    int n, priority;
    string memory;
    char ch;

    cin >> n; // SIZE OF STRING

    for (int i = 0; i < n; ++i) // INPUT STRING
    {
        cin >> ch;
        input.push(ch);
    }

    cin >> priority; // 1 OR -1

    while (!input.empty()) {
        memory = input.top() + memory;
        input.pop();

        if (priority == 1) {
            higher.push(memory);
        } else {
            lower.push(memory);
        }
    }

    //OUTPUT
    if (priority == 1) {
        while (!higher.empty()) {
            cout << higher.top() << endl;
            higher.pop();
        }
    } else {
        while (!lower.empty()) {
            cout << lower.top() << endl;
            lower.pop();
        }
    }
    //system("pause");
    return 0;
}

G. Несложная задача

Условие

Игорь любит решать математические задачи. Но сегодня ему попалась не совсем математическая задача а задача со строками, которые он не любит. Задача в том что на вход подаются строки и запросы "Сколько раз подобная строка встречалась среди всех поданных на данный момент строк?". Помогите Игорю решить эту задачу.

Идея

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

Решение

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    // n – количество строк и запросов
    int n;
    cin >> n;
    unordered_map<string, int> mp;

    for (int i = 0; i < n; ++i) {
        // запросы в формате
        // q s,
        // q – целое число от 1 до 2,
        // s – строка.
        int q;
        string s;

        cin >> q >> s;

        if (q == 1) {
            // При q равном 1 строку следует добавить    
            mp[s]++;
        } else if (q == 2) {
            // при q равном 2 вывести сколько раз встречалась в запросах на добавление эта строка раньше
            if (mp.count(s) == 0) {
                // иначе - не было таких
                cout << -1 << endl;
            } else {
                cout << mp[s] << endl;
            }
        }
    }
}
In [ ]: