e-olymp 34. Слово спонсора

06/12/2019 by Артем Рогулин

Задача

По завершению турнира «Новогодняя ночь» спонсор решил отправить $m$ призерам подарки по почте. Зная количество участников $n$ и время доставки почты между некоторыми отделениями «Укрпочты», найти, через какое минимальное время последний из призеров получит свой приз.

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

Первая строка содержит $3$ числа: количество участников турнира $n$, количество призов спонсора $m$ и количество известных временных сроков доставки между некоторыми из отделений $k$. В следующей строке через пробел указаны номера участников, ставших призёрами.

Далее идет $k$ строк по $3$ числа в каждой с информацией об известных сроках доставки между некоторыми из отделений в формате: $a$ $b$ $t$, где $a$ и $b$ — номера отделений, $t$ $(0 \leqslant t \leqslant 365)$ — время доставки почты между ними. В последней строке находится единственное число — номер почтового отделения, из которого спонсор будет отправлять призы. Известно, что $1 \leqslant n, m, a, b \leqslant 365$.

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

Если все призы будут доставлены участникам — вывести в первой строке «The good sponsor!», а в следующей — время, через какое последний из призеров получит свой приз. Если хотя бы один из участников не сможет получить приз — вывести в единственной строке «It is not fault of sponsor…». Фразы выводить без кавычек.

Тесты

№	Входные данные	Выходные данные
1.	3 2 2 2 3 1 2 3 2 3 4 1	The good sponsor! 7
2.	5 1 4 5 1 3 2 2 3 3 4 2 5 4 5 6 1	The good sponsor! 16
3.	7 2 6 1 3 1 3 2 2 4 32 4 5 94 3 1 0 6 2 4 7 2 3 7	It is not fault of sponsor…
4.	5 2 6 1 2 3 1 1 3 4 2 2 4 3 5 1 4 4 5 5 2 3 7 2	The good sponsor! 6

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

Первый вариант

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

int main() {
    int n, m, k; // Количество вершин, количество победителей и количество ребер
    cin >> n >> m >> k;
    vector<int> winner(m); // Вершины, которые нам нужно достичь
    for(int i = 0; i < m; i++) 
    {
        cin >> winner[i];
        winner[i]--; // В задаче отсчёт идёт с 1, поэтому мы уменьшаем все индексы на 1
    }
    vector<vector<vector<int>>> path(n); // Список смежности с весом
    for(int i = 0; i < k; i++)
    {
        int a, b, t;
        cin >> a >> b >> t; // Соединённые вершины и вес ребра
        a--;// Сдвиг индексов на 1
        b--;
        path[a].push_back({b, t}); // В список путей из вершины 'а' добавляем вершину 'b' и длину пути
        path[b].push_back({a, t}); 
    }
    int start; // Вершина, с которой мы начинаем
    cin >> start;
    start--; // Сдвигаем индекс
    vector<int> count(n, -1); // Счётчик длины путей
    count[start] = 0; // Мы находимся в этой вершине, поэтому дистанция до неё равна 0
    queue<int> plan; // Наш план посещения вершин. Так как мы используем BFS, то это контейнером является очередь
    plan.push(start); // Кладём нашу стартовую вершину в план
    while(!plan.empty()) // Наш BFS
    {
        start = plan.front(); 
        plan.pop();
        for(auto next: path[start]) // Достаём наши пары  вершина + вес
        {
            if(count[next[0]] == -1 || count[next[0]] > count[start] + next[1]) // Если вершина не посещена или путь через ту на котором мы сейчас более короткий
            {
                plan.push(next[0]); // Мы добавляем эту вершину в план
                count[next[0]] = count[start] + next[1]; // И отмечаем дистанцию до неё
            }
        }
    }
    bool delivered = true; // Предпологаем, что мы побывали во всех вершинах, которые нам нужны
    int longest = 0; // Положим максимальную дистанцию равной нулю
    for(int i = 0; i < m && delivered; i++)
    {
        if(count[winner[i]] == -1) // Если путь до нужной вершины не был найден
        {
            delivered = false; // Отмечаем, что мы побывали не везде, где надо
        }
        longest = max(count[winner[i]], longest);
    }
    if(delivered) // Если нужные вершины посещены
    {
        cout << "The good sponsor!\n" << longest; // Выводим фразу и длину пути до самой далёкой вершины
    }
    else
    {
        cout << "It is not fault of sponsor...";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

int main() {

int n, m, k; // Количество вершин, количество победителей и количество ребер

cin >> n >> m >> k;

vector<int> winner(m); // Вершины, которые нам нужно достичь

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

{

cin >> winner[i];

winner[i]--; // В задаче отсчёт идёт с 1, поэтому мы уменьшаем все индексы на 1

}

vector<vector<vector<int>>> path(n); // Список смежности с весом

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

{

int a, b, t;

cin >> a >> b >> t; // Соединённые вершины и вес ребра

a--;// Сдвиг индексов на 1

b--;

path[a].push_back({b, t}); // В список путей из вершины 'а' добавляем вершину 'b' и длину пути

path[b].push_back({a, t});

}

int start; // Вершина, с которой мы начинаем

cin >> start;

start--; // Сдвигаем индекс

vector<int> count(n, -1); // Счётчик длины путей

count[start] = 0; // Мы находимся в этой вершине, поэтому дистанция до неё равна 0

queue<int> plan; // Наш план посещения вершин. Так как мы используем BFS, то это контейнером является очередь

plan.push(start); // Кладём нашу стартовую вершину в план

while(!plan.empty()) // Наш BFS

{

start = plan.front();

plan.pop();

for(auto next: path[start]) // Достаём наши пары вершина + вес

{

if(count[next[0]] == -1 || count[next[0]] > count[start] + next[1]) // Если вершина не посещена или путь через ту на котором мы сейчас более короткий

{

plan.push(next[0]); // Мы добавляем эту вершину в план

count[next[0]] = count[start] + next[1]; // И отмечаем дистанцию до неё

}

bool delivered = true; // Предпологаем, что мы побывали во всех вершинах, которые нам нужны

int longest = 0; // Положим максимальную дистанцию равной нулю

for(int i = 0; i < m && delivered; i++)

{

if(count[winner[i]] == -1) // Если путь до нужной вершины не был найден

{

delivered = false; // Отмечаем, что мы побывали не везде, где надо

}

longest = max(count[winner[i]], longest);

}

if(delivered) // Если нужные вершины посещены

{

cout << "The good sponsor!\n" << longest; // Выводим фразу и длину пути до самой далёкой вершины

}

else

{

cout << "It is not fault of sponsor...";

}

return 0;

}

Второй вариант

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

int main() {
    int n, m, k;
    cin >> n >> m >> k; // Количество вершин
    vector<int> winner(m);
    for (int i = 0; i < m; i++) // Нужные нам вершины
    {
        cin >> winner[i];
        winner[i]--; // Сдвиг индекса, так как у нас отсчёт в задаче начинается с 1, а в коде с нуля
    }
    vector<vector<int>> path(n, vector<int>(n, 1e6)); // Матрица смежности (1е6 значит, что ребра нет)
    for (int i = 0; i < k; i++)
    {
        int a, b, t;
        cin >> a >> b >> t;
        a--; //Свдиг индекса
        b--;
        if (path[a][b] > t)
        {
            path[a][b] = t;
            path[b][a] = t;
        }
    }
    int start; // Вершина, в которой мы находимся
    cin >> start;
    start--; // Сдвиг индекса
    vector<int> count(n, 1e6); // Счётчик пути до вершин
    vector<bool> used(n, false); // Посещена ли вершина
    count[start] = 0;
    while (start != -1) // Алгоритм Дейкстры
    {
        int next = -1, mini = 1e6;
        for (int j = 0; j < n; j++)
        {
            if (count[j] > count[start] + path[start][j]) // Обновляем расстояние до смежных вершин
            {
                count[j] = count[start] + path[start][j];
            }
            if (count[j] < mini && !used[j]) // Ищем непосещённую вершину с минимальным расстоянием
            {
                next = j;
                mini = count[j];
            }
        }
        used[start] = true; // Отмечаем, что данную вершину мы посетили
        start = next; // Переходим в следующую вершину
    }
    bool deliver = true; // Предположим, что посетили все вершины
    int longest = 0; // Ставим значение, равное минимальному возможному расстоянию
    for (int i = 0; i < m && deliver; i++)
    {
        if (!used[winner[i]]) // Проверяем всем ли победителям доставили призы
        {
            deliver = false;
        }
        longest = max(count[winner[i]], longest); // Ищем максимальную дистанцию
    }
    if (deliver) // Если доставили призы всем
    {
        cout << "The good sponsor!\n" << longest;
    }
    else // Иначе
    {
        cout << "It is not fault of sponsor...";
    }

    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

int n, m, k;

cin >> n >> m >> k; // Количество вершин

vector<int> winner(m);

for (int i = 0; i < m; i++) // Нужные нам вершины

{

cin >> winner[i];

winner[i]--; // Сдвиг индекса, так как у нас отсчёт в задаче начинается с 1, а в коде с нуля

}

vector<vector<int>> path(n, vector<int>(n, 1e6)); // Матрица смежности (1е6 значит, что ребра нет)

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

{

int a, b, t;

cin >> a >> b >> t;

a--; //Свдиг индекса

b--;

if (path[a][b] > t)

{

path[a][b] = t;

path[b][a] = t;

}

int start; // Вершина, в которой мы находимся

cin >> start;

start--; // Сдвиг индекса

vector<int> count(n, 1e6); // Счётчик пути до вершин

vector<bool> used(n, false); // Посещена ли вершина

count[start] = 0;

while (start != -1) // Алгоритм Дейкстры

{

int next = -1, mini = 1e6;

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

{

if (count[j] > count[start] + path[start][j]) // Обновляем расстояние до смежных вершин

{

count[j] = count[start] + path[start][j];

}

if (count[j] < mini && !used[j]) // Ищем непосещённую вершину с минимальным расстоянием

{

next = j;

mini = count[j];

}

used[start] = true; // Отмечаем, что данную вершину мы посетили

start = next; // Переходим в следующую вершину

}

bool deliver = true; // Предположим, что посетили все вершины

int longest = 0; // Ставим значение, равное минимальному возможному расстоянию

for (int i = 0; i < m && deliver; i++)

{

if (!used[winner[i]]) // Проверяем всем ли победителям доставили призы

{

deliver = false;

}

longest = max(count[winner[i]], longest); // Ищем максимальную дистанцию

}

if (deliver) // Если доставили призы всем

{

cout << "The good sponsor!\n" << longest;

}

else // Иначе

{

cout << "It is not fault of sponsor...";

}

return 0;

}

Объяснение

В данной задаче нам нужно построить граф, где будет $n$ вершин (по количеству участников) и $k$ рёбер (по количеству путей). Граф будет взвешенный и неориентированный. Также у нас будет список $m$ вершин (наши победители) и нам нужно проверить, достижимы ли они из начальной вершины (её номер указывается отдельно в самом конце).

К первому варианту кода

Итак, по входным данным мы строим список смежности и после запускаем поиск в ширину (BFS) из стартовой вершины. Так как граф взвешенный, расстоянием до вершины будем считать совокупный вес рёбер на пути к ней от стартовой вершины. Находясь в какой-либо вершине, мы проверяем, куда мы можем попасть из неё. Если сопряжённая вершина не посещена, то мы добавляем её в план. А если она уже посещена, мы проверяем, будет ли путь через вершину в которой мы находимся, короче того пути, которым мы добирались до этой сопряжённой вершины ранее. Если это так, то мы просто заменяем значение в счётчике пути для сопряжённой вершины и добавляем её в план, ведь если путь до неё стал короче, то и путь «через» неё тоже. После того, как мы нашли наикратчайшие пути до всех достижимых вершин, мы проверяем достигли ли мы всех из списка победителей и находим расстояние до самого дальнего из них. И вывод в зависимости от результата.

Ко второму варианту кода

По входным мы строим матрицу смежности. Для несуществующих рёбер мы ставим значение бесконечность ($10^6$ нам подходит, так как это то значение, которое нам не достичь по ограничениям), а для остальных — их вес. А дальше, из стартовой вершины мы запускаем алгоритм Дейкстры, находя кратчайшие пути до каждой вершины. После идёт проверка, всех ли необходимых вершин мы достигли и расстояние до самой дальней из них. И вывод, в зависимости от результата.

Ссылки

E-olymp (условие).

Ideone (первый вариант кода).

Ideone (второй вариант кода).

Related Images:

e-olymp 566. Письмо почтальона Печкина

05/12/2019 by Артем Рогулин

Задача

Дорогие ребята!
Наблюдая за тем, как Шарик распиливал нестандартную шахматную доску, я также решил задать для вас задачку: “А сколько разных квадратных и прямоугольных (не считая квадратных) досок мог бы получить при распиливании Шарик из найденной им нестандартной прямоугольной шахматной доски размером $M\times N$?”

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

В первой строке количество заданий Печкина $K$, в последующих $K$ строках по два целых числа $M$ и $N$ $(1 \leqslant K, M, N \leqslant 100)$, разделённых пробелом.

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

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

Тесты

№	Входные данные	Выходные данные
1.	1 3 2	8 10
2.	2 4 4 2 2	30 70 5 4
3.	4 3 3 25 46 100 100 1 1	14 22 12350 338975 338350 25164150 1 0

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

#include <iostream>
using namespace std;

int main() {
    int k; // Количество заданий
    cin >> k;
    for(int l = 0; l < k; l++)
    {
        int m, n; // Размер шахматной доски
        cin >> m >> n;
        int res = 0; // Количество кусков, на которые мы можем разделить доску
        for(int i = min(m, n); i >= 0; i--) // Находим количество квадратов
        {
            res += (m - i) * (n - i);
        }
        cout << res; // Вывод количества квадратных досок
        res = res * - 1; // Чтобы не учитывать квадратные доски, сразу вычитаем их
        for(int i = m - 1; i >= 0; i--) // Находим количество прямоугольников
        {
            for(int j = n - 1; j >= 0; j--) 
            {
                res += (m - i) * (n - j);
            }
        }
        cout << ' ' << res << endl; // Вывод количества прямоугольников
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k; // Количество заданий

cin >> k;

for(int l = 0; l < k; l++)

{

int m, n; // Размер шахматной доски

cin >> m >> n;

int res = 0; // Количество кусков, на которые мы можем разделить доску

for(int i = min(m, n); i >= 0; i--) // Находим количество квадратов

{

res += (m - i) * (n - i);

}

cout << res; // Вывод количества квадратных досок

res = res * - 1; // Чтобы не учитывать квадратные доски, сразу вычитаем их

for(int i = m - 1; i >= 0; i--) // Находим количество прямоугольников

{

for(int j = n - 1; j >= 0; j--)

{

res += (m - i) * (n - j);

}

cout << ' ' << res << endl; // Вывод количества прямоугольников

}

return 0;

}

Объяснение

Ответом на каждый запрос будет количество квадратов и прямоугольников которые можно получить из нашей шахматной доски размера $M\times N$. Для вычисления количества квадратов нам надо посчитать, сколько квадратов каждого возможного размера поместится в нашей шахматной доске. Аналогично для прямоугольников. Пример с доской $3\times 2$ разобран на картинке.

Пояснение к первому тесту

Для подсчёта квадратов, нам следует отдельно считать их количество для каждого возможного размера. Таким образом сначала идут квадраты $1\times 1$, то есть $M\cdot N$ квадратов. Далее, квадратов $2\times 2$ помещаются ровно на $1$ меньше горизонтально и на $1$ меньше вертикально, значит получаем $(M-1)\times (N-1)$. Соответственно, $(M — 2)\times (N — 2)$ для квадратов $3\times 3$. И так продолжаем пока квадрат помещается в нашу доску.

Аналогично мы поступаем и с прямоугольниками. Однако считая количество прямоугольников каждого размера, нам нужно считать сколько поместится прямоугольников размера $(1\times 1), (1\times 2)\dots (1\times N)$. Также $(2\times 1), (2\times 2)\dots (2\times N)$. И так до $(M\times 1), (M\times 2)\dots (M\times N)$. Это довольно просто реализовать используя вложенный цикл.

Не стоит забывать, что квадрат — тот же прямоугольник, но с равными сторонами и в нашем цикле мы считаем все прямоугольники. А так как квадраты мы не должны учитывать, то после нахождения числа прямоугольников, нам нужно вычесть из него количество квадратов. В коде после нахождения и вывода числа квадратов, мы домножили это число на $(-1)$ и и уже после прибавили к нему количество прямоугольников, таким образом не учитывая квадраты.

Ссылки

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

Код на ideone.

Related Images:

e-olymp 9081. Автомобілі

30/11/2019 by Артем Рогулин

Завдання

Троє водіїв вирішили опробувати нове шосе. Перший їхав зі сталою швидкістю $v_1$ км/год. протягом $t_1$ годин. Другий їхав зі сталою швидкістю $v_2$ км/год. протягом $t_2$ годин, третій – зі сталою швидкістю $v_3$ км/год. протягом $t_3$ годин. Хто з них проїхав найдовший шлях?

Вхідні дані

В одному рядку через пропуск ввести на стандартний пристрій введення значення $v_1$, $v_2$, $v_3$, $t_1$, $t_2$, $t_3$. Інтервал значень швидкостей – від $30$ до $100$ км/год. включно. Час у дорозі – з інтервалу $[1;15]$ годин.

Вихідні дані

Якщо найдовший шлях проїхав один водій, вивести на стандартний пристрій введення номер водія. Якщо найдовший шлях проїхали два або три водія, треба ввести в одному рядку через пропуск їх номери у порядку зростання.

Тести

№	Вхідні дані	Вихідні дані
1.	38 9 54 5 62 3	1
2.	30 9 45 6 90 3	1 2 3
3.	30 15 45 5 50 9	1 3
4.	50 6 42 14 84 7	2 3

Код програми

#include <iostream>
using namespace std;
 
int main() {
    int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв
    int t1, t2, t3; // Час, який вони їхали
    int s1, s2, s3; // І відстань
    int max_; // Також, змінну, де буде зберігатися максимальна відстань
    cin >> v1 >> t1; // Прочитуємо швидкість і час для кожного водія
    cin >> v2 >> t2; 
    cin >> v3 >> t3;
    s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них
    s2 = v2 * t2; 
    s3 = v3 * t3;
    max_ = max(max(s1, s2), s3); // Виявляємо максимальну відстань
    if ( s1 == max_ )  // Перевіряючи, чи є пройдена відстань максимальною
        cout << "1 "; // Виводимо номер відповідного водія
    if ( s2 == max_ )
        cout << "2 ";
    if ( s3 == max_ )
        cout << 3;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв

int t1, t2, t3; // Час, який вони їхали

int s1, s2, s3; // І відстань

int max_; // Також, змінну, де буде зберігатися максимальна відстань

cin >> v1 >> t1; // Прочитуємо швидкість і час для кожного водія

cin >> v2 >> t2;

cin >> v3 >> t3;

s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них

s2 = v2 * t2;

s3 = v3 * t3;

max_ = max(max(s1, s2), s3); // Виявляємо максимальну відстань

if ( s1 == max_ ) // Перевіряючи, чи є пройдена відстань максимальною

cout << "1 "; // Виводимо номер відповідного водія

if ( s2 == max_ )

cout << "2 ";

if ( s3 == max_ )

cout << 3;

return 0;

}

Пояснення

Відповіддю до задачі є номери водіїв, що проїхали максимальну відстань. Для цього треба використати формулу, знайому всім ще зі школи: $S = Vt$. Після знаходження відстані пройденої кожним водієм, ми знаходимо максимальну серед них. Далі нам залишається тільки виводити у порядку зростання номери водіїв, які пройшли максимальну відстань.

Примітка: Швидкість і час вводяться попарно для кожного водія.