Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2007-10-23 17:17:54

Luzer
Новий користувач
Зареєстрований: 2007-10-23
Повідомлень: 1

Решаем задачки!

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

Народ помогите решить задачу! плз!
Меня не интересует код, я хочу знать идею или способ решения, правильного решения!
Большое спасибо! Жду...

условие задачи:
По заданному двоичному дереву найдите способ
распилить некоторые  его ребра так, чтобы каждая из его частей
имела не более k вершин, а общее количество частей не превышало
(2*n/k). В первой строке n - количество вершин и k. Следующие n-1
строк  описывают ребра дерева. Каждое описывается двумя номерами
вершин: номером родителя и номером ребенка. Корень дерева 1.
Вывести количество ребер, которые следует перепилить и эти ребра.
Пример
ввод: 5 2
     1 2
     1 5
     5 3
     5 4

Ввывод: 2
       2 4


БОЛЬШОЕ СПАСИБО

Поза форумом

 

#2 2007-10-23 19:45:50

reiten
журі
Звідки: Киев
Зареєстрований: 2005-10-16
Повідомлень: 196

Re: Решаем задачки!

Первое, что приходит в голову - сделать динамику по дереву.

Количество частей в результате разреза дерева равняется числу разрезанных ребер + 1. То есть достаточно построить такой разрез, который минимизирует количество разрываемых ребер, и мы получим ответ к задаче.
Введем функцию f(v,sz), где v-вершина дерева, sz - количество вершин, которые в этом поддереве можно оставить соединенными с v.
тогда все зависит от того, сколько потомков у вершины v:
0. v-лист. Ничего разрезать точно не надо. f(v,sz)=0
1. у v есть 1 потомок. Значит можно либо разрезать ребро к потомку, либо не разрезать. f(v,sz)=min(f(chld[v],sz-1),f(chld[v],k)+1)
2 тут выходит 4 разных варианта.
- удалить оба ребра к детям. если сделать так, то в сумме в поддереве будет сделано f(left[v],k)+f(right[v],k)+2 разрезов.
- удалить только ребро к левому сыну. Тогда будет f(left[v],k)+f(right[v],sz-1)+1
- удалить только ребро к правому сыну. Тогда будет f(right[v],k)+f(left[v],sz-1)+1
- не удалять не одного из ребер. ответом для этого случая будет min(f(left[v],i)+f(right[v],sz-1-i)) по i от 1 до sz-2.
f(v,sz) будет равняться минимуму из этих 4 вариантов.

А имея посчитанную функцию f, восстановить удаленные ребра - это уже дело техники.


"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар

Поза форумом

 

#3 2007-10-26 19:21:00

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Решаем задачки!

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

Відредаговано necro (2007-10-26 19:21:30)


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#4 2007-10-28 19:05:26

reiten
журі
Звідки: Киев
Зареєстрований: 2005-10-16
Повідомлень: 196

Re: Решаем задачки!

Про жадность - согласен. Это первое, что приходит в голову. Но очевидной и при этом правильной жадности я тут не вижу.
А динамика - железный способ.


"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар

Поза форумом

 

#5 2007-10-29 12:23:26

LineOfLife
Новий користувач
Зареєстрований: 2007-10-21
Повідомлень: 1

Re: Решаем задачки!

Подскажите пожалуйста! Учасниками олимпиады могут стать только школьники? Заранее спасибо

Поза форумом

 

#6 2007-10-29 18:38:59

MAXXX
Новий користувач
Звідки: м. Київ
Зареєстрований: 2006-10-17
Повідомлень: 132

Re: Решаем задачки!

Ні. Не школярі реєструються у категорії НЕ ШКОЛЯРІ


ICQ 426287475

Поза форумом

 

#7 2007-10-30 08:12:55

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Решаем задачки!

Решил не создавать еще одну тему не по тематике форума

Вопрос к всем - Кто какие знает архивы задач с проверяющей системой и возможностью просматривать тесты.
Раньше был оч хороший проект ТТБ но уже мертвы не только конкурсы но и архив....(сегодня в надежде опять проверил)


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&img=5

Поза форумом

 

#8 2007-11-01 16:16:43

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Решаем задачки!

Усцака


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#9 2007-11-01 20:41:02

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Решаем задачки!

necro написав:

Усцака

не совсем понял, ето выражение эмоций или инет-проект с заданными характеристиками?)))


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&img=5

Поза форумом

 

#10 2007-11-01 21:12:03

Skiminok
Новий користувач
Звідки: Киев, Украина
Зареєстрований: 2006-01-19
Повідомлень: 144
Вебсайт

Re: Решаем задачки!

Dark_Dimius написав:

necro написав:

Усцака

не совсем понял, ето выражение эмоций или инет-проект с заданными характеристиками?)))

Насколько я понимаю, имелся в виду Usaco :-)


Если вы с первого раза сумели написать программу, в которой транслятор не обнаружил ни одной ошибки, сообщите об этом системному программисту. Он исправит ошибки в трансляторе.
http://wwp.icq.com/scripts/online.dll?icq=282667777&img=5ICQ 282667777

Поза форумом

 

#11 2007-11-01 21:29:07

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: Решаем задачки!

Skiminok написав:

Dark_Dimius написав:

necro написав:

Усцака

не совсем понял, ето выражение эмоций или инет-проект с заданными характеристиками?)))

Насколько я понимаю, имелся в виду Usaco :-)

+1 ттырррррррррррррр.....тыш в яболчко... wink


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt