Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 44 45 46 47 48 49 50 >> Отображать по:
#391
Уборка снега
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вася очень хочет попасть на сборы в СУНЦ и, к счастью, живет недалеко от него. Поэтому он решил дойти до места проведения сборов пешком. Васе известен план города - какие перекрестки соединены улицами и сколько времени требуется, чтобы пройти по каждой улице. Движение по любой улице разрешено в обе стороны.

Администрация города, однако, решила устроить в этот день уборку улиц от снега. Если на какой-то из улиц происходит уборка, то движение по ней замедляется в два раза. В распоряжении города есть K снегоуборочных машин.

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

Дом Васи находится около перекрестка с номером 1, а СУНЦ - около перекрестка с номером N. Таким образом, перемещение Васи от дома до СУНЦа выглядит следующим образом. В начале глава выбирает дороги, на которых будет проводиться уборка, затем Вася выбирает улицу, по которой он пойдет от перекрестка 1 (Вася достаточно наблюдателен, чтобы заметить, на каких улицах идет уборка). Когда он доходит до конца выбранной улицы и оказывается на перекрестке, процесс повторяется: глава вновь выбирает улицы для уборки, и машины туда мгновенно перемещаются, а затем Вася - улицу, по которой идти, и т. д. Процесс продолжается, пока Вася не попадет в СУНЦ.

Ваша задача - выяснить, за какое минимально возможное время Васе удастся достичь СУНЦа при условии, что глава администрации всегда действует оптимально.

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

Первая строка содержит числа N - количество перекрестков в городе, M - количество улиц и K - количество снегоуборочных машин (1 <= N <= 100, 0 <= K <= M <= 20000). Следующие M строк содержат описания улиц в следующем формате: a и b - номера перекрестков, которые данная улица соединяет, t - время движения по данной улице (целое положительное число, не превосходящее 1000).

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

Выведите одно число - минимальное время, за которое Вася может добраться до СУНЦа. или -1, если добраться туда невозможно.

Система оценки
  • Подзадача 1 (30 баллов) \( n, m \le 50\).
  • Подзадача 2 (20 баллов) \(n \le 50\). Необходимые подгруппы: 1.
  • Подзадача 3 (50 баллов) без дополнительных ограничений. Необходимые подгруппы: 1-2.
Пример 
3 3 2
1 2 3
1 3 5
2 3 1
Ответ 8
Примеры
Входные данные
3 3 2
1 2 3
1 3 5
2 3 1
Выходные данные
8
#394
K задач (A)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

K участникам сборов для решения было предложено K задач. Участники решили разделить задачи между собой, решить каждому по одной задаче, а затем обменяться решениями (они не учли, что система ejudge способна отследить данный факт J). Известно ориентировочное время, за которое каждый из участников сборов может решить каждую из предложенных задач.

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

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

Во входном файле сначала записано число K (0 < K < 101) и далее K2 неотрицательных целых чисел, не превосходящие 20000, описывающих матрицу K x K, времен решения каждым из участников каждой из задач.

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

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

input.txt output.txt
2

1 2

2 4

 4
#395
Коровы
  
Темы: [Потоки]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке входного файла записано число досок N (0 <= N <= 1000). Далее для каждой доски записаны координаты кочек - концов доски (-231 <= Xi,Yi <= 231). Затем записаны координаты начальной и конечной точек (точки различны и доски, их соединяющей нет). Все числа во входном файле целые.

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

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

Примеры
Входные данные
8
0 0 1 0     
1 0 2 1    
1 0 2 -1
2 1 3 0     
2 -1 3 0  
1 0 4 0
3 0 4 0     
0 0 3 0    
0 0 
4 0
Выходные данные
2
#397
Цена и длина
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В саду растут деревья. У каждого есть цена и длина. Чтобы построить забор какой-то длины L, нужно срубить деревьев с суммарной длиной L или больше. Нужно, срубив некоторые деревья, построить забор вокруг оставшихся. При этом нужно потратить как можно меньше денег. Если таких способов несколько, нужно выбрать тот, в котором деревьев рубится меньше. Если и таких несколько, выведите любой. Деревья считаются имеющими нулевой радиус.

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

Во входном файле записано число деревьев N (2 <= N <= 14), а затем каждое дерево описано четырьмя числами xi, yi, vi, li - координаты (целые от -10000 до 10000), цена и длина (от 0 до 10000).

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

В выходной файл выведите номера деревьев, которые необходимо срубить, а также излишек срубленного материала. Формат выходных данных - см. примеры выходных файлов.

Примеры
Входные данные
5
0 0 1000 11
0 3 1000 11
3 0 1000 11
3 3 1000 11
1 1 100  12
Выходные данные
Cut these trees: 5
Extra wood: 0.00
Входные данные
2
100 100 100 100
0   1   100 100
Выходные данные
Cut these trees: 1
Extra wood: 100.00
#404
Кинотеатр
  
Источники: [ Командные олимпиады, ВКОШП, 2006, Задача B ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Числа расставляются в одном прямоугольнике по строкам, в другом - по столбцам. Необходимо подсчитать количество совпадающих чисел, стоящих на одинаковых местах.

Марья Ивановна с Марьей Михайловной привели школьников в кинотеатр. Чтобы не было никаких обид, Марья Ивановна построила всех школьников по алфавиту и рассадила их: сначала в первый ряд слева направо, затем во второй слева направо и т.д., заполнив весь зал из n рядов по m кресел. Тут пришла Марья Михайловна и сказала, что ребята сели неправильно – надо пересесть. Она предложила сначала заполнить все первые места от первого ряда к последнему, затем все вторые места и т. д.

Определите, сколько школьников после такой пересадки останется на своем месте.

Например, если n = 3 и m = 3, то в первом случае дети сядут так:

1 2 3
4 5 6
7 8 9
а во втором – так:
1 4 7
2 5 8
3 6 9

Таким образом, три школьника: 1, 5 и 9 останутся на своих местах.

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

Вводятся два целых числа n и m (\(1 \le n, m \le 10^9\)).

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

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

Примеры
Входные данные
3 3
Выходные данные
3
Входные данные
2 4
Выходные данные
2
Страница: << 44 45 46 47 48 49 50 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест