Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Задача 1«Тролли и физика».

Пусть каждой дуге (i, j) графа (I, U) поставлено в соответствие число называемое длиной дуги.

Рассмотрим задачу: определить кратчайший путь из множества А в множество В, пересекающий каждое множество разбиения один и только один раз. Очевидно, что если каждое множество разбие­ния состоит из одного элемента и , то имеем обычную задачу коммивояжера.

Определим функцию : положим для произвольного пути .Итак, значениями функции будут множества номеров подмножеств разбиения, которые пересекает путь . Пусть каждое множество Ф_i, , состоит из всевозможных подмножеств множества {1, 2,..., p},a . Применим для решения этой задачи следующий алгоритм.

Достаточной системой функций в данном случае будут функции

Обозначим через число элементов произвольного конечного множества А.

Шаг 0. Положим . Пометим вершины признаками . Для помеченных вершин увеличим на 1. Рассмотрим одну из пометок и перейдем к шагу 1.

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

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

Шаг 2. Строим кратчайший допустимый путь от вершины . Пусть - пометка вершины, для которой . Перейдём к вершине и рассмотрим пометку вершины,

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

Шаг 3. Пусть - множество помеченных вершин. Рассмотрим все возможные числа при . Определим среди этих чисел наименьшее и возьмем его за новое приближение к длине искомого пути. Затем перейдем к шагу 1.

Этот алгоритм можно изменить. Если для некоторой пометки при всех j, для которых или , то путь соответствующий этой пометке, уже продленво все смежные с вершины. Следовательно, для таких пометок при­знаки можно стирать.

Задача 1«Тролли и физика».

ограничение по времени на тест: 2 секунды

ограничение по памяти на тест: 64 мегабайта

ввод: stdin

вывод: stdout

— А что это за звуки, вон там? – спросила Алиса, кивнув на весьма укромные заросли какой-то симпатичной растительности на краю сада.

— А это чудеса, – равнодушно пояснил Чеширский Кот.

— И.. И что же они там делают? – поинтересовалась девочка, неминуемо краснея.

— Как и положено, – Кот зевнул. – Случаются…

Льюис Кэрролл

Однажды юный физик Кеша, гуляя по лесу, заметил двух злобных лесных троллей, которые были заняты высокоинтеллектуальной деятельностью. Они раскручивали свои топоры по окружности так, чтобы они вращались с определенными частотами и, за счет стробоскопического эффекта, получали таким образом послания из космоса. Кеше не составило труда заметить, что топоры движутся по окружностям радиусов r ₁ и r ₂ с угловыми скоростями ω₁и ω₂ соответственно. Как настоящий физик, Кеша решил провести наблюдения и выяснить, чей топор преодолеет больший путь за время получения одного блока информации. Но на t_fail секунде наблюдений тролли заметили Кешу, и эксперимент прервался по техническим причинам. Так как Кеше сейчас не до расчета путей и он не сообщил нам время получения блока информации, мы просим вас просто выяснить, чей топор преодолел большее расстояние за время Кешиных наблюдений.