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

Задача

По завершению турнира «Новогодняя ночь» спонсор решил отправить $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

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

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

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

 

Объяснение

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

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

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

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

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

Ссылки

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

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

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

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

Задача

Дорогие ребята!
Наблюдая за тем, как Шарик распиливал нестандартную шахматную доску, я также решил задать для вас задачку: “А сколько разных квадратных и прямоугольных (не считая квадратных) досок мог бы получить при распиливании Шарик из найденной им нестандартной прямоугольной шахматной доски размером $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

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

Объяснение

Ответом на каждый запрос будет количество квадратов и прямоугольников которые можно получить из нашей шахматной доски размера $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.

 

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

Завдання

Троє водіїв вирішили опробувати нове шосе. Перший їхав зі сталою швидкістю $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

Код програми

Пояснення

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

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

Посилання