e-olymp 7824. Без повторений

22/12/2020 by Максим Алексеев

Задача

В натуральном числе $A$ удалили некоторые цифры так, чтобы получить наибольшее натуральное число $B$ с разными цифрами. Какое это число?

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

Натуральное число $x \ (1 \leqslant x \leqslant 10^{100})$.

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

Натуральное число $B$.

Тесты

№	Входные данные	Выходные данные
1	575747	754
2	123231	321
3	314159265359	4192653
4	1092010	9210
5	112221332	213

Код

#include <iostream>
#include <cstring>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    string current_number;
    string ansver = "";
    cin >> current_number;
    set<char> digits_set;    // Инициализируем и заполняем множество со всеми цифрами начального числа
    for (int i = 0; i < current_number.size(); i++){
        char element = current_number[i];
        digits_set.insert(element);
    }
    std::vector<char> digits;
    for (char i : digits_set){
        digits.push_back(i);
    }
    std::reverse(digits.begin(), digits.end());    // Располагаем цифры в порядке убывания
    while (digits.size() != 1){    // Повторяем, пока не нашли все цифры кроме последней
        for (int i=0; i < digits.size(); i++){    // Перебираем цифры в порядке убывания
            char local_max = digits[i];
            int position = current_number.find(local_max);
            string new_number;
            for (int j = position; j < current_number.size(); j++){    // Делаем срез по элементу
                new_number += current_number[j];
            }
            set<char> digits_on_the_right;
            for (int j = 0; j < new_number.size(); j++){    // Находим цифры нового числа
                digits_on_the_right.insert(new_number[j]);
            }
            if (digits.size() == digits_on_the_right.size()){    // Проверяем, сохранится ли ранг ответа
                ansver += local_max;
                digits.erase(digits.begin() + i);
                string number_without_digit = "";
                for (int t = 0; t < new_number.size(); t++){    // Удаляем добавленную в ответ цифру из числа
                    if (new_number[t] != local_max){
                        number_without_digit += new_number[t];
                    }
                }
                current_number = number_without_digit;
                break;    // Останавливаем цикл, т.к. необходимая цифра на позицию уже найдена
            }
        }
    }
    cout << ansver + digits[0];    // Добавляем к ответу последнюю оставшуюся цифру
    return 0;
}

#include <iostream>

#include <cstring>

#include <set>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

string current_number;

string ansver = "";

cin >> current_number;

set<char> digits_set; // Инициализируем и заполняем множество со всеми цифрами начального числа

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

char element = current_number[i];

digits_set.insert(element);

}

std::vector<char> digits;

for (char i : digits_set){

digits.push_back(i);

}

std::reverse(digits.begin(), digits.end()); // Располагаем цифры в порядке убывания

while (digits.size() != 1){ // Повторяем, пока не нашли все цифры кроме последней

for (int i=0; i < digits.size(); i++){ // Перебираем цифры в порядке убывания

char local_max = digits[i];

int position = current_number.find(local_max);

string new_number;

for (int j = position; j < current_number.size(); j++){ // Делаем срез по элементу

new_number += current_number[j];

}

set<char> digits_on_the_right;

for (int j = 0; j < new_number.size(); j++){ // Находим цифры нового числа

digits_on_the_right.insert(new_number[j]);

}

if (digits.size() == digits_on_the_right.size()){ // Проверяем, сохранится ли ранг ответа

ansver += local_max;

digits.erase(digits.begin() + i);

string number_without_digit = "";

for (int t = 0; t < new_number.size(); t++){ // Удаляем добавленную в ответ цифру из числа

if (new_number[t] != local_max){

number_without_digit += new_number[t];

}

current_number = number_without_digit;

break; // Останавливаем цикл, т.к. необходимая цифра на позицию уже найдена

}

cout << ansver + digits[0]; // Добавляем к ответу последнюю оставшуюся цифру

return 0;

}

Нажмите здесь, чтобы выполнить этот код.

Решение

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

Рассмотрим пример: для числа $121323$ правильным ответом будет $213$.

Ход рассуждений следующий: поскольку в числе содержатся три цифры, ответ также будет трехзначным. Наибольшая цифра в числе — 3, следовательно, она должна быть первой цифрой ответа. Для выполнения этого условия придется «вычеркнуть» все предыдущие цифры, но тогда мы сможем получить лишь двухзначное число $32$. Следующим кандидатом является двойка, и этот выбор нас полностью устраивает, поскольку справа от нее есть остальные цифры «входного» числа. Записав в ответ $2$, рассмотрим число за ней: $1323$. Мы можем видеть, что двойка повторяется, однако в ответе ее быть уже не может по условию задачи. Отбросим ее за ненадобностью и рассмотрим получившееся число $133$. Для полученного числа нам необходимо выполнить те же операции, что и для предыдущего, а значит, мы столкнулись с задачей на динамическое программирование (о чем нам, правда, уже заботливо сообщил e-olymp прямо под условием). Рассуждения аналогичны: взять $3$ мы не можем, поскольку это вынудит нас отбросить $1$, что в результате даст нам число $23$, то есть даже меньшее, чем то, что мы получали в начале. Следовательно, добавляем к ответу $1$. Последнюю оставшуюся цифру можно сразу добавлять к ответу, поскольку сравнивать ее не с чем. Получаем искомый ответ — $213$.

Как и оговаривалось вначале, работать будем со строчным представлением числа. До объявления цикла в строке 22 выполняются подготовительные процедуры: создается множество с целью определения цифр, составляющих число, а затем массив, в который помещаются элементы множества в порядке убывания. В теле цикла проходим по всем элементам массива, пока не находим такой, справа от которого будут все остальные элементы. Здесь важно отметить две вещи: во-первых, меня не интересуют сами цифры, имеет значение лишь их количество в соответствующих множествах; во-вторых, поскольку справа от элемента могут находится ему идентичные, включаем его в срез строки и проверяем, можно ли опустить левую часть числа без ущерба количеству цифр в нем. Если да, то этот элемент добавляется в ответ и извлекается из массива для следующего прохода, а если нет — программа переходит к следующему по старшинству элементу.

Ссылки

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

Related Images:

Минимальная реализация алгоритма RSA на C++

06/06/2019 by Андрей Зиновьев

Описание программы

Алгоритм асимметричного шифрования RSA основан на практической сложности факторизации больших чисел, что делает его на сегодняшний день одним из самых популярных криптографических алгоритмов.
Однако он имеет свои отрицательные стороны, например среди них достаточно низкая скорость шифрования, поэтому зачастую используют смешанную криптосистему, в которой сначала две стороны передают симметричный ключ с помощью RSA, а затем шифруют сообщение с помощью какого-либо симметрического алгоритма, например AES.
О самом алгоритме можно почитать например тут.
RSA может шифровать числа до так называемого модуля, который является частью ключа. В настоящее время используются модули длиной в 1024, 2048 и даже 4096 бит. В нашей реализации без длинной арифметики получится иметь дело максимум с 64-битными ключами, однако для наглядности этого хватит. Для того, чтобы сообщение при шифровании многократно не увеличивалось в размере, шифровать его надо блоками по $k — 1$ бит, где $k$ — битность ключа. При этом каждый блок перейдет в $k$-битное число, то есть на больших файлах прирост размера составит всего лишь $\frac{k}{k-1}$ раз, и чем больше ключ — тем меньше этот прирост.
В программе делением массива чисел одной битности на числа другой битности занимается функция resize, дополняя недостающие биты нулями.
Шифрованием и одновременно дешифрованием занимается функция process_bytes, так как в RSA оба этих процесса имеют идентичные алгоритмы, отличающиеся только размером блока входа и выхода. Для этого используется алгоритм быстрого возведения в степень.
Также программа может генерировать ключи на основании предустановленных простых чисел (в будущем случайных), или на основании простых чисел, введенных пользователем. Для этого используется нахождении обратного в кольце по модулю расширенным алгоритмом Евклида.
Программа реализована в интерактивном виде, список команд можно вызвать командой h.

Continue reading →

Related Images:

e-olymp 419. Задача 3n + 1

31/12/2017 by Амир Аль-Омари

Задача

Рассмотрим следующий алгоритм генерации последовательности чисел:

input n
print n
if n = 1 then STOP
if n is odd then n = 3 * n + 1
else n = n / 2
GOTO 2

input n

print n

if n = 1 then STOP

if n is odd then n = 3 * n + 1

else n = n / 2

GOTO 2

Например, для [latex]n[/latex] = 22 будет сгенерирована следующая последовательность чисел:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Полагают (но это еще не доказано), что этот алгоритм сойдется к [latex]n[/latex] = 1 для любого целого [latex]n[/latex]. По крайней мере, это предположение верно для всех целых [latex]n[/latex], для которых 0 < [latex]n[/latex] < 1,000,000.

Длиной цикла числа n будем называть количество сгенерированных чисел в последовательности включая 1. В приведенном примере длина цикла числа 22 равна 16.

Для двух заданных чисел [latex]i[/latex] и [latex]j[/latex] необходимо найти максимальную длину цикла среди всех чисел между [latex]i[/latex] и [latex]j[/latex] включительно.

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

Каждый тест задается в отдельной строке и содержит пару целых чисел [latex]i[/latex] и [latex]j[/latex]. Входные числа будут меньше 1000000 и больше 0. Считайте, что для вычислений достаточно использовать 32 битный целочисленный тип.

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

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

Тесты

Входные данные	Выходные данные
1 10 100 200 201 210 900 1000	1 10 20 100 200 125 201 210 89 900 1000 174
1 10 10 1	1 10 20 10 1 20
5 25 70 54 38 250	5 25 24 70 54 113 38 250 128

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

#include <iostream>
using namespace std;

int length(int ch) {
    int it = 1;
    while (ch != 1) {
        if (ch % 2 == 1) {
            ch = ch * 3 + 1;
        }
        else {
            ch = ch / 2;
        }
        it++;
    }
    return it;
}

int main() {
    int i, j;
    while(cin >> i) {
        cin >> j;
        int it, maxIt = 0;
        for (int a = min(i, j); a <= max(i, j); a++) {
            it = length(a);
            if (it > maxIt) {
                maxIt = it;
            }
        }
        cout << i << ' ' << j << ' ' << maxIt << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int length(int ch) {

int it = 1;

while (ch != 1) {

if (ch % 2 == 1) {

ch = ch * 3 + 1;

}

else {

ch = ch / 2;

}

it++;

}

return it;

}

int main() {

int i, j;

while(cin >> i) {

cin >> j;

int it, maxIt = 0;

for (int a = min(i, j); a <= max(i, j); a++) {

it = length(a);

if (it > maxIt) {

maxIt = it;

}

cout << i << ' ' << j << ' ' << maxIt << endl;

}

return 0;

}

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

Алгоритм, описанный в условии задачи используется для построения сиракузской последовательности. Интересный факт — какое бы число не взять, в конце получаем единицу. Нам же надо посчитать сколько раз должен сработать алгоритм для подсчитывания «длины цикла». Считывая пару чисел из потока ввода я высчитывал «длину цикла» для каждого числа из заданного введенной парой промежутка. После чего сравнивал количество итераций для каждого такого числа и находил максимальное. И так для каждой пары чисел.

Ссылки

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

Related Images:

A1038. Дейкстра?

06/12/2017 by Калачьов Андрій Сергійович

Задача: Имеется [latex]n [/latex] городов. Некоторые из них соединены дорогами известной длины. Вся система дорог задана квадратной матрицей порядка [latex]n [/latex], элемент [latex]a_{ij} [/latex] которой равен некоторому отрицательному числу, если город [latex]i [/latex] не соединен напрямую дорогой с городом [latex]j [/latex] и равен длине дороги в противном случае latex [/latex].

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

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

-1	2	4	-1
2	-1	1	6
4	1	-1	1
-1	6	1	-1

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

1 > 2 = 2

1 > 3 = 3

1 > 4 = 4

Длина кратчайшей цепи, проходящей через все вершины 4

Ссылка на ideone: http://ideone.com/iXjoLZ

Решение:

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

int main(){
    int n,st=0,sum=0; 
    bool p=true;
    cin>>n;
    int GR[n][n]; 
    int distance[n];
    bool visited[n];    
    int index;
    for (int i=0; i<n; i++){
        distance[i]=INT_MAX; visited[i]=false; 
        for (int j=0; j<n; j++){
            cin>>GR[i][j];
            if (GR[i][j]<0 && i!=j)p=false;
        }
    }    
    if (p==true){
        for (int i=0; i<n-1; i++){
            int minl=INT_MAX;
            for (int j=0; j<n; j++){
                if (GR[i][j]<minl && GR[i][j]>0 && j>i) minl=GR[i][j];
            }
            sum+=minl;
        }
    }    
    distance[st]=0;
    for (int p=0; p<n-1; p++){
        int min=INT_MAX;
        for (int i=0; i<n; i++){
            if (!visited[i] && distance[i]<min){
                min=distance[i]; index=i;
            }
        }    
        visited[index]=true;
        for (int i=0; i<n; i++){
            if (!visited[i] && GR[index][i]>0 && distance[index]!=INT_MAX && distance[index]+GR[index][i]<distance[i]){
                distance[i]=distance[index]+GR[index][i]; 
            }
        }    
    }
    for (int i=1; i<n; i++){
        if (distance[i]!=INT_MAX) cout<<st+1<<" > "<<i+1<<" = "<<distance[i]<<endl;
        else cout<<st+1<<" > "<<i+1<<" = "<<"Маршрут недоступен"<<endl;
    }    
    if (p==true) cout<<"Длина кратчайшей цепи, проходящей через все вершины "<<sum;
    else cout<<"Не все вершины графа соединены";
}

#include <iostream>

#include <climits>

using namespace std;

int main(){

int n,st=0,sum=0;

bool p=true;

cin>>n;

int GR[n][n];

int distance[n];

bool visited[n];

int index;

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

distance[i]=INT_MAX; visited[i]=false;

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

cin>>GR[i][j];

if (GR[i][j]<0 && i!=j)p=false;

}

if (p==true){

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

int minl=INT_MAX;

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

if (GR[i][j]<minl && GR[i][j]>0 && j>i) minl=GR[i][j];

}

sum+=minl;

}

distance[st]=0;

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

int min=INT_MAX;

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

if (!visited[i] && distance[i]<min){

min=distance[i]; index=i;

}

visited[index]=true;

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

if (!visited[i] && GR[index][i]>0 && distance[index]!=INT_MAX && distance[index]+GR[index][i]<distance[i]){

distance[i]=distance[index]+GR[index][i];

}

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

if (distance[i]!=INT_MAX) cout<<st+1<<" > "<<i+1<<" = "<<distance[i]<<endl;

else cout<<st+1<<" > "<<i+1<<" = "<<"Маршрут недоступен"<<endl;

}

if (p==true) cout<<"Длина кратчайшей цепи, проходящей через все вершины "<<sum;

else cout<<"Не все вершины графа соединены";

}

Алгоритм: Для решения задачи применим алгоритм Дейкстры. Применяя этот алгоритм мы считаем что у нас нету ребер с отрицательным весом. Если вес ребра отрицательный, то его просто не существует (по условию задачи). Вводим матрицу смежности графа и проверяем является ли граф полным (для задания 2). Если граф является полным, то ищем для каждой вершины инцидентное ребро с минимальным весом и суммируем (задание 2). В цикле каждой вершине присваиваем минимально расстояние до нее от первой вершины и записываем в массив (задание 1).

Related Images:

e-olimp 4852. Кратчайшее расстояние

27/06/2016 by Аня Шохина

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины x до всех остальных вершин графа.

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

В первой строке содержатся два натуральных числа [latex]n[/latex] и [latex]x[/latex] [latex]\left ( 1\leq n\leq 1000,1\leq x\leq n \right )[/latex] — количество вершин в графе и стартовая вершина соответственно. Далее в [latex]n[/latex] строках по [latex]n[/latex] чисел — матрица смежности графа: в [latex]i[/latex]-ой строке на [latex]j[/latex]-ом месте стоит [latex]1[/latex], если вершины [latex]i[/latex] и [latex]j[/latex] соединены ребром, и [latex]0[/latex], если ребра между ними нет. На главной диагонали матрицы стоят нули.

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

Выведите через пробел числа [latex]d_1,d_2,[/latex][latex]\ldots[/latex][latex],d_i[/latex], где [latex]d_i[/latex] равно[latex]-1[/latex], если путей между [latex]x[/latex] и [latex]i[/latex] нет, в противном случае это минимальное расстояние между [latex]x[/latex] и [latex]i[/latex].

Тесты

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

Реализация

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    const int inf=4000; // задаем бесконечность 
    int n, start_position, x; // n-количество вершин,х используем для приема матрицы смежности 
    cin>>n>>start_position;
    start_position--; // в условии счет начинается с единицы, а в программе с нуля 
    vector <int> verges [1001]; //задаем массив векторов, где i-ый вектор содержит в себе номера вершин в которые можно попасть с i-ой вершины
    for (int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>x;
            if (x==1){
                verges[i].push_back(j);
            }
        }
    }
    bool *used = new bool [n];
    for (int i=0; i<n; i++){
        used[i]=false;
    }
    int *distances = new int [n]; //задаем массив расстояний, где i-ый элемент - это расстояние от исходной вершины до  i-ой
    for (int i=0; i<n; i++){
        distances[i]=inf; 
    }
    distances[start_position] = 0;
    for (int i=0; i<n; i++){ //ищем вершину с наименьшей длиной пути до заданной вершины 
        int minimum=inf;
        int position = 0;
        for (int j=0; j<n; j++){
            if (distances[j]<minimum && !used[j]){
                minimum=distances[j];
                position=j;
            }
        }
        used[position]=true; //запоминаем, что применили алгоритм для вершины 
        for (int i=0; i<verges[position].size(); i++){ // применяем алгоритм Дейкстры 
            distances[verges[position][i]] = min(distances[verges[position][i]], (distances[position]+1));
        }
    }
    for (int i=0; i<n; i++) {
        cout<<((distances[i]==inf)?-1:distances[i])<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

const int inf=4000; // задаем бесконечность

int n, start_position, x; // n-количество вершин,х используем для приема матрицы смежности

cin>>n>>start_position;

start_position--; // в условии счет начинается с единицы, а в программе с нуля

vector <int> verges [1001]; //задаем массив векторов, где i-ый вектор содержит в себе номера вершин в которые можно попасть с i-ой вершины

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

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

cin>>x;

if (x==1){

verges[i].push_back(j);

}

bool *used = new bool [n];

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

used[i]=false;

}

int *distances = new int [n]; //задаем массив расстояний, где i-ый элемент - это расстояние от исходной вершины до i-ой

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

distances[i]=inf;

}

distances[start_position] = 0;

for (int i=0; i<n; i++){ //ищем вершину с наименьшей длиной пути до заданной вершины

int minimum=inf;

int position = 0;

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

if (distances[j]<minimum && !used[j]){

minimum=distances[j];

position=j;

}

used[position]=true; //запоминаем, что применили алгоритм для вершины

for (int i=0; i<verges[position].size(); i++){ // применяем алгоритм Дейкстры

distances[verges[position][i]] = min(distances[verges[position][i]], (distances[position]+1));

}

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

cout<<((distances[i]==inf)?-1:distances[i])<<" ";

}

return 0;

}

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

Код на ideone.com

Решение

Для решения данной задачи необходимо применить алгоритм Дейкстры . А именно, мы храним в массиве текущую длину наиболее короткого пути из заданной вершины во все остальные вершины графа. Положим, что изначально длина такого пути равна бесконечности ( при реализации просто используем достаточно большое число). А длина пути из заданной вершины до самой себя равна нулю. Обозначим, что вершина может быть помечена или не помечена. Изначально все вершины являются не помеченными. Далее выбираем вершину [latex]v[/latex] с наименьшей длиной пути до заданной вершины и помечаем ее. Тогда просматриваем все ребра, исходящие из вершины [latex]v[/latex]. Пусть эти ребра имеют вид [latex]\left ( v,t_0 \right )[/latex]. Тогда для каждой такой вершины [latex]t_0[/latex] пытаемся найти наиболее коротки путь из заданной вершины. После чего снова выбираем еще не помеченную вершину и проделываем вышеописанный алгоритм снова до тех пор, пока не останется не помеченных вершин. Найденные расстояния и будут наименьшими.

Related Images:

e-olymp 975

26/06/2015 by Сіренко Валерія Сергіївна

Задача:

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

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

В первой строке содержится количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках находится по n чисел, которые задают матрицу смежности графа. В ней -1 означает отсутствие ребра между вершинами, а любое неотрицательное число — присутствие ребра данного веса. На главной диагонали матрицы всегда расположены нули.

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

Вывести искомое максимальное кратчайшее расстояние.

#include <cstdlib>
#include <iostream>
 using namespace std;
 
int main(){
    int n;
    cin >> n;
    int a[n][n];
    long long maxr = 0;
    for( int i=0 ; i<n ; i++ ){
        for( int j=0 ; j<n ; j++ ){
            cin >> a[i][j];
        }
    }
    for( int k=0 ; k<n ; k++ ){
        for( int i=0 ; i<n ; i++ ){
            for( int j=0 ; j<n ; j++ ){
                if(i != j && a[i][k] != -1 && a[k][j] != -1){
                    if(a[i][j] == -1){
                        a[i][j] = a[i][k] + a[k][j];
                    }
                        else
                    {
                        a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
                    }
                }
            }
        }
    }
    for( int i=0 ; i<n ; i++ )
    {
        for( int j=0 ; j<n ; j++ )
        {
            if(a[i][j] > maxr) maxr = a[i][j];
        }
    }
    cout << maxr << endl;
}

#include <cstdlib>

#include <iostream>

using namespace std;

int main(){

int n;

cin >> n;

int a[n][n];

long long maxr = 0;

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

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

cin >> a[i][j];

}

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

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

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

if(i != j && a[i][k] != -1 && a[k][j] != -1){

if(a[i][j] == -1){

a[i][j] = a[i][k] + a[k][j];

}

else

{

a[i][j] = min(a[i][j], a[i][k] + a[k][j]);

}

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

{

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

{

if(a[i][j] > maxr) maxr = a[i][j];

}

cout << maxr << endl;

}

Задача на e-olimp

Тесты

input	output
4 0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0	16
5 0 5 5 6 -1 -1 0 9 8 4 -1 -1 0 3 8 6 -1 -1 0 5 -1 2 5 6 0	14

Решение:

По алгоритму Флойда (это алгоритм который способствует нахождению кротчайших расстояний между всеми вершинами взвешенного графа, благородя ему мы берем вершину и проверяем если возможно пройти через нее и это будет короче чем идти напрямик, то сохраняем длину пути через эту вершину ) мы проверяем на прочность все связи, иными словами — мы проходим все ребра и проверяем условие. Если существует альтернативный путь от одной вершины к другой, то будет ли он будет короче если да, то мы его заменяем. Таким алгоритмом мы находим все кротчайшие пути через вершины. Но в ответе должен быть максимальный из путей через вершины, поэтому приходится снова пройтись по путям через вершины (но это уже не ребра, а оптимальные длины путей) и найти кратчайший путь максимальной длины.

Related Images:

e-olimp 4856. Кратчайший путь

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

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

Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.

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

Первая строка содержит натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex]\left(n\leq 2000, m\leq 50000 \right)[/latex] — количество вершин и рёбер графа. Вторая строка содержит натуральные числа [latex]s[/latex] и [latex]f[/latex] [latex]\left(1\leq s, f\leq n, s\neq f \right)[/latex] — номера вершин, длину пути между которыми требуется найти. Следующие [latex]m[/latex] строк содержат по три числа [latex]b_{i}[/latex], [latex]e_{i}[/latex] и [latex]w_{i}[/latex]- номера концов [latex]i[/latex]-ого ребра и его вес соответственно [latex]\left(1 \leq b_{i}, e_{i}\leq n, 0\leq w_{i}\leq 100000\right)[/latex].

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

Первая строка должна содержать одно число — длину минимального пути между вершинами [latex]s[/latex] и [latex]f[/latex]. Во второй строке через пробел выведите вершины на кратчайшем пути из [latex]s[/latex] в [latex]f[/latex] в порядке обхода. Если путь из [latex]s[/latex] в [latex]f[/latex] не существует, выведите -1.

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

#include <iostream> 
#include <vector>
#include <set>
#include <utility>
using namespace std;
#define INF 1000000000000
#define MAX 100000

vector <pair <int, long long> > G[MAX];
vector <int> path;
vector <int> ans;
set <pair <long long, int> > q;
long long length[MAX];
int parent[MAX];

int main() {
    ios::sync_with_stdio(false);
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    a--, b--; // начнём отсчёт с 0, для удобства
    for (int i=0; i<m; i++) {
        int from, to, len;
        cin >> from >> to >> len;
        from--, to--;
        G[to].push_back(make_pair(from, len));
        G[from].push_back(make_pair (to, len));
    }
    for (int i=0; i<n; i++) length[i]=INF;
    length[a]=0;
    q.insert (make_pair (length[a], a));
    while (!q.empty()) { // будем выполнять, пока наша очередь не пуста
        int v = q.begin()->second;
        q.erase (q.begin());
        for (int i=0; i<G[v].size(); i++) {
            int to=G[v][i].first, len=G[v][i].second;
            if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять
                   q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них
                   length[to]=length[v]+len; // ставим новую длину
                   parent[to]=v; // и записываем предка
                   q.insert (make_pair (length[to], to));
            }
        }
    }
    if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли
        cout << "-1"; 
        return 0;
    } 
    cout << length[b] << endl;
    int c=b;
    while (c!=a) {
        ans.push_back(c+1); // так как начинали с 1, то увеличиваем
        c=parent[c];
    }
    ans.push_back(a+1);
    cout << ans[ans.size()-1];
    for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];
    cout << endl;
    return 0;   
}

#include <iostream>

#include <vector>

#include <set>

#include <utility>

using namespace std;

#define INF 1000000000000

#define MAX 100000

vector <pair <int, long long> > G[MAX];

vector <int> path;

vector <int> ans;

set <pair <long long, int> > q;

long long length[MAX];

int parent[MAX];

int main() {

ios::sync_with_stdio(false);

int n, m, a, b;

cin >> n >> m >> a >> b;

a--, b--; // начнём отсчёт с 0, для удобства

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

int from, to, len;

cin >> from >> to >> len;

from--, to--;

G[to].push_back(make_pair(from, len));

G[from].push_back(make_pair (to, len));

}

for (int i=0; i<n; i++) length[i]=INF;

length[a]=0;

q.insert (make_pair (length[a], a));

while (!q.empty()) { // будем выполнять, пока наша очередь не пуста

int v = q.begin()->second;

q.erase (q.begin());

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

int to=G[v][i].first, len=G[v][i].second;

if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять

q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них

length[to]=length[v]+len; // ставим новую длину

parent[to]=v; // и записываем предка

q.insert (make_pair (length[to], to));

}

if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли

cout << "-1";

return 0;

}

cout << length[b] << endl;

int c=b;

while (c!=a) {

ans.push_back(c+1); // так как начинали с 1, то увеличиваем

c=parent[c];

}

ans.push_back(a+1);

cout << ans[ans.size()-1];

for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];

cout << endl;

return 0;

}

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

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: алгоритм

e-olymp 7824. Без повторений

Задача

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

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

Тесты

Код

Решение

Ссылки

Related Images:

Минимальная реализация алгоритма RSA на C++

Описание программы

Related Images:

e-olymp 419. Задача 3n + 1

Задача

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

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

Тесты

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

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

Ссылки

Related Images:

A1038. Дейкстра?

Related Images:

e-olimp 4852. Кратчайшее расстояние

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

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

Related Images:

e-olymp 975

Related Images:

e-olimp 4856. Кратчайший путь

Related Images: