Messages posted by: obi1kenobi

mile wrote:Дечки, многу е просто! Кој го создал проблемот - треба да си го реши! Упатете ги забелешките директно таму.

Значи, се реагира и кај ЗИМ и кај СММ за решавање на овој проблем со конструктивен разговор. Мислам дека ако сите заземаме hardline позиции нема да се реши и и едната и другата екипа на Македонија ќе настрадаат како резултат.

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

Така да Миле се надевам дека ќе можеме да најдеме конструктивно решение за да можеме уредно да учествуваме на натпреварите и да биде одбрана најдобрата можна екипа затоа што во ничиј интерес не би било Македонија како држава да се срами со слаби резултати на светските натпревари.

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

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

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

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

Постои уште едно решение за 100 поени, со користење на Прим заедно со Union-Find структура и алгоритам, ама сметам дека тоа е доста потешко од ова...

Не би било добро и ако олимпијадата се закаже во првите 10 дена од мај, затоа што тогаш е Балканската Математичка Олимпијада.

http://www.smm.org.mk/index.php?view=article&catid=1:latest-news&id=208:2011-04-06-09-09-20&format=pdf

Поради прогласувањето на 9ти април за работен ден, Македонската Математичка Олимпијада е преместена на 16ти април и е во конфликт со Македонската Олимпијада по Информатика. 17ти април е втората рунда од CodeFu. Дали ќе има можност да се интервенира и во договор со Сојузот на Математичари на Македонија, да се помести или едната или другата олимпијада за некој датум што одговара за сите?

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

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<cmath>
#include<ctime>
#include<fstream>
#include<string>
#include<cstring>
#include<climits>

using namespace std;

#define sz(x) (int)((x).size())
#define all(c) (c).begin(),(c).end()
#define DBGM(x,y) if(DEBUG) cout << #x << ' ' << #y << ": " << x << ' ' << y << '\n'
#define MSI(x,y) memset((x),(y),sizeof(x));

#define DEBUG true;

class dijk
{
    public:
    int nd,cost,orig;
};

bool operator<(dijk a,dijk b)
{
    if(a.cost==b.cost) return a.nd>b.nd;
    return a.cost>b.cost;
}

list<int> bgn,en;
int res;
int remnr;
int n,m;
int taken;

list<int> cnn[101];
list<int> cost[101];
bool vis[101],add;
priority_queue<dijk> * que;

void proc(dijk in)
{
    if(vis[in.nd]) return;

dijk tmp;
    list<int>::iterator it,it2;

if(add)
    {
        bgn.push_back(in.orig);
        en.push_back(in.nd);
    }

vis[in.nd]=true;
    taken++;
    res+=in.cost;
    it=cnn[in.nd].begin();
    it2=cost[in.nd].begin();

while(it!=cnn[in.nd].end())
    {
        if(!vis[*it])
        {
            tmp.nd=*it;
            tmp.cost=*it2;
            tmp.orig=in.nd;
            que->push(tmp);
        }
        it++;
        it2++;
    }

}

int span()
{
    MSI(vis,0);
    res=0;
    taken=0;
    dijk tmp;
    tmp.nd=0;
    tmp.cost=0;
    tmp.orig=-1;

que->push(tmp);

while(taken<n && !que->empty())
    {
        tmp=que->top();
        que->pop();

proc(tmp);
    }
    if(taken<n)
    {
        return INT_MAX;
    }
    return res;
}

int main()
{
    int a,b,c,i,j,ares,bres=INT_MAX;
    que=new priority_queue<dijk>;
    add=true;

scanf("%d %d",&n,&m);

for(i=0;i<m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        a--;
        b--;
        cnn[a].push_back(b);
        cost[a].push_back(c);
        cnn[b].push_back(a);
        cost[b].push_back(c);
    }

ares=span();
    add=false;

list<int>::iterator ita,itb,itan,itbn,itc,itcn,itd,itdn;

while(bgn.begin()!=bgn.end())
    {
        if(*bgn.begin()==-1 || *en.begin()==-1)
        {
            bgn.pop_front();
            en.pop_front();
            continue;
        }

ita=cnn[*bgn.begin()].begin();
        itb=cost[*bgn.begin()].begin();
        itc=cnn[*en.begin()].begin();
        itd=cost[*en.begin()].begin();
        while(*ita!=*en.begin())
        {
            ita++;
            itb++;
        }
        itan=ita;
        itan++;
        cnn[*bgn.begin()].erase(ita);
        remnr=*itb;
        itbn=itb;
        itbn++;
        cost[*bgn.begin()].erase(itb);

while(*itc!=*bgn.begin())
        {
            itc++;
            itd++;
        }
        itcn=itc;
        itcn++;
        itdn=itd;
        itdn++;
        cnn[*en.begin()].erase(itc);
        cost[*en.begin()].erase(itd);

delete que;
        que=new priority_queue<dijk>;

bres=min(bres,span());

ita=itan;
        itb=itbn;
        itc=itcn;
        itd=itdn;
        cnn[*bgn.begin()].push_back(*en.begin());
        cnn[*en.begin()].push_back(*bgn.begin());
        cost[*bgn.begin()].push_back(remnr);
        cost[*en.begin()].push_back(remnr);
        bgn.pop_front();
        en.pop_front();
    }
    printf("%d %d\n",min(ares,bres),max(ares,bres));
   
    return 0;
}

Има шанси доделувањето на наградите да се помести или порано или подоцна? Затоа што има CodeFu од пладне до 2

MindCalamity wrote:

obi1kenobi wrote:

dbojadzievski wrote:Gi imam site ovie,plus i Borland C++.Prvo,Visual Studio nema vrska so C++.Nivniot dijalekt e sosema razlichen od kodificiraniot C++.Vtoro,kodot shto taka se generira e losh,spor i zavisen od .NET platformata,shto znachi deka nema mnogu cross-platformiranje i backwards-kompatibilnost.
A od ovie ponudenive razvojni okolini,rechisi site go koristat MinGW kompajlerot taka da se gore-dolu isti.Kako IDE najdobro e Code::Blocks,zatoa shto e najaktivno.Imeno timot na Dev-Cpp se otkazha pred podolgo vreme,a eden od koderite raboti sega na Code::Blocks.A i ne mozhete da ja nadminete poddrshkata za plug-ins

FYI, Visual C++ и .Net се две сосема различни работи, единствено што ги поврзува е што и двете можат да се пишуваат во Visual Studio. C#, Visual Basic, F#, IronPython и IronRuby зависат од .Net, додека Visual C++ зависи само од Visual C++ Runtime библиотеките кои не се дел од .Net. Ако си инсталирал игра, сигурно си видел дека се инсталира фајл со име vcredist - тоа се библиотеките на C++. .Net доаѓа во dotnetfx и слични фајлови.

Точно.

dbojadzievski wrote:Prvo,Visual Studio nema vrska so C++.Nivniot dijalek...

Ахх кога се правиш паметен правиш многу грешки, нели ? Дијалект ? Се вика синтакса (syntax) колку што сум информиран, инаку од пред неколку години постои Mono што овозможува дел .NET framework-от да биде "cross-platform" и "backwards-compatible", спротивно од тоа ти што го кажа

Mono го прави .NET cross-platform, а backward-compatible е по дефиниција затоа што .NET 4.0 е само суперсет на сите претходни верзии после .NET 2.0, нешто слично како што C++ е суперсет на C.

Мислам дека не вели дека цистерната треба да се врати назад во А, само дека треба да стигне во Б. Пробај така

Браво бе Бујо, ај сега врати се назад и види го датумот од кога е последниот пост пред твојот

Мислам дека повеќе не мора да се биде логиран за да се влезе на форумот.

Како може без JIT да е бавен а со JIT да е unusable, кога JIT може само да го забрза? Ти дечко си ми анти-Микрософт настроен, не ќе да е до јазикот

Python дефинитивно е јазик што треба да се знае, нема подобар кога ти треба нешто набрзина да искуцаш. Микрософт работи на имплементација на Python која ќе работи на CLR и ќе се компајлира преку JIT така да би требало да биде доста побрза од vanilla варијантите.

dbojadzievski wrote:Gi imam site ovie,plus i Borland C++.Prvo,Visual Studio nema vrska so C++.Nivniot dijalekt e sosema razlichen od kodificiraniot C++.Vtoro,kodot shto taka se generira e losh,spor i zavisen od .NET platformata,shto znachi deka nema mnogu cross-platformiranje i backwards-kompatibilnost.
A od ovie ponudenive razvojni okolini,rechisi site go koristat MinGW kompajlerot taka da se gore-dolu isti.Kako IDE najdobro e Code::Blocks,zatoa shto e najaktivno.Imeno timot na Dev-Cpp se otkazha pred podolgo vreme,a eden od koderite raboti sega na Code::Blocks.A i ne mozhete da ja nadminete poddrshkata za plug-ins

FYI, Visual C++ и .Net се две сосема различни работи, единствено што ги поврзува е што и двете можат да се пишуваат во Visual Studio. C#, Visual Basic, F#, IronPython и IronRuby зависат од .Net, додека Visual C++ зависи само од Visual C++ Runtime библиотеките кои не се дел од .Net. Ако си инсталирал игра, сигурно си видел дека се инсталира фајл со име vcredist - тоа се библиотеките на C++. .Net доаѓа во dotnetfx и слични фајлови.

Како може графот да биде ориентиран кога можеш од која било соба да одиш во која било соба со уклучено светло, без разлика дали си го чепкал светлото таму или не? Објаснувањето на Филип е ок.

tStojkovski wrote:Ја реши некој целосна освен Предраг? Дајте помош, ми излегува точен резултат само кога во крајната соба се наоѓа прекинувачот за соба 1

Закачи го кодот или прати ми го по ПП па можеби ќе можам да ти помогнам