[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Решенија државен 2011  XML
Forum Index » Задачи од национални натпревари
Author Message
FREEZX



Joined: 16/02/2010 19:32:31
Messages: 33
Offline

Ајмо ставајте ваши решенија за задачите од државен. Еве ги моите:

Одземање:



Прегледување:


FREEZX



Joined: 16/02/2010 19:32:31
Messages: 33
Offline

Регистрација:
FREEZX



Joined: 16/02/2010 19:32:31
Messages: 33
Offline

Финкимен:
FREEZX



Joined: 16/02/2010 19:32:31
Messages: 33
Offline

Ајде камо open-source дух! Моиве решенија ги ставив на Wiki-то
bedzo



Joined: 18/01/2011 02:05:03
Messages: 234
Offline

Odzemanje:

This message was edited 2 times. Last update was at 05/04/2011 01:07:18

obi1kenobi



Joined: 18/02/2010 20:01:33
Messages: 168
Offline

Задача Прекин, државен 2011 напредна група - задача 3.

This message was edited 2 times. Last update was at 05/04/2011 20:06:06

bedzo



Joined: 18/01/2011 02:05:03
Messages: 234
Offline

FREEZX



Joined: 16/02/2010 19:32:31
Messages: 33
Offline

може објаснување за Прекин?

This message was edited 1 time. Last update was at 05/04/2011 22:47:34

bedzo



Joined: 18/01/2011 02:05:03
Messages: 234
Offline

frezeex koga ke imas vreme napisi objasnuvanje za finkimen.. Dupka sum u BFS & DFS..

This message was edited 1 time. Last update was at 06/04/2011 16:01:14

FREEZX



Joined: 16/02/2010 19:32:31
Messages: 33
Offline

ова е уствари дфс решение, со тоа што секогаш се означува поминатото поле со -1. Почнуваш од минимална висини и се движиш кон поголемите колку што можеш после пак бараш друго минимално поле па и од тоа почнуваш, и така на крајот све ќе поминеш и ќе изброиш колку пати така требало да се бара минимум. секое поминување на еден дфс проверуваш дали сите членови се -1. Ако се, прекинуваш и печатиш решение
obi1kenobi



Joined: 18/02/2010 20:01:33
Messages: 168
Offline

FREEZX wrote:може објаснување за Прекин?


Задачата ја решавам со алгоритам на Прим за наоѓање minimum spanning tree во граф. Тоа го прави функцијата span().

Откако ќе се утврди минималното дрво од кои рабови е составено, се разгледува графот без по еден од тие рабови - значи се одзема еден раб, се пушта Прим за да се најде второто минимално дрво и после работ се враќа и се одзема друг.

Прим има сложеност V log E, и во најлош случај се пушта E пати, така да сложеноста на ова решение е V * E * log E, што комотно поминува во дадените ограничувања.

Постои уште едно решение за 100 поени, со користење на Прим заедно со Union-Find структура и алгоритам, ама сметам дека тоа е доста потешко од ова...
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team