e-olymp 3738. Простая сортировка

16/03/2021 by Verheles Vladyslav

Задача

Дан массив целых чисел. Ваша задача — отсортировать его в порядке неубывания.

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

В первой строке входного файла содержится число $N (1 \leqslant N \leqslant 100000)$ — количество элементов в массиве. Во второй строке находятся N целых чисел, по модулю не превосходящих $10^9$.

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

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

Тесты

№	Входные данные	Выходные данные
1	10 1 8 2 1 4 7 3 2 3 6	1 1 2 2 3 3 4 6 7 8
2	9 7 39 8 1 4 2 65 10 5	1 2 4 5 7 8 10 39 65
3	12 -3 7 -7 -11 40 -30 25 30 2 7 -30 1	-30 -30 -11 -7 -3 1 2 7 7 25 30 40

Код

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

int main() {
    int a;
    cin >> a;
    int* arr = new int[a];
    for (int i = 0; i < a; i++) { cin >> arr[i]; }
    sort(arr, arr + a);
    for (int i = 0; i < a; i++) { cout << arr[i] << ' '; }
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int a;

cin >> a;

int* arr = new int[a];

for (int i = 0; i < a; i++) { cin >> arr[i]; }

sort(arr, arr + a);

for (int i = 0; i < a; i++) { cout << arr[i] << ' '; }

}

Решение

Для решения задачи используем функцию сортировки из библиотеки algorithm. Для начала создаем одномерный массив, потом с помощью цикла записываем значения в массив. С помощью функции sort(), сортируем и записываем изменения в массив. Потом с помощью цикла выводим результат.

Ссылки

Задача на e-olymp
Код решения на ideone
Засчитанное решение на e-olymp

Related Images:

e-olymp 1462. Хитрая сортировка

26/02/2020 by Николай Жирко

Задача

Дана последовательность чисел. Вам следует упорядочить их по неубыванию последней цифры, а при равенстве последних цифр – по неубыванию самих чисел.

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

Первая строка содержит число [latex] n [/latex] ([latex] 1 \leqslant n \leqslant 100 [/latex]), а вторая — сами натуральные числа, не превышающие [latex] 32000 [/latex].

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

Выведите последовательность чисел, упорядоченную согласно условию.

Тесты

№	Входные данные	Выходные данные
1	7 12 15 43 13 20 1 15	20 1 12 13 43 15 15
2	10 82 22 19 90 34 17 588 921 200 121	90 200 121 921 22 82 34 17 588 19
3	4 162 9801 37 14	9801 162 14 37

Код программы

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

bool comp (const int& a, const int& b) {
    if (a % 10 == b % 10) return (a < b);
    else return a % 10 < b % 10;
}

int main() {
    int n, a;
    vector<int> array;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        array.push_back(a);
    }
    
    sort (array.begin(), array.end(), comp);
    
    for (int a = 0; a < n; a++) {
        cout << array[a] << " ";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

bool comp (const int& a, const int& b) {

if (a % 10 == b % 10) return (a < b);

else return a % 10 < b % 10;

}

int main() {

int n, a;

vector<int> array;

cin >> n;

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

cin >> a;

array.push_back(a);

}

sort (array.begin(), array.end(), comp);

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

cout << array[a] << " ";

}

return 0;

}

Решение задачи

Для решения этой задачи необходимо объявить вектор, который будет хранить все числа, введенные пользователем, например, array.
Сортировку будем проводить с помощью функции sort. Для правильного упорядочивания чисел, напишем функцию компаратор comp, для сравнения чисел и решения, стоит ли их менять местами.
В конце выводим вектор array.

Ссылки

Условие на e-olymp

Решение на e-olymp

Решение на ideone.com

Related Images:

e-olymp 1462. Хитрая сортировка

25/02/2020 by Нина Хоробрых

Задача

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

Первая строка содержит число $n \ (1 \leqslant n \leqslant 1000)$, а вторая — сами натуральные числа, не превышающие $32000$.

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

Выведите последовательность чисел, упорядоченную согласно условию.

Тесты

№	Входные данные	Выходные данные
1	7 12 15 43 13 20 1 15	12 33 14 44 64 77
2	4 345 112 999 29	112 345 29 999
3	9 78 33 13 0 12 89 20 78 9990	0 20 9990 12 13 33 78 78 89

Код

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int mass[n];
    for (int i = 0; i < n; i++) {
        cin >> mass[i];
    }
    
    for (int i = 0; i < n; i++){
        for (int j = 1; j < (n - i);  j++) {
        if (mass[j] % 10 < mass[j-1] % 10) {
                swap (mass[j-1], mass[j]);
        } 
        else if ( mass[j] % 10 == mass[j-1] % 10 and mass[j] < mass[j-1]){
            swap (mass[j-1], mass[j]);
        }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << mass[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n;

cin >> n;

int mass[n];

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

cin >> mass[i];

}

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

for (int j = 1; j < (n - i); j++) {

if (mass[j] % 10 < mass[j-1] % 10) {

swap (mass[j-1], mass[j]);

}

else if ( mass[j] % 10 == mass[j-1] % 10 and mass[j] < mass[j-1]){

swap (mass[j-1], mass[j]);

}

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

cout << mass[i] << " ";

}

return 0;

}

Решение

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

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 2662. Метод минимума

01/02/2020 by Виктория Крачилова

Условие задачи

Массив сортируется методом выбора по возрастанию. Сколько раз меняет свое место первый по порядку элемент?

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

Первая строка содержит количество элементов в массиве $n$ $\left(1\leqslant n\leqslant1000\right)$. Во второй строке задан сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10^9$.

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

Вывести количество перемещений первого элемента.

Тесты

№	Ввод	Вывод
1	3 1 3 2	0
2	2 2 1	1
3	4 4 1 5 3	3
4	6 23 5 56 2 87 3	1
5	7 15 1 6 3 9 8 13	4

Код программы

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int x[n];
    int counter = 0; // количество перемещений
    for (int i = 0; i < n; i++){
        cin >> x[i];
    }
    int first = x[0]; // первый по порядку элемент
    for (int i = 0; i < n - 1; i++) {
        int min = i; // индекс минимального элемента
        for (int j = i + 1; j < n; j++) {
            if (x[j] < x[min]) min = j;
        }
        if((x[i] == first || x[min] == first) && x[i] != x[min]) counter++;
        swap(x[i], x[min]);
    }
    cout << counter;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int x[n];

int counter = 0; // количество перемещений

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

cin >> x[i];

}

int first = x[0]; // первый по порядку элемент

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

int min = i; // индекс минимального элемента

for (int j = i + 1; j < n; j++) {

if (x[j] < x[min]) min = j;

}

if((x[i] == first || x[min] == first) && x[i] != x[min]) counter++;

swap(x[i], x[min]);

}

cout << counter;

return 0;

}

Решение

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

Подробное изложение алгоритма сортировки можно найти в этой статье .

Ссылки

Related Images:

e-olymp 2663. Сортировка пузырьком

28/01/2020 by Даниил Кадочников

Условие

Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива.

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

В первой строке содержится количество элементов $n$ ($1 \leqslant n \leqslant 1000$) в массиве. Во второй строке — сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10$^$9$.

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

Выведите одно число — количество обменов пузырьковой сортировки.

Тесты

№	Ввод	Вывод
1	3 1 3 2	1
2	2 2 1	1
3	4 4 1 5 3	3
4	5 5 4 1 100000 7	4
5	6 6 5 4 3 2 1	15

Решение

Используем простой алгоритм пузырьковой сортировки: проходим по массиву циклом, если два элемента стоят не в том порядке, то меняем их местами. Так как задача состоит в том, чтобы вывести число обменов, при каждом обмене прибавляем к счётчику $1$. При каждом выполнении цикла по j ставится на место хотя бы 1 элемент, поэтому с каждым полным проходом его длина сокращается на $1$.

Код программы

#include <iostream>
using namespace std;
int n;

int main() {
    cin >> n;
    int arr[n];

    for(int i=0; i<n; i++) cin >> arr[i];
    int counter=0;
    for(int u=0; u<n;u++) {
        for(int j=1; j<(n-u); j++) {
            if((arr[j]<arr[j-1])) {
                
                int prev;
                prev = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = prev;
                counter++;            
            }
        }
    }
    cout << counter;
    return 0;
}

#include <iostream>

using namespace std;

int n;

int main() {

cin >> n;

int arr[n];

for(int i=0; i<n; i++) cin >> arr[i];

int counter=0;

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

for(int j=1; j<(n-u); j++) {

if((arr[j]<arr[j-1])) {

int prev;

prev = arr[j-1];

arr[j-1] = arr[j];

arr[j] = prev;

counter++;

}

cout << counter;

return 0;

}

Ссылки

решение на e-olymp
код на ideone

Related Images:

e-olymp 9410. Студенческая любовь

01/12/2019 by Дмитрий Воротов

Задача

Нурдаулет и Жарасхан тренируют студентов. К каждому студенту у них имеется свое собственное отношение, которое выражается как числа $a_{i}$ (для Нурдаулета) и $b_{i}$ (для Жараскана), которые называются индексом любви студентов. Аскар попросил их рассчитать коэффициент несправедливого отношения. Коэффициент несправедливого отношения — это разница между самым большим и самым маленьким индексом любви. Чтобы не показывать свои, возможно, большие коэффициенты несправедливого отношения, они решили обмануть: каждый перемешивает свой массив, после чего формируется новый массив $c_{i}$ = $a_{i}$ + $b_{i}$, и его коэффициент несправедливого отношения передается Аскару. Какое минимально возможное значение коэффициента они могут достичь?

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

Первая строка содержит одно целое число $n$ $(1 ⩽ n ⩽ 200000)$. Вторая строка содержит $n$ целых чисел $a_{i}$ $(-10^6 ⩽ a_{i} ⩽ 10^6)$. Третья строка содержит $n$ целых чисел $b_{i}$ $(-10^6 ⩽ b_{i} ⩽ 10^6)$.

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

Выведите одно число — ответ на задачу.

Тесты

№	Входные данные	Выходные данные
1	2 -3 -5 3 5	0
2	1 5 -2	0
3	5 -5 -2 -1 0 4 5 4 0 0 -1	4
4	9 1000 -22 333 -56 1 2 -77 -650 10 -7 166 -333 90 -565 12 788 -800 111	523

Код программы

#include <iostream>
#include 
#include 
using namespace std;

int main() {
    int n;
    cin >> n;
    int *a = new int[n], *b = new int[n];
    for (int i = 0; i < n; i ++) cin >> a[i];  // Считываем массивы
    for (int i = 0; i < n; i ++) cin >> b[i];  
    sort(a, a + n);    // Сортируем массивы
    sort(b, b + n);    // Вместо сортировки по убыванию будем просматривать отсортированный массив в обратном порядке 
    for (int i = 0; i < n; i ++) a[i] += b[n - i - 1];  // Суммируем элементы
    int maxa = a[0], mina = a[0];
    for (int i = 0; i < n; i ++) {
        maxa = max(maxa, a[i]);    // Находим минимальный и максимальный элементы
        mina = min(mina, a[i]);     
    }
    cout << maxa - mina;  // Разность минимального и максимального и будет самым маленьким индексом любви 
    return 0;
}

#include <iostream>

#include

using namespace std;

int main() {

int n;

cin >> n;

int *a = new int[n], *b = new int[n];

for (int i = 0; i < n; i ++) cin >> a[i]; // Считываем массивы

for (int i = 0; i < n; i ++) cin >> b[i];

sort(a, a + n); // Сортируем массивы

sort(b, b + n); // Вместо сортировки по убыванию будем просматривать отсортированный массив в обратном порядке

for (int i = 0; i < n; i ++) a[i] += b[n - i - 1]; // Суммируем элементы

int maxa = a[0], mina = a[0];

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

maxa = max(maxa, a[i]); // Находим минимальный и максимальный элементы

mina = min(mina, a[i]);

}

cout << maxa - mina; // Разность минимального и максимального и будет самым маленьким индексом любви

return 0;

}

Решение

Коэффициент будет минимальным в том случае, когда все элементы массива $c_{i}$ будут отличаться друг от друга как можно меньше. Для этого отсортируем один массив по убыванию, другой — по возрастанию и почленно сложим. После этого останется только найти максимальный и минимальный элементы полученного массива.

Ссылки

Условие задачи e-olymp

Код решения ideone

Related Images:

e-olymp 145. Квадраты

25/06/2019 by Алина Гук

Задача взята с сайта e-olymp

Задача

Заданы длины $n$ отрезков. Какое наибольшее количество квадратов можно из них составить? Сторона каждого квадрата должна состоять только из одного отрезка.

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

В первой строке находится количество отрезков $n \left(1 \leqslant n\leqslant 10^6\right)$. Во второй строке заданы $n$ натуральных чисел — длины отрезков, числовые значения которых не превышают $100$.

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

Вывести максимально возможное количество квадратов, которое можно составить из заданных отрезков.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	9 2 2 4 2 3 2 1 2 4	1
2	11 2 2 4 2 2 4 2 2 1 2 2	2
3	5 8 9 8 9 11	0

Код программы

#include <iostream>
#define MAX 101
using namespace std;

int a[MAX];

int main() {
    int n, l, res = 0, i;
    cin >> n;
    for(l = 0; l < n; l++) cin >> i, a[i]++;
    for(i = 1; i <= MAX - 1; i++) res += a[i] / 4;
    cout << res << "\n";
    return 0;
}

#include <iostream>

#define MAX 101

using namespace std;

int a[MAX];

int main() {

int n, l, res = 0, i;

cin >> n;

for(l = 0; l < n; l++) cin >> i, a[i]++;

for(i = 1; i <= MAX - 1; i++) res += a[i] / 4;

cout << res << "\n";

return 0;

}

Решение

Пусть имеется $k$ отрезков одинаковой длины. Тогда из них можно составить $\frac{k}{4}$ квадрата. Длины отрезков изменяются от $1$ до $100$. Подсчитываем количество отрезков длины $i\left(1\leqslant i\leqslant 100\right)$ в массив $a\left[i\right]$. Тогда максимально возможное количество квадратов, которое можно составить из данных отрезков, равно $$\frac{a\left[1\right]+a\left[2\right]+\dots +a\left[100\right]}{4}.$$

Для этого совершим сортировку подсчетом. В ячейке a[i] подсчитываем количество отрезков длины i . В переменную res подсчитываем количество квадратов, которое можно построить.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

Сортировка подсчетом на Wikipedia

Related Images:

А291а

25/05/2016 by Андрей Яроцкий

Задача: А291а

Условие:

Даны действительные числа [latex]a_{1},\ldots,a_{30}.[/latex] Получить [latex]\max (a_{1}+ a_{30},a_{2}+a_{29},\ldots,a_{15}+a_{n}).[/latex]

Тесты:

№	Входные данные	Выходные данные
1	2 3 5 4	8
2	2 3 7 5 4	14
3	4.5 1.1 3 9.25 0.75	10.35
4	-4.5 -2 0 -7.1 5	0.5

Код программы:

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

bool f(double a, double b){ //Вспомогательная функция для сортировки вектора по убыванию
    return a>b;
}

int main() {
    vector<double> real;
    double value;
    while(cin >> value){
        real.push_back(value);
    }
    int size = real.size();
    int size_of_sum = ceil(size%2==0?size/2:size/2+1); //Размер вектора сумм
    vector<double> sum;
    for(int i = 0; i < size_of_sum; i++){
        if(i == size_of_sum-1 && size%2 != 0) sum.push_back(2*real[i]);// Средний элемент массива real при нечетном size
        else sum.push_back(real[i] + real[size - i - 1]);
    }
    sort(sum.begin(),sum.end(),f); // Сортировка по убыванию
    cout << sum[0];
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

using namespace std;

bool f(double a, double b){ //Вспомогательная функция для сортировки вектора по убыванию

return a>b;

}

int main() {

vector<double> real;

double value;

while(cin >> value){

real.push_back(value);

}

int size = real.size();

int size_of_sum = ceil(size%2==0?size/2:size/2+1); //Размер вектора сумм

vector<double> sum;

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

if(i == size_of_sum-1 && size%2 != 0) sum.push_back(2*real[i]);// Средний элемент массива real при нечетном size

else sum.push_back(real[i] + real[size - i - 1]);

}

sort(sum.begin(),sum.end(),f); // Сортировка по убыванию

cout << sum[0];

return 0;

}

Решение:

После считывания входного потока данных в вектор [latex]real[/latex] вещественных чисел, вычисляем размер вектора [latex]sum[/latex], равный половине количества элементов входного потока с округлением вверх. В случае нечетного количества элементов, последним элементом вектора [latex]sum[/latex] будет центральный элемент вектора [latex]real[/latex] увеличенный в два раза. Далее, после сортировки полученного вектора по убыванию, выводим первый элемент вектора.

Ссылки:

Задачник по программированию С. Абрамова.

Код программы на ideone.com.

Related Images:

e-olymp 4003. Топологическая сортировка

26/03/2016 by Сплошнов Кирилл

Задача взята отсюда.

Условие

Дан ориентированный невзвешенный граф. Необходимо его топологически отсортировать.

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

В первой строке содержатся два натуральных числа [latex]n[/latex] и [latex]m[/latex] ([latex]1 \leq n \leq 10^5[/latex], [latex]1 \leq m \leq 10^5[/latex]) — количество вершин и рёбер в графе соответственно. Далее в [latex]m[/latex] строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.

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

Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, требуется вывести [latex]-1[/latex].

Решение

Для решения использовался алгоритм топологической сортировки методом поиска в глубину (подробнее в комментариях к коду). Функция bool dfs() (поиск в глубину) также проверяет, цикличен ли граф, т.к. по условию он может как содержать, так и не содержать циклы. Результат сортировки заносим в вектор result, потом выводим его элементы по порядку.

Тесты

№	Входные данные	Выходные данные
1	6 6 1 2 3 2 4 2 2 5 6 5 4 6	4 6 3 1 2 5
2	3 3 1 2 2 3 3 1	-1
3	4 4 1 4 4 3 3 2 4 2	1 4 3 2

Код

#include <iostream>
#include <vector>
#include <algorithm>
#define WHITE 0 //вершина не посещена
#define GREY 1 //вершина обрабатывается
#define BLACK 2 //вершина обработана
using namespace std;

bool dfs (int v, vector<int>* vertex, int* state, vector<int> &result, int size) //возвращает true или false в зависимости от того, был ли найден цикл
{
	state[v] = GREY; //отмечаем, что вершина в процессе обработки
	for (int i = 0; i < vertex[v].size(); i++) //для каждой вершины, в которую можно попасть из данной
	{
		int dest = vertex[v].at(i);
		if (state[dest] == WHITE) //если еще не посетили - запускаем поиск в глубину, возвращаем true, если далее был найден цикл
		{
			if (dfs(dest, vertex, state, result, size))
				return true;
		}
		else if (state[dest] == GREY) //если из вершины можно попасть туда, где мы уже были при данном порядке обхода - найден цикл
		{
			return true;
		}
	}
    //если цикл не найден:
	state[v] = BLACK; //помечаем вершину как обработанную
	result.push_back(v+1); //помещаем ее номер (со сдвигом на 1, из-за разницы в нумерациях) в вектор-результат сортировки
	return false;
}

void topologicalSort(vector<int>* vertex, int* state, vector<int> &result, int size)
{
	for (int i = 0; i < size; i++) //для каждой вершины графа
	{
		if (state[i] == WHITE) //если она еще не посещена
		{
			bool cyclic = dfs(i, vertex, state, result, size); //вызываем для нее поиск в глубину
			if (cyclic) //если нашли цикл, возвращаем единственное значение -1 (по условию)
			{
				result.clear();
				result.push_back(-1);
				return;
			}
		}
	}
	reverse(result.begin(), result.end()); //вершины добавляются в вектор в порядке, противоположном топологической сортировке, так что нужно вызвать для вектора reverse()
}

int main() 
{
	ios::sync_with_stdio(false); 
	int n, m;
	cin >> n >> m;
	vector<int> vertex[n]; //сам граф
	int state[n]; //массив состояний вершин
	vector<int> result;
	fill (state, state + n, WHITE); //изначально ни одна вершина не посещена
	for (int i = 0; i < n; i++)
	{
		int begin, end;
		cin >> begin >> end;
		vertex[begin-1].push_back(end-1);
	}
	topologicalSort(vertex, state, result, n); //сортируем граф
	for (int i = 0; i < result.size(); i++)
		cout << result.at(i) << " ";
	return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

#define WHITE 0 //вершина не посещена

#define GREY 1 //вершина обрабатывается

#define BLACK 2 //вершина обработана

using namespace std;

bool dfs (int v, vector<int>* vertex, int* state, vector<int> &result, int size) //возвращает true или false в зависимости от того, был ли найден цикл

{

state[v] = GREY; //отмечаем, что вершина в процессе обработки

for (int i = 0; i < vertex[v].size(); i++) //для каждой вершины, в которую можно попасть из данной

{

int dest = vertex[v].at(i);

if (state[dest] == WHITE) //если еще не посетили - запускаем поиск в глубину, возвращаем true, если далее был найден цикл

{

if (dfs(dest, vertex, state, result, size))

return true;

}

else if (state[dest] == GREY) //если из вершины можно попасть туда, где мы уже были при данном порядке обхода - найден цикл

{

return true;

}

//если цикл не найден:

state[v] = BLACK; //помечаем вершину как обработанную

result.push_back(v+1); //помещаем ее номер (со сдвигом на 1, из-за разницы в нумерациях) в вектор-результат сортировки

return false;

}

void topologicalSort(vector<int>* vertex, int* state, vector<int> &result, int size)

{

for (int i = 0; i < size; i++) //для каждой вершины графа

{

if (state[i] == WHITE) //если она еще не посещена

{

bool cyclic = dfs(i, vertex, state, result, size); //вызываем для нее поиск в глубину

if (cyclic) //если нашли цикл, возвращаем единственное значение -1 (по условию)

{

result.clear();

result.push_back(-1);

return;

}

reverse(result.begin(), result.end()); //вершины добавляются в вектор в порядке, противоположном топологической сортировке, так что нужно вызвать для вектора reverse()

}

int main()

{

ios::sync_with_stdio(false);

int n, m;

cin >> n >> m;

vector<int> vertex[n]; //сам граф

int state[n]; //массив состояний вершин

vector<int> result;

fill (state, state + n, WHITE); //изначально ни одна вершина не посещена

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

{

int begin, end;

cin >> begin >> end;

vertex[begin-1].push_back(end-1);

}

topologicalSort(vertex, state, result, n); //сортируем граф

for (int i = 0; i < result.size(); i++)

cout << result.at(i) << " ";

return 0;

}

Ссылки

Код на ideaone.

Засчитанное решение на e-olymp.

Наглядное объяснение топологической сортировки здесь.

Related Images:

e-olimp 1667. Конденсация графа

29/03/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №1667. Ссылка на засчитанное решение.

Вам задан связный ориентированный граф с [latex]N[/latex] вершинами и [latex]M[/latex] ребрами [latex]\left(1\leq N\leq 20000, 1\leq M\leq 200000 \right)[/latex]. Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.

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

Граф задан во входном файле следующим образом: первая строка содержит числа [latex]N[/latex] и [latex]M[/latex]. Каждая из следующих [latex]M[/latex] строк содержит описание ребра — два целых числа из диапазона от [latex]1[/latex] до [latex]N[/latex] — номера начала и конца ребра.

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

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

Тесты:

6 7

1 2

2 3

3 1

4 5

5 6

6 4

2 4

1 1 1 2 2 2

10 19

1 4

7 8

5 10

8 9

9 6

2 6

6 2

3 8

9 2

7 2

9 7

4 5

3 6

7 3

6 7

10 8

10 1

2 9

2 7

1 2 2 1 1 2 2 2 2 1

Иллюстрация к первому тесту:

Иллюстрация ко второму тесту:

Код программы:

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

vector <int> G[100010];
vector <int> Gt[100010]; // транспонированній граф
vector<bool> used;
vector<int> order, component;
int res[100010];
int n, m, num=1;

void dfs_1 (int u) {
 used[u]=1;
 for (int i=0; i<G[u].size(); i++) {
     if (used[G[u][i]]==0) {
         dfs_1(G[u][i]);
     }
 }
 order.push_back(u);
}

void dfs_2 (int u) {
  used[u]=1;
  component.push_back(u);
  for (int i=0; i<Gt[u].size(); i++) {
      if (used[Gt[u][i]]==0) {
          dfs_2 (Gt[u][i]);
      }
  }
}

int main() {
 ios::sync_with_stdio(false);
 cin >> n >> m;
 
 while (m--) {
     int a, b;
     cin >> a >> b;
     a--;
     b--;
     G[a].push_back(b);
     Gt[b].push_back(a);
 }
 
 used.assign (n, false);

 for (int i=0; i<n; i++) {
         if (used[i]==0) dfs_1(i);
 }
 
 used.assign (n, false);
 
 for (int i=0; i<n; i++) {
      int v=order[n-1-i];
      if (used[v]==0) {
          dfs_2 (v);
          for(auto I=component.begin(); I!=component.end(); I++)
              res[*I]=num;
          num++;
          component.clear();
      }
  }
  
  cout << num-1 << endl;
  for (int i=0; i<n-1; i++) cout << res[i] << " ";
  cout << res[n-1] << endl;
  return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector <int> G[100010];

vector <int> Gt[100010]; // транспонированній граф

vector<bool> used;

vector<int> order, component;

int res[100010];

int n, m, num=1;

void dfs_1 (int u) {

used[u]=1;

for (int i=0; i<G[u].size(); i++) {

if (used[G[u][i]]==0) {

dfs_1(G[u][i]);

}

order.push_back(u);

}

void dfs_2 (int u) {

used[u]=1;

component.push_back(u);

for (int i=0; i<Gt[u].size(); i++) {

if (used[Gt[u][i]]==0) {

dfs_2 (Gt[u][i]);

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

while (m--) {

int a, b;

cin >> a >> b;

a--;

b--;

G[a].push_back(b);

Gt[b].push_back(a);

}

used.assign (n, false);

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

if (used[i]==0) dfs_1(i);

}

used.assign (n, false);

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

int v=order[n-1-i];

if (used[v]==0) {

dfs_2 (v);

for(auto I=component.begin(); I!=component.end(); I++)

res[*I]=num;

num++;

component.clear();

}

cout << num-1 << endl;

for (int i=0; i<n-1; i++) cout << res[i] << " ";

cout << res[n-1] << endl;

return 0;

}

Алгоритм решения

Прежде всего топологически сортируем граф [latex]G[/latex] (с помощью функции dfs_1), записывая результат в вектор order. В итоге первой вершиной этого вектора окажется некая вершина [latex]u[/latex], принадлежащая «корневой» компоненте сильной связности, то есть в которую не входит ни одно ребро в графе конденсаций.

Теперь нужно сделать такой обход из этой вершины, который посетил бы только эту компоненту сильной связности и не зашёл бы ни в какую другую. Для этого служит функция dfs_2, которая применяется к траспонированному графу [latex]G^{T}[/latex] (граф, полученный из [latex]G[/latex] изменением направления каждого ребра на противоположное). В этом графе будут те же компоненты сильной связности, что и в исходном графе. Пусть [latex]G^{*}[/latex] — это граф конденсации, получаемый из данного графа сжатием каждой компоненты сильной связности в одну вершину (очевидно, что он ацикличен). Тогда [latex]\left(G^{T} \right)^{*}[/latex] будет равен транспонированному графу конденсации исходного графа [latex]G^{*}[/latex]. Это значит, что теперь из рассматриваемой нами «корневой» компоненты уже не будут выходить рёбра в другие компоненты.

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

Таким образом, чтобы обойти всю «корневую» компоненту сильной связности, содержащую некоторую вершину [latex]u[/latex], достаточно запустить обход из этой вершины в графе[latex]G^{T}[/latex]. Этот обход посетит все вершины этой компоненты сильной связности и только их. Дальше мы можем мысленно удалить эти вершины из графа, находить очередную вершину с максимальным значением времени выхода и запускать обход на транспонированном графе из неё.

Так после каждого запуска dfs_2 в векторе component окажутся все вершины, принадлежащие одной компоненте связности. Поэтому каждой из тих вершин присваиваем номер компоненты, после чего вектор component чистится и идёт новая итерация (номер компоненты при этом увеличивается на 1).

Related Images:

М16. Freshly Pressed Juice

29/11/2014 by Іванов Вячеслав Володимирович

Формулировка задачи

Известно, что каждый посетитель фруктового бара просит сделать наиболее дешевый коктейль из свежевыжатого сока. Объем стакана для сока V. Рассчитайте стоимость и сформируйте рецепт коктейля, который достанется n-тому посетителю. V и n читаются из входного потока. Во входном потоке имеется неизвестное количество строк – справочник в котором для каждого вида фруктов указано его название, текущая стоимость за килограмм, процент выхода сока и количество фруктов на складе.
а) Прочитать справочник в список (vector) соответствующих структур.
б) Сформировать рецепт и рассчитать стоимость наиболее дешёвого коктейля.

Тесты

[latex]V[/latex]	[latex]n[/latex]	[latex]Menu[/latex]	[latex]Recipe[/latex]	Комментарий
150	2	Apple 10 60 200 Cherry 20 70 50	Sorry, we are closed for today	Объем фруктов на складе меньше 300.
80	8	Dragonfruit 123 50 10 Aplle 10 60 200 Cherry 40 80 100 Coconut 20 5 30 Pineapple 80 90 50 Raspberry 70 95 30 Blackberry 130 95 30 Strawberry 60 95 40 Grape 20 95 120 Orange 10 80 200 Melon 10 98 300 Banana 20 30 120	Apple 80 800	В самом деле, более выгодным будет использование только арбузов и апельсинов, израсходованных ранее.
80	14	(см. тест № 2)	Banana 40.000000 Raspberry 30.000000 Pineapple 10.000000 3700	Корректно
110	1	(см. тест №2)	Melon 110 1100	Корректно

Анализ задачи

Параметры «количество», «удельная стоимость», «процент выхода сока» описывают сущность типа «фрукт». Следовательно, необходимо создать одноименную структуру, связав конкретное наименование в меню (списке) с его количественными характеристиками.
Условие задачи можно переформулировать как поиск наиболее выгодного фрукта по соотношению (у.е./куб.ед.) — фрукта, из единицы массы которого можно дешевле всего получить кубическую единицу объема, [latex]\frac {price}{volume}[/latex]. Данные, необходимые для сортировки фруктов в порядке возрастания стоимости единицы объема сока, присуствуют в исходных данных. Подробнее: [latex]\frac {price}{volume} = \frac {amount*specificCost}{amount*percentage*\rho} = \frac {specificCost}{percentage*\rho}[/latex]. В условии не указано обратное, потому плотность сока принята равной [latex]\rho = 1[/latex](г/мл). Окончательно, [latex]worth = \frac {specificCost}{percentage}[/latex].

Алгоритм решения

- Объявить структуру [latex]fruit[/latex] с переменными:
  - name
  - specific_cost
  - percentage
  - amount
- Необходимо
  1. считывать информацию о фрукте;
  2. сортировать фрукты по некоторому параметру
  Следовательно, уместно определить методы [latex]get()[/latex] и [latex]worth()[/latex] соответственно.
Дальнейшее решение распадается на несколько подзадач:
1. Сортировка элементов вектора в порядке убывания стоимости единицы объема.
2. Поиск фруктов, доступных в момент, когда [latex]n[/latex]-ый посетитель делает заказ.
3. Составление коктейля наименьшей стоимости при заданном объёме порции.
Был намечен следующий алгоритм действий:
1. После сортировки определить, какая масса фруктов должна быть израсходована к моменту заказа, и последовательно проходить по вектору, уменьшая количество каждого фрукта, пока не дойдем до требуемого значения.
2. Если оставшихся фруктов достаточно для приготовления коктейля, последовательно перерабатывать фрукты, пока на складе не закончится текущее наименование, а тогда перейти к следующему, и так пока не прийдем к заданному объему.
3. На каждом шаге добавлять в рецепт количество использованных фруктов вместе с их названиями. В конце рецепта указать стоимость коктейля.

Программный код

Программа доступна для тестирования по ссылке: http://ideone.com/qj8ovB.

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

struct fruit{
    string name;            //название фрукта
    double specific_cost;   //удельная стоимость
    double percentage;      //процентный выход сока
    double amount;          //текущее количество на складе
    double worth(){         //параметр в критерии отбора 
        return (specific_cost * 100)/percentage;
    }
    bool get(){             //логический тип позволяет 
        return (cin >> name //производить считывание
        >> specific_cost  //до конца файла
        >> percentage
        >> amount);
    }
};

int main()
{
    double V; int n;        //объем сока и номер посетителя по счёту
    cin >> V >> n;          
    /*Заполнение меню - показателя текущего состояния на складе*/
    vector<fruit> menu;
    fruit tmp; double total_amount = 0;
    while(tmp.get()){
        menu.push_back(tmp);
        total_amount += tmp.amount;
    }
    /*Критерий отбора: отсортировать в порядке уменьшения цены за литр*/
    sort(menu.begin(), menu.end(), [](fruit a, fruit b){return a.worth() < b.worth();});
    /*Составление рецепта коктейля*/
    /*1. Поиск фруктов, доступных на n-м шаге*/
    double used = (n - 1) * V; int starting_position = 0;
    if(total_amount >= n*V &&
        any_of(menu.begin(), menu.end(), [&](fruit &a) mutable {
            double new_amount = (used -= a.amount);
            if(new_wolume >= 0){starting_position++; a.amount = 0;}
            else a.amount = (-1)*new_amount;
            return new_amount < 0;
        })){
        //Заполнение коктейля соком до заданного объёма
        double volume_left = V, price = 0; string recipe;
        /*Добавлять ингредиенты из отсортированного меню, пока возможно*/
        any_of(menu.begin() + starting_position, menu.end(), [&](fruit &a) mutable {
        /*Если ингридиент израсходован*/
            double new_amount = (volume_left -= a.amount);
            if(new_amount >= 0){
                price += a.specific_cost * a.amount;
                recipe += a.name + ' ' + to_string(a.amount) + '\n';
                a.amount = 0;
            }
        /*Если коктейль готов*/
            else{
                a.amount = new_amount + a.amount;
                price += a.specific_cost * a.amount;
                recipe += a.name + ' ' + to_string(a.amount) + '\n';
            }
            return (new_amount <= 0);
        });
        cout << recipe << price << endl;
    }
    else cout << "Sorry, we are closed for today." << endl;
    return 0;
}

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

struct fruit{

string name; //название фрукта

double specific_cost; //удельная стоимость

double percentage; //процентный выход сока

double amount; //текущее количество на складе

double worth(){ //параметр в критерии отбора

return (specific_cost * 100)/percentage;

}

bool get(){ //логический тип позволяет

return (cin >> name //производить считывание

>> specific_cost //до конца файла

>> percentage

>> amount);

}

};

int main()

{

double V; int n; //объем сока и номер посетителя по счёту

cin >> V >> n;

/*Заполнение меню - показателя текущего состояния на складе*/

vector<fruit> menu;

fruit tmp; double total_amount = 0;

while(tmp.get()){

menu.push_back(tmp);

total_amount += tmp.amount;

}

/*Критерий отбора: отсортировать в порядке уменьшения цены за литр*/

sort(menu.begin(), menu.end(), [](fruit a, fruit b){return a.worth() < b.worth();});

/*Составление рецепта коктейля*/

/*1. Поиск фруктов, доступных на n-м шаге*/

double used = (n - 1) * V; int starting_position = 0;

if(total_amount >= n*V &&

any_of(menu.begin(), menu.end(), [&](fruit &a) mutable {

double new_amount = (used -= a.amount);

if(new_wolume >= 0){starting_position++; a.amount = 0;}

else a.amount = (-1)*new_amount;

return new_amount < 0;

})){

//Заполнение коктейля соком до заданного объёма

double volume_left = V, price = 0; string recipe;

/*Добавлять ингредиенты из отсортированного меню, пока возможно*/

any_of(menu.begin() + starting_position, menu.end(), [&](fruit &a) mutable {

/*Если ингридиент израсходован*/

double new_amount = (volume_left -= a.amount);

if(new_amount >= 0){

price += a.specific_cost * a.amount;

recipe += a.name + ' ' + to_string(a.amount) + '\n';

a.amount = 0;

}

/*Если коктейль готов*/

else{

a.amount = new_amount + a.amount;

price += a.specific_cost * a.amount;

recipe += a.name + ' ' + to_string(a.amount) + '\n';

}

return (new_amount <= 0);

});

cout << recipe << price << endl;

}

else cout << "Sorry, we are closed for today." << endl;

return 0;

}

Подробности реализации

Из интереса и эксперимента ради решение было запрограммировано в двух вариантах: в процедурном, в духе классического языка C, и средствами стандарта C++11. Вторая версия получилась более лаконичной, но, при необходимости, может быть предъявлена и первая.

После считывания списка переменная [latex]total amount[/latex] хранит в себе общее количество всех фруктов на складе.
Метод [latex]get()[/latex] возвращает значение булевого типа, так как таким образом можно производить чтение до конца файла средствами [latex]cin[/latex], с автоматической проверкой.
Для работы только с фруктами, доступными в момент совершения заказы [latex]n[/latex]-м посетителем, была создана переменная [latex]used[/latex], хранящая объем всех коктейлей, сделанных для предыдущих посетителей. В цикле [latex]any of()[/latex] на каждом шаге происходит уменьшение переменной [latex]used[/latex] на доступную массу фруктов данного типа. Для наглядности восприятия введена переменная [latex]new amount[/latex]. Если оставшееся на складе количество фруктов позволяет сделать ещё один коктейль, происходит вход во внутренний цикл. В противном случае, пользователя уведомляют о том, что выполнение заказа невозможно.
Во внутреннем цикле, который выполняется, пока не наберется достаточный объем сока, на каждом шаге берут максимально возможное количество фрукта данного типа. Рецепт сохраняется в строку [latex]recipe[/latex].
В лямбда-выражения параметры из тела программы передаются по ссылке. Возможность их изменения гарантируется ключевым словом [latex]mutable[/latex].