---> 33 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

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

Необходимо за минимальную стоимость получить из числа a число b, при этом все промежуточные числа должны быть положительными и не должны превышать n.

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

Входной файл содержит три целых числа: n, a, b (1 ≤ a, b ≤ n ≤ 5000).

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

Если из числа a нельзя получить число b, выведите в выходной файл одно число -1.

Если такая последовательность преобразований существует, в первой строке выходного файла выведите минимальную стоимость требуемого преобразования. Во второй строке выходного файла выведите число k — количество шагов в преобразовании. В последующих k строках выведите сами шаги преобразования по одному в строке. Каждая строка должна иметь вид +число или –число, в зависимости от того, прибавляется или вычитается очередное число.

Примеры
Входные данные
20 12 18
Выходные данные
5
3
-2
+10
-2
Входные данные
100 5 43
Выходные данные
29
8
+5
+1
+1
+1
+13
+26
-5
-4
Входные данные
50 5 43
Выходные данные
-1
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Правительство некоторой всем известной страны решило глобально перестроить дорожную систему – оно уже успело разрушить все дороги, и теперь нужно выстроить дорожную сеть заново. Новые двусторонние дороги можно строить между любыми двумя городами, и стоимость постройки дороги равна расстоянию между соответствующими городами (здесь понимается расстояние между точками на плоскости). Однако в некоторых случаях ландшафт вынуждает построить дорогу за другую цену, такие пары городов называются особыми. Правительство решило первым делом соединить два главных города данной страны – А и Б. Вам поручили разработать план постройки дорог, при котором суммарная стоимость всех построенных дорог будет минимально возможной, и при этом по построенным дорогам можно будет добраться из города А в город Б.

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

Первая строка содержит число $N$ – количество городов в стране ($1 \leq N \leq 10^4$). Каждая из последующих $N$ строк содержит по два целых числа, $x_i$ и $y_i$ – координаты соответствующего города ($|x_i|, |y_i| \leq 10^6$). Далее содержится число $M$ – количество особых пар городов ($0 \leq M \leq min(10^4, N(N-1)/2)$). Далее в $M$ строках содержится описание особых дорог, каждое состоит из трех целых чисел: $u$, $v$ – пара различных городов, между которыми проходит особая дорога, и $w$ – стоимости постройки соответствующей дороги ($1 \leq u, v \leq N$, $0 \leq w \leq 10^6$). В последней строке содержатся номера городов А и Б (от 1 до $N$).

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

Выведите одно число – искомую минимальную длину. Ваш ответ должен отличаться от правильного не более чем на $10^{-5}$.

Примеры
Входные данные
4
1 1
0 0
1 0
0 1
1
1 2 100
2 1
Выходные данные
2.0000000000
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вам дано описание дорожной сети страны. Ваша задача – найти длину кратчайшего пути между городами А и B.

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

Сеть дорог задана во входном файле следующим образом: первая строка содержит числа $N$ и $K$ ($1 \leq N \leq 100000$, $0 \leq K \leq 300000$), где $K$ – количество дорог. Каждая из следующих $K$ строк содержит описание дороги с двусторонним движением – три целых числа $a_i$, $b_i$ и $l_i$ ($1 \leq a_i,b_i \leq N$, $1 \leq l_i \leq 10^6$). Это означает, что имеется дорога длины $l_i$, которая ведет из города $a_i$ в город $b_i$. В последней строке находятся два числа $А$ и $В$ – номера городов, между которыми надо посчитать кратчайшее расстояние ($1 \leq A, B \leq N$)

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

Вы должны вывести в выходной файл единственное число – расстояние между требуемыми городами. Если по дорогам от города $А$ до города $В$ доехать невозможно, выведите –1.

Примеры
Входные данные
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
Выходные данные
115
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке входных данных задано число NUM — количество различных запусков алгоритма Дейкстры (на разных графах). Далее следуют NUM блоков, каждый из которых имеет следующую структуру.

Первая строка блока содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них в пределах от 0 до N–1 каждое и обозначают концы соответствующего ребра, третье — в пределах от 0 до 20000 и обозначает длину этого ребра. Далее, в последней строке блока, записанное единственное число от 0 до N–1 — вершина, расстояния от которой надо искать.

Количество различных графов в одном тесте NUM не превышает 5. Количество вершин не превышает 60000, рёбер — 200000.

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

Выведите на стандартный выход (экран) NUM строк, в каждой из которых по Ni чисел, разделенных пробелами — расстояния от указанной начальной вершины взвешенного неориентированного графа до его 0-й, 1-й, 2-й и т. д. вершин (допускается лишний пробел после последнего числа). Если некоторая вершина недостижима от указанной начальной, вместо расстояния выводите число 2009000999 (гарантировано, что все реальные расстояния меньше).

Примечание

Убедитесь, что программа правильно учитывает, что за один запуск следует обработать несколько различных графов.

Указания.

Чтобы обеспечить асимптотическую оценку времени выполнения , следует:

1. Представлять граф списками смежности и делать перебор соседей аналогично задаче «Поиск в ширину – 1».

2. При выборе, какая именно вершина статуса 1 имеет наименьшую оценку расстояния, пользоваться пирамидой.

Поскольку списками смежности следует подать взвешенный граф, то граф уже нельзя представить как vector<list<int> >. Элементами списков должны быть структуры из двух полей (вершина, куда идет ребро, и длина ребра). Например, можно объявить тип

struct edge

{

  unsigned int v; / / номер вершины, куда идет ребро

  unsigned int len; / / длина этого ребра

};

и после этого граф в целом можно будет представить как vector<list<edge> >. При переборе соседей вершины curr с помощью цикла

for(list<edge>::iterator w = graph[curr].begin() ;

                         w != graph[curr].end() ; w++)   w будет итератором уже не списка чисел, а списка структур; поэтому, чтобы узнать номер вершины, куда ведет соответствующее ребро, следует обратиться к полю w->v, а чтобы узнать вес этого ребра — к полю w->len.

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

struct estdata

{

  unsigned int v; // номер вершины

  unsigned int est; // оценка расстояния этой вершины

};

Тогда пирамида может быть объявлена как переменная типа priority_queue<estdata>. Чтобы программу с переменной такого типа можно было хотя бы скомпилировать, необходимо задать правило, по которому будет определяться, какой из двух элементов типа estdata меньше и какой больше. Ведь не зная, что больше и что меньше, невозможно поддерживать основное свойство priority_queue (каждый элемент больше-равен своих сыновей).

Один из способов задать такое правило — перегрузить (overload) операцию сравнения путем написания функции

bool operator < (const estdata &d1, const estdata &d2)

{

  return d1.est > d2.est;

}

где estdata — имя типа, для которого задаем правило сравнения; перегружать надо именно operator < (а не operator > и не operator <=); в теле функции, которая задает правило для <, в данном случае пишем >, так как priority_queue размещает в корне максимальный элемент, а нам нужно эффективно извлекать вершину с минимальной оценкой.

Еще одну мелкую проблему создает то, что при выполнении алгоритма Дейкстры возможно изменение оценки расстояния до вершины статуса 1 (когда новый маршрут оказывается короче найденного ранее). Шаблон priority_queue не позволяет изменять значения элемента, вставленного в пирамиду ранее. Поэтому при изменении оценки на меньшую приходится вставлять в пирамиду еще один элемент с меньшим полем est и таким же полем v.

Благодаря правилам выбора элементов из пирамиды, первой среди всех структур с одинаковым полем v будет обработано ту, у которой минимальное поле est. Благодаря этому, повторные вставки никак не влияют ни на правильность алгоритма, ни на асимптотические оценки времени, Θ(M) памяти. Нужно только при вынимании очередного элемента из пирамиды проверять, а не вынимали ли эту вершину раньше. Причем, делать эту проверку просто: если вершина имеет статус 1, ее вынули впервые; если статус 2 — ее вынимали и обрабатывали прежде.

Итак, находить, какую вершину следует сделать новой текущей, можно, например, так:

while (!the_heap.empty() && st[the_heap.top().v] == 2)

  the_heap.pop (); // пропускаем все структуры, соответствующие

                   // повторным вхождением уже обработанных элементов

if(the_heap.empty()) // пирамида пуста — значит, все достижимые вершины

  break; // уже обработаны и пора завершать основной цикл

curr = the_heap.top().v; // запоминаем как новую текущую вершину

      // с минимальной оценкой;

      // раз дошли сюда после предыдущих while и if,

      // она существует и ещё не обработана

the_heap.pop(); // вынимаем запомненную в curr вершину из пирамиды

Здесь the_heap — пирамида (переменная типа priority_queue<estdata>), st — вектор (массив) статусов вершин, curr — номер текущей (для следующей итерации большого цикла) вершины.

Если писать пирамиду вручную, можно не вставлять в пирамиду новый элемент с таким же полем v, а уменьшать поле est ранее вставленного элемента. Но для этого надо постоянно поддерживать информацию о том, где именно в пирамиде (в каком по номеру элемента массива) находится каждая вершина статуса 1. Это достаточно сложно, и этого часто все равно не делают (т. е. все равно вставляют в пирамиду копии).

Бонусное задание. Докажите, что повторная вставка элементов с тем же полем v действительно не ухудшает асимптотические оценки времени, Θ(M) памяти.

Примеры
Входные данные
1
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
1
Выходные данные
18 0 5 2 8 
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Во время летних каникул Вася и Петя путешествовали со своими родителями по Одной Очень Гостеприимной Стране. В этой стране всего N городов, пронумерованных числами от 1 до N. Маршрут Васи начинался в городе A и заканчивался в городе B, а маршрут Пети – начинался в городе C и заканчивался в городе D. Поскольку времени у них было немного, то и Васины и Петины родители выбрали самый короткий путь, соединяющий начальный и конечный города их маршрута.

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

Определите, в каких городах побывали и Вася и Петя и выведите их номера в порядке возрастания. Если же маршруты ребят не пересекались, выведите -1.

Обратите внимание на то, что поскольку на некоторых дорогах шел ремонт, то длина пути от города X в город Y может отличаться от длины пути от города Y в город X.

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

В первой строке вводится число N (1 ≤ N ≤ 100). В следующих N строках вводится по N чисел, не превосходящих 100, j-ое число в i-ой строке равно длине пути между i-м и j-м городом. Известно, что между любыми двумя городами есть дорога и поскольку на некоторых дорогах идет ремонт, то длина пути от города X в город Y может отличаться от длины пути от города Y в город X. В следующих двух строках вводятся пары целых числа от 1 до 100 – номера городов, являющихся началом и концом маршрута Васи (A и B), и аналогичные числа для Пети (C и D).

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

Выведите их номера в порядке возрастания. Если маршруты ребят не пересекались, выведите одно число  - 1. Гарантируется, что кратчайший путь – единственный.

Примеры тестов

Входные данные
4
0 100 100 1
100 0 3 100
100 4 0 1
100 3 10 0
1 3
2 3
Выходные данные
2 3 


Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест