e-olymp 7254. Отрезки

13/03/2021 by Євген Константинов

Задача

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

Отрезки пронумерованы последовательными натуральными числами, начиная с единицы. Отрезок номер [latex]i[/latex] характеризуется двумя числами — длиной [latex]L_i[/latex] и ценой [latex]C_i[/latex]. Петя очень умный, поэтому знает, что желаемый треугольник он может сложить из трех отрезков. Более того, наш герой знает, что треугольник возможно сложить только из таких трех отрезков, среди которых длина любого отрезка строго меньше суммарной длины двух других. Итак, мальчик решил купить ровно три таких отрезка. Разумеется, он хочет сэкономить как можно больше денег на мороженое, поэтому стремится потратить как можно меньше денег на покупку треугольника.

Задание

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

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

В первой строке входного файла записано единственное число [latex]N[/latex] — количество отрезков. В следующих [latex]N[/latex] строках записана информация о самих отрезках. Каждая такая строка содержит соответствующие [latex]L_i[/latex] [latex](1 \leqslant L_i \leqslant 10^9)[/latex] и [latex]C_i[/latex]. Цены образуют перестановку чисел от [latex]1[/latex] до [latex]N[/latex], то есть являются попарно различными натуральными числами, не превосходящими [latex]N[/latex].

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

Выходной файл должен содержать единственное число — минимальную стоимость трех отрезков, из которых можно сложить треугольник, либо «-1» (кавычки для наглядности) в том случае, если выбрать ровно три таких отрезка невозможно.

Тесты

№	Входные данные	Выходные данные
1	4 1 1 2 2 3 3 4 4	9

Код

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

//Структура для представления одного отрезка
struct Line {
    int price;
    int length;
};

//Функция сортировщик по цене в порядке возрастания
bool comparator_price (Line i, Line j) { 
    return i.price < j.price;
}

int main() {
    int n, price, length, cheapest = INT_MAX;
    cin >> n;
    Line lines_by_price[n];
    
    for (int i = 0; i < n; i++) {
        Line l;
        cin >> length >> price;
        l.price = price;
        l.length = length;
        lines_by_price[i] = l;
    }
    
    //Сортируем все отрезки по цене, чтобы была возможность "отсечь"
    //слишком дорогие отрезки, когда цена одного(или двух) будет 
    //больше текущей минимальной
    sort(&lines_by_price[0], &lines_by_price[n], comparator_price);
    
    for (int i = 0; i < n; i++) {
        Line first_side = lines_by_price[i];
        if (first_side.price > cheapest) break;
        vector<Line> sides = {};
        //Перебираем все возможные тройки отрезков, отсекая
        //слишком дорогие, основываясь на сортировке по цене
        //и текущей минимальной цене
        for (int j = 0; j < n; j++) {
            if (lines_by_price[j].price != first_side.price && lines_by_price[j].length <= first_side.length) {
                sides.push_back(lines_by_price[j]);
                Line second_side = lines_by_price[j];
                if (first_side.price + second_side.price > cheapest) break;
                for (auto third_side: sides) {
                    if ((third_side.length != second_side.length && third_side.price != second_side.price) 
                    && first_side.length < second_side.length + third_side.length 
                    && second_side.length < first_side.length + third_side.length 
                    && third_side.length < second_side.length + first_side.length) {
                        if (first_side.price + second_side.price + third_side.price < cheapest) {
                            cheapest = first_side.price + second_side.price + third_side.price;
                        }
                        break;
                    }
                }
            }
        }
    }
    //Если ни одна тройка отрезков не подошла, значит составить
    //треугольник невозможно - выводим "-1"
    if (cheapest == INT_MAX) cheapest = -1;
    cout << cheapest;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <climits>

using namespace std;

//Структура для представления одного отрезка

struct Line {

int price;

int length;

};

//Функция сортировщик по цене в порядке возрастания

bool comparator_price (Line i, Line j) {

return i.price < j.price;

}

int main() {

int n, price, length, cheapest = INT_MAX;

cin >> n;

Line lines_by_price[n];

for (int i = 0; i < n; i++) {

Line l;

cin >> length >> price;

l.price = price;

l.length = length;

lines_by_price[i] = l;

}

//Сортируем все отрезки по цене, чтобы была возможность "отсечь"

//слишком дорогие отрезки, когда цена одного(или двух) будет

//больше текущей минимальной

sort(&lines_by_price[0], &lines_by_price[n], comparator_price);

for (int i = 0; i < n; i++) {

Line first_side = lines_by_price[i];

if (first_side.price > cheapest) break;

vector<Line> sides = {};

//Перебираем все возможные тройки отрезков, отсекая

//слишком дорогие, основываясь на сортировке по цене

//и текущей минимальной цене

for (int j = 0; j < n; j++) {

if (lines_by_price[j].price != first_side.price && lines_by_price[j].length <= first_side.length) {

sides.push_back(lines_by_price[j]);

Line second_side = lines_by_price[j];

if (first_side.price + second_side.price > cheapest) break;

for (auto third_side: sides) {

if ((third_side.length != second_side.length && third_side.price != second_side.price)

&& first_side.length < second_side.length + third_side.length

&& second_side.length < first_side.length + third_side.length

&& third_side.length < second_side.length + first_side.length) {

if (first_side.price + second_side.price + third_side.price < cheapest) {

cheapest = first_side.price + second_side.price + third_side.price;

}

break;

}

//Если ни одна тройка отрезков не подошла, значит составить

//треугольник невозможно - выводим "-1"

if (cheapest == INT_MAX) cheapest = -1;

cout << cheapest;

return 0;

}

Решение

Для начала запишем все отрезки в массив в виде структур. Отсортируем их по цене в порядке возрастания, чтобы позже иметь возможность «отсекать» слишком дорогие отрезки. Далее мы начинаем перебирать все возможные тройки отрезков. На первом уровне цикла ставим условный оператор. Если на [latex]n[/latex]-ой итерации цикла будет отрезок с ценой больше текущей наименьшей цены треугольника, то мы можем выходить из массива и выводить текущую минимальную стоимость, т.к. все последующие отрезки будут дороже (пользуемся сортировкой и тем, что цены отрезков образуют перестановку от [latex]1[/latex] до [latex]N[/latex]). Далее на втором и третьем уровнях цикла мы также перебираем все отрезки от дешевых к дорогим и при обнаружении тройки отрезков, цена которых меньше текущей минимальной, записываем их в переменную [latex]cheapest[/latex]. При этом на втором уровне цикла проверяем, не больше ли сумма цен двух отрезков текущей минимальной, чтобы не проверять лишние тройки.

Ссылки

Related Images:

e-olymp 7233. Путешествия в космосе

03/12/2020 by Євген Константинов

Задача

Инфраструктура космической галактики состоит из [latex]N[/latex] планет и [latex]M[/latex] прямых межпланетных маршрутов, каждый из которых связывает ровно две разные планеты. Расстояния в космосе достаточно большие, поэтому, если планеты не имеют прямого сообщения, то во время перелетов используют транзитные планеты.

Популярностью планеты [latex]k[/latex] будем считать количество пар различных планет [latex]i[/latex] и [latex]j[/latex], перелет между которыми возможен только при использовании планеты [latex]k[/latex] [latex] (i, j, k = 1..N)[/latex]. Для заданной системы космических сообщений найти значение максимальной популярности и количество планет, достигающих её.

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

В первой строке натуральные числа [latex]N[/latex] и [latex]M[/latex] ([latex]1 \leqslant N \leqslant 1000[/latex], [latex]1 \leqslant M \leqslant 5000[/latex]). В следующих [latex]M[/latex] строках по два натуральных числа, описывающие маршрут между планетами [latex]i[/latex] и [latex]j[/latex] [latex](i, j, k = 1..N)[/latex].

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

Ответ к задаче.

Тесты

№	Входные данные	Выходные данные	Схема
1	4 4 1 2 1 3 1 4 2 3	5 1
2	14 14 1 2 2 3 2 4 3 5 1 6 6 7 7 8 8 6 1 9 9 10 10 11 9 12 1 13 13 14	75 1
3	4 4 1 2 2 3 3 4 4 1	3 4

Код

#include <iostream>
#include <vector>

using namespace std;

int inspect(int vertice, vector<int> graph[], bool visited[]);
bool allVisited(bool visited[], int n);
int firstNotVisited(bool visited[], int n);

int main() {
    int n, m, a, b;
    cin >> n >> m;
    
    vector<int> graph[n] = {};
    
    //Ввод данных, создание списка смежности графа
    
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    //Поиск наиболее популярного узла (планеты)
    //Осуществляется с помощью Depth-first search, поочередно убирая каждый узел
    //и перемножая кол-во планет в получившихся подграфах графа
    
    int maxPop = 0, maxPlanets = 0;
    for (int i = 0; i < n; i++) {
        bool visited[n] = {};
        //Отмечаем "убранный" узел как уже посещенный, чтобы не учитывать его при обходе
        visited[i] = true;
        vector<int> structures;
        //Рекурсивно проходим по всему графу, пока остаются не посещенные узлы
        //Кол-во итераций = кол-во подграфов
        while (!allVisited(visited, n))
            structures.push_back(inspect(firstNotVisited(visited, n), graph, visited));
        int pop = n - 1;
        //Изначальная популярность - кол-во других планет, т.к. перелет
        //между ними и убранной планетой уже не возможен
        for (int j = 0; j < structures.size() - 1; j++)
            for (int k = j + 1; k < structures.size(); k++)
                pop += structures[j] * structures[k];
                //Поочередно перемножаем кол-во планет из каждого подграфа
        if (pop > maxPop) {
            maxPlanets = 1;
            maxPop = pop;
        } else if (pop == maxPop)
            maxPlanets++;
    }
    cout << maxPop << " " << maxPlanets;
}

bool allVisited(bool visited[], int n) {
    for (int i = 0; i < n; i++)
        if (!visited[i]) return false;
    return true;
}

int firstNotVisited(bool visited[], int n) {
    for (int i = 0; i < n; i++)
        if (!visited[i]) return i;
    return -1;
}

int inspect(int vertice, vector<int> graph[], bool visited[]) {
    //Рекурсивный метод обхода графа
    //Проходится по всем смежным узлам из списка смежности, пока не наткнется
    //на уже посещенный узел
    int cnt = 1;
    visited[vertice] = true;
    for (auto e: graph[vertice])
        if (!visited[e])
            cnt += inspect(e, graph, visited);
    return cnt;
}

#include <iostream>

#include <vector>

using namespace std;

int inspect(int vertice, vector<int> graph[], bool visited[]);

bool allVisited(bool visited[], int n);

int firstNotVisited(bool visited[], int n);

int main() {

int n, m, a, b;

cin >> n >> m;

vector<int> graph[n] = {};

//Ввод данных, создание списка смежности графа

for (int i = 0; i < m; i++) {

cin >> a >> b;

a--, b--;

graph[a].push_back(b);

graph[b].push_back(a);

}

//Поиск наиболее популярного узла (планеты)

//Осуществляется с помощью Depth-first search, поочередно убирая каждый узел

//и перемножая кол-во планет в получившихся подграфах графа

int maxPop = 0, maxPlanets = 0;

for (int i = 0; i < n; i++) {

bool visited[n] = {};

//Отмечаем "убранный" узел как уже посещенный, чтобы не учитывать его при обходе

visited[i] = true;

vector<int> structures;

//Рекурсивно проходим по всему графу, пока остаются не посещенные узлы

//Кол-во итераций = кол-во подграфов

while (!allVisited(visited, n))

structures.push_back(inspect(firstNotVisited(visited, n), graph, visited));

int pop = n - 1;

//Изначальная популярность - кол-во других планет, т.к. перелет

//между ними и убранной планетой уже не возможен

for (int j = 0; j < structures.size() - 1; j++)

for (int k = j + 1; k < structures.size(); k++)

pop += structures[j] * structures[k];

//Поочередно перемножаем кол-во планет из каждого подграфа

if (pop > maxPop) {

maxPlanets = 1;

maxPop = pop;

} else if (pop == maxPop)

maxPlanets++;

}

cout << maxPop << " " << maxPlanets;

}

bool allVisited(bool visited[], int n) {

for (int i = 0; i < n; i++)

if (!visited[i]) return false;

return true;

}

int firstNotVisited(bool visited[], int n) {

for (int i = 0; i < n; i++)

if (!visited[i]) return i;

return -1;

}

int inspect(int vertice, vector<int> graph[], bool visited[]) {

//Рекурсивный метод обхода графа

//Проходится по всем смежным узлам из списка смежности, пока не наткнется

//на уже посещенный узел

int cnt = 1;

visited[vertice] = true;

for (auto e: graph[vertice])

if (!visited[e])

cnt += inspect(e, graph, visited);

return cnt;

}

Решение

Для начала представим полученный граф из планет в виде списка смежности (список, где каждой вершине соответствует список смежных ей других вершин). Так как нам надо получить значение наибольшей популярности, будем поочередно убирать (по сути заранее отмечать ее как посещенную) каждую из вершин и смотреть, между сколькими парами вершин нельзя составить маршрут. Для этого воспользуемся depth-first search. Его суть состоит в том, что мы берем любую вершину и начинаем рекурсивно проходить по всем ее соседям, а потом по их соседям и так далее. Каждую посещенную вершину мы отмечаем, чтобы при попадании на посещенную ранее вершину выйти из рекурсии. Таким образом, мы запускаем рекурсивную функцию пока остаются не посещенные вершины. В конце мы получим список связных подграфов и количество вершин в каждом из них. Чтобы получить популярность искомой вершины, мы суммируем кол-во остальных вершин (так как у них нет маршрута к убранной вершине) и поочередное произведение кол-ва вершин полученных подграфов.