jun_1.txt

1. Дат је скуп који садржи N природних бројева. Нађи највећи подскуп такав да за било који пар елемената A и B из тог подскупа или A дели B или B дели A.

Улаз:
У првом реду стандардног улаза дат је цео број N
(1≤N≤2000). У другој линији дато је N чланова скупа (све вредности су између 1 и 109).
Излаз:
На стандарни излаз исписати један цео број који представља број чланова жељеног скупа.
Примери
Улаз:
5
9 36 17 108 3
Излаз:	
4
Појашњење:
Решење са 4 елемента је (9,36,108,3).

Улаз:
9
18 20 6 200 4 36 108 40 2
Излаз:
5
Појашњење:
Решење са 5 елемената је (20,200,4,40,2).

2. Вероватно да ово нисте знали, али у нашој галаксији има N настањених планета. Између неких планета постојеустаљени међупланетарни летови. Са сваке планете могуће је доћи до било које друге и ако постоји лет од планете A до планете B, постоји и повратни лет и он кошта C динара. Велики трошкови одржавања међупланетарних линија довели су до тога да је галактички одбор за транспорт одлучио да укине све летове који неће реметити повезаност свих планета, али тако да се трошкови одржавања свих преосталих летова сведу на минимум.

Улаз:
У првој линији стандардног улаза налазе се два цела броја N
и М. (број планета у галаксији 1≤N≤5000 и број међупланетарних летова N−1≤M≤100000). У следећих M редова налазе се по три броја А, B и C одвојени размаком. А и B су бројеви планета које су повезане, а C је цена одржавања међупланетарне линије између планета А и B. (1≤А,B,C≤5000)

Излаз:
У прву линију стандардног излаза испишиte један цео број који представља цену одржавања преосталих летова након укидања оних неповољних.
Временска сложеност алгоритма: O(MlogM)
Меморијска сложеност: O(MlogN).

Пример:
Улаз:
5 10
2 3 2
2 1 3
3 5 3
3 4 16
2 4 10
5 1 15
4 5 2
2 5 19
1 3 9
4 1 10
Излаз:
10

3. Римљани опет нападају Гале. У галском селу постоји N стубова око којих се могу градити заштитне зидине и М кућа. Заштитне зидине се граде тако што се подижу између стубова. Дакле, између свака 2 стуба можемо изградити део зида. Помозите Галима да утврде да ли могу да изграде заштитне зидине око стубова и да заштите све куће у селу. 

У првој линији стандардног улаза се уносе бројеви N и М.
У наредних N линија се уносе по 2 броја која представљају позиције стубова. Након тога се у наредних М линија уносе позиције кућа у селу.

У јединој линији стандардног излаза исписати NE ако је немогуће оградити све куће заштитном оградом која се формира око стубова, а DА иначе.

Сложеност алгоритма треба да буде О(𝑁log𝑁).
Вредности координата по апсолутној вредности неће прелазити 500.

Вредности природних бројева N и М неће прелазити 1000.
Напомена: Не морају сви стубови бити искоришћени.

Пример 1:
Улаз:
5 4
0 3
6 4
2 5
3 0
0 0
2 1
2 2
1 1
3 3
Излаз:
DA

Пример 2:
Улаз:
4 5
0 3
2 5
3 0
0 0
2 2
2 1
1 1
3 3
6 4
Излаз:
NE