[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Задача Натпревар (тест натпревар март 2012)  XML
Forum Index » Задачи од национални натпревари
Author Message
mprelevic



Joined: 05/03/2011 00:07:30
Messages: 9
Offline

Можи малку помош околу решението на задачава?
Еве го кодот што го напишав:
filip_bujaroski


[Avatar]

Joined: 13/09/2010 21:58:57
Messages: 150
Location: Skopje
Offline

Zatoa shto ova e greedy i nema da raboti
eve ti primer na koj kje padne
6
10000000 10 10 10 1 1

Live to play, die for fun.
[Email] [MSN]
Vikjan94



Joined: 22/02/2011 20:11:00
Messages: 27
Offline

Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?
obi1kenobi



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

Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?


Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.
Vikjan94



Joined: 22/02/2011 20:11:00
Messages: 27
Offline

obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?


Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.


Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!
tStojkovski



Joined: 13/02/2010 14:23:00
Messages: 108
Location: Гостивар
Offline

Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?


Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.


Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.
[Email] [MSN]
Vikjan94



Joined: 22/02/2011 20:11:00
Messages: 27
Offline

tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?


Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.


Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.


Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???
tStojkovski



Joined: 13/02/2010 14:23:00
Messages: 108
Location: Гостивар
Offline

Vikjan94 wrote:
tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?


Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.


Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.


Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???

Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш
[Email] [MSN]
Vikjan94



Joined: 22/02/2011 20:11:00
Messages: 27
Offline

tStojkovski wrote:
Vikjan94 wrote:
tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?


Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.


Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.


Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???

Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш


Да, да, нема потреба од дополнително објаснување
Фала за идејата, немаше да ми текне вака да ја решам
filip_bujaroski


[Avatar]

Joined: 13/09/2010 21:58:57
Messages: 150
Location: Skopje
Offline

tStojkovski wrote:
Vikjan94 wrote:
tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?


Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.


Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.


Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???

Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш


A kako kje znaesh deka nema nekoj natprevaruvac da se povtori po nekolku pati vo dinamickoto?

Live to play, die for fun.
[Email] [MSN]
tStojkovski



Joined: 13/02/2010 14:23:00
Messages: 108
Location: Гостивар
Offline

filip_bujaroski wrote:
tStojkovski wrote:
Vikjan94 wrote:
tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?


Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.


Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.


Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???

Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш


A kako kje znaesh deka nema nekoj natprevaruvac da se povtori po nekolku pati vo dinamickoto?

Не мора цела задача на тацна
[Email] [MSN]
filip_bujaroski


[Avatar]

Joined: 13/09/2010 21:58:57
Messages: 150
Location: Skopje
Offline

tStojkovski wrote:
filip_bujaroski wrote:
tStojkovski wrote:
Vikjan94 wrote:
tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?


Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.


Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.


Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???

Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш


A kako kje znaesh deka nema nekoj natprevaruvac da se povtori po nekolku pati vo dinamickoto?

Не мора цела задача на тацна


Epa realno se drugo mi beshe jasno osven kako da znam deka ne sum go zemal 2 pati istiot natprevaruvac

Live to play, die for fun.
[Email] [MSN]
Vikjan94



Joined: 22/02/2011 20:11:00
Messages: 27
Offline

tStojkovski wrote:
filip_bujaroski wrote:
tStojkovski wrote:
Vikjan94 wrote:
tStojkovski wrote:
Vikjan94 wrote:
obi1kenobi wrote:
Vikjan94 wrote:Која е идејата за задачава?
Претпоставувам дека е нешто со динамичко, така?


Генерално, кога за алчно решение ќе најдеш контра-пример, вистинското решение е динамичко; значи да.


Да, да, баш по таа логика одев
Ама прашањето ми е, како да го изведам тоа? Немам некоја идеја!

Со динамичко запишуваш во bool низа секој можен збир што можеш да го добиеш со комбинација на сите натпреварувачи и кога ќе го сториш најблискиот можен збир до sum/2 ти е едната екипа а другата ти е разликата помеѓу првата екипа и сумата од натпреварувачите.


Мислиш, да ги изгенерирам сите можни комбинации со n/2 членови и да го пресметувам збирот на нивните јачини???

Вака, ќе направиш низа boolean T[N] каде што N ти е сума од јачините на сите n-натпреварувачи. Потоа за секој натпреварувач i за неговата вредност C[i] задаваш вредност T[C[i]]=true, и за секој елемент T[j]=true определуваш T[j+C[i]]=true. Мислам дека бев повеќе од јасен сега и дека ако има потреба од понатамошно разјаснување сам треба да разгледаш и да поекспериментираш


A kako kje znaesh deka nema nekoj natprevaruvac da se povtori po nekolku pati vo dinamickoto?

Не мора цела задача на тацна


Овој пристап ти помина на сите тест-примери???
Јас ја направив и така, функционира на 19/20. Реално, може да се води сметка да не се додава неколку пати истиот човек, ама не може да се води сметка колкава ќе биде разликата помеѓу бројот на луѓе во групите.
bedzo



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

Еве, направи матрица [N][10000] каде што N ти е бројот на земени луѓе, а другото ти е јачината.

Поточно матрица[2][30] ти означува дали со 2ца можеш да стигнеш до јачина 30.

Потоа само го гледаш редот N/2 и бараш кое решение е најблиско до средината...
filip_bujaroski


[Avatar]

Joined: 13/09/2010 21:58:57
Messages: 150
Location: Skopje
Offline

bedzo wrote:Еве, направи матрица [N][10000] каде што N ти е бројот на земени луѓе, а другото ти е јачината.

Поточно матрица[2][30] ти означува дали со 2ца можеш да стигнеш до јачина 30.

Потоа само го гледаш редот N/2 и бараш кое решение е најблиско до средината...


Mene za ovoj slucaj mi teknuva samo bruteforce knapsack... :/
Da baras do kade mozes da stignes, i od tamu da go dodavas noviot chlen, shto najverojatno kje bide so ogromna slozenost

Live to play, die for fun.
[Email] [MSN]
 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team