|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
07.01.2024, 01:54 | #1 |
Новичок
Джуниор
Регистрация: 07.01.2024
Сообщений: 1
|
Препод сказал показать решение этой задачи до вторника, а я вообще даже не представляю как оно должно выглядеть...Помогите пожалуйста!!!
Каждой твари по паре
Коллекционировать животных можно не только на Ноевом ковчеге, но и на дереве. А дерево, как известно из теории графов, является связным ациклическим графом. Иными словами, дерево состоит из n вершин и n-1 ребра между ними. Каждое ребро соединяет некоторые две вершины дерева. Из любой вершины дерева можно добраться по ребрам до любой другой. Также дерево не содержит циклов, т. е. нельзя построить путь по ребрам из некоторой вершины и вернуться в нее, не пройдя по одному и тому же ребру дважды. Для расположения животных на нашем дереве сделано q гнезд, где q - четное число. Животным каждого вида предназначены два гнезда. После расселения по дереву каждая пара одного вида может перемещаться по ребрам дерева между своими гнездами. Они не должны мешать другим видам, т. е. чтобы никакие два пути не имели общего ребра. При этом допускается пересечение путей в вершине. Вам необходимо разместить q/2 видов животных по гнездам таким образом, чтобы пути животных одного вида удовлетворяли этому условию.(Желательно решать на Python/C++/PascalABC.NET/Java/C#/Rust) Формат входных данных В первой строке входных данных находится два целых числа n и q (2≤ n ≤ 2 • 10^5, 2≤n, q четно) — общее количество вершин в дереве и количество вершин, в которых расположены гнезда. Во второй строке входных данных находятся q различных целых чисел m(i) (1≤ m(i) ≤ n) - номера вершин с гнездами. В каждой из следующих n - 1 строк входных данных находится два целых u(i) и v(i) ( 1≤ v(i), v(i) ≤ n, u(i)≠v(i) ). Это означает, что между вершинами u(i) и v(i) в дереве проведено ребро. Гарантируется, что ребра во входных данных образуют дерево. Формат выходных данных Выходные данные должны содержать q/2 строк. В каждой строке должно содержаться два целых числа х(i) и у(i) (1 ≤ x(i), y(i)≤ n) - номера вершин, в которых будут располагаться гнезда i-го вида животных. Все числа в выходных данных должны быть различны и должны представлять собой номера вершин с гнёздами. Если разместить животных требуемым образом невозможно, выведите число -1. Критерии оценивания: Баллы начисляются за каждый тест в отдельности, но ряд тестов имеют специфическую структуру: 1. u(i) = i, v(i) = i+1 2. u(i) = 1, v(i) = i+1 3. n ≤ 3000, q≤6 4. q=n. 5. Нет дополнительных ограничений. Ввод: 9 6 1 3 2 5 8 6 3 1 3 2 3 4 3 5 3 6 4 7 7 8 1 9 Вывод: 3 2 8 5 1 6 Последний раз редактировалось mlgdanya; 07.01.2024 в 19:15. |
07.01.2024, 15:25 | #2 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,356
|
Если вообще ничего не представляете как делать по задаче, то лучше сразу создавайте тему во фрилансе с указанием языка программирования, сроков и вознаграждения.
При первом взгляде ничего лучше рекурсивного переборного алгоритма не приходит в голову. Начать перебирать все пути от первого гнезда до остальных. При выборе пути исключать ребра пути из дерева. Брать следующее оставшееся гнездо и перебирать пути из него. Если удалось выбрать пути между всеми гнездами, то печатать список. Если на текущем шаге не удалось найти путь ни в одно из гнезд, то возвращаться на шаг назад и выбирать другой путь для предыдущего гнезда. Но такой алгоритм для больших деревьев явно будет работать слишком долго.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
07.01.2024, 17:42 | #3 | |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,338
|
Можно пойти и таким путём:
1. Выбрать корневой узел. Поскольку через корневой узел можно перебираться на другие ветви, то претендентом на корневой узел будет узел, от которого идёт максимум ветвей. 2. Просматриваем каждую ветвь на предмет наличия гнёзд. 3. Если число гнёзд на ветви чётное, то соседние пары отдаём под особь. 4. Если число гнёзд нечётное, то дальние от корня соседние пары отдаём под особь, а ближайшее к корню связываем с гнездом на ветви, где гнёзд нечётное число. Проход между такими гнёздами - через корень. Как вариант, распределяем гнёзда по ветвям с числом гнёзд большим чем одно. Если число гнёзд нечётное, то оставляем свободными ближайшие к корню. На следующем шаге распределяем особи по свободным гнёздам, которые будут соединяться через корень. PS: Цитата:
PSS: И да, если решение будет найдено, то не плохо бы его тут оставить.
Как-то так, ...
|
|
07.01.2024, 18:15 | #4 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,356
|
Это подсказки, какие тесты сделать для проверки решения.
1. u(i) = i, v(i) = i+1 - все вершины дерева на одной "линии" (например, 1-2-3-4-5); 2. u(i) = 1, v(i) = i+1 - все вершины дерева кроме первой связаны с первой (дерево в виде "звезды"); 3. n ≤ 3000, q≤6 - много вершин, мало гнезд; 4. q=n - все вершины дерева являются гнездами.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
07.01.2024, 18:49 | #5 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,338
|
Спасибо.
Так понимаю что вершины - это узлы? У меня сложно с терминологией. Так знаю, что у графа может быть корень, узлы и рёбра. Слово "вершина" у меня ассоциируется с горами (тут живу).
Как-то так, ...
|
07.01.2024, 21:23 | #6 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,356
|
Да, узлы, вершины, точки - синонимы в данном случае.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
10.01.2024, 00:32 | #7 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,338
|
Это на Python (условия на язык нет).
Немного повозился в Сети и составил скрипт, который строит дерево с узлами, помеченными как гнездо и выбирает корневой узел. Код:
Код:
PS: Первичный код найден тут: https://stackoverflow.com/questions/...tree-in-python
Как-то так, ...
|
10.01.2024, 08:51 | #8 |
Форумчанин
Регистрация: 27.04.2022
Сообщений: 495
|
Уже среда, расходимся
стимулятор https://yoomoney.ru/to/41001303250491
|
10.01.2024, 15:21 | #9 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,356
|
Вот код для алгоритма из 2 сообщения:
Код:
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
10.01.2024, 15:51 | #10 |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,338
|
В своих рассуждениях полагал, что пересечения путей возможны только в корне. Но перечитал условие.
Пересечение путей может быть в любом узле. Но тогда сложно придумать дерево, на котором нельзя распределить пары животных. Если у двух пар есть общее ребро, то достаточно переставить гнёзда, которые соединены общим ребром. Спасибо, попробую разобраться в вашем коде. Авось что-то пригодится для студентов. PS: Ваше решение, в другой теме, с вложенными циклами и else, и командами break и continue буду использовать.
Как-то так, ...
|
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
По нажатию на кнопку Показать приложение должно открыть новое окно и показать в нем заказанные картинки с короткими подписями | Zerroz | JavaScript, Ajax | 0 | 26.04.2017 23:56 |
Помогите составить блоксхему, препод не принимает вообще | Spanchik | Помощь студентам | 1 | 23.12.2014 12:48 |
Проверьте пожалуйста код препод сказал, что не верен | mital25 | Помощь студентам | 18 | 16.11.2014 20:48 |
Помогите пожалуйста создать код для этой задачи на Delphi 7 | Viktor Makarov | Помощь студентам | 0 | 11.01.2014 09:26 |