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


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

Ви не зайшли.

#1 2007-01-04 20:23:21

FireTiger
Новий користувач
Звідки: Донецк
Зареєстрований: 2006-09-27
Повідомлень: 86

Обсуждение решения задачи Conflict (только после 23:59 04.01.07)

Здесь я предлагаю обсудить решение задачи Conflict

Если вы собрались написать сообщение в этой теме пожалуйста прочитайте следующие правила:
1. Постить только после окончания приёма решений. (без комментариев)
2. Постите код только если вас об этом попросили. (обилие кода делает тему нечитабельной)
3. Обсуждайте только задачу, которая указана в теме.

Надеюсь эти простые правила сделают обмен мнениями более плодотворным.

Відредаговано FireTiger (2007-01-04 20:36:06)


ICQ 339203772  - Если что-нибудь срочно необходимо - стучитесь, я отвечу! smile
----------------
Основная проблема с программистами заключается в том, что вы никогда не можете сказать, чем они занимаются, до тех пор, пока не будет слишком поздно.

Поза форумом

 

#2 2007-01-05 08:33:25

Yevgeniy
Новий користувач
Зареєстрований: 2006-10-14
Повідомлень: 67

Re: Обсуждение решения задачи Conflict (только после 23:59 04.01.07)

Ідея базується на стандартному алгоритмі пошуку в ширину чи в глибину. Трохи змінити ці алгоритми і ми отримаємо рішення задачі Конфлікт


"Математика -- цариця наук, арифметика -- цариця математики."
      Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.

Поза форумом

 

#3 2007-01-05 09:30:00

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Обсуждение решения задачи Conflict (только после 23:59 04.01.07)

Я просто просматриваю все конфликтные пары, и одного из полярников я помещаю в одну группу, а другого - в другую. Если окажется, что полярники из очередной конфликтной пары уже есть в одной группе, тогда их невозможно нормально разместить, и я вывожу 0. Если же я посмотрел все конфликтные пары, но не просмотрел всех полярников, тогда я одного непросмотренного полярника помещаю во вторую группу (если конфликтных пар не было и вторая группа вдруг окажется пустой) а всех остальных непросмотренных - в первую. Вот и все. big_smile

Поза форумом

 

#4 2007-01-05 10:22:44

Taras
Олімпієць
Звідки: Хмельницька обл.
Зареєстрований: 2005-12-05
Повідомлень: 24

Re: Обсуждение решения задачи Conflict (только после 23:59 04.01.07)

Я теж просто робив цю задачу. Для кожного полярника записував з ким він конфліктує. Тепер в мене утворилася таблиця.
Лишається тільки вибрати: в яку групу i-того полярника відправити, а в яку його ворогів.  Якщо це не можливо, то вивести 0.
Також потрібно передбачити коли немає конфліктних пар, то тоді потрібно одного з першої групи перевести в другу, щоб вона була не пуста.
Надіюсь цей спосіб праивльний  smile


ExPerT - EXtrimal PERson Taras

Поза форумом

 

#5 2007-01-05 10:32:11

FireTiger
Новий користувач
Звідки: Донецк
Зареєстрований: 2006-09-27
Повідомлень: 86

Re: Обсуждение решения задачи Conflict (только после 23:59 04.01.07)

guest1 написав:

Я просто просматриваю все конфликтные пары, и одного из полярников я помещаю в одну группу, а другого - в другую. Если окажется, что полярники из очередной конфликтной пары уже есть в одной группе, тогда их невозможно нормально разместить, и я вывожу 0. Если же я посмотрел все конфликтные пары, но не просмотрел всех полярников, тогда я одного непросмотренного полярника помещаю во вторую группу (если конфликтных пар не было и вторая группа вдруг окажется пустой) а всех остальных непросмотренных - в первую. Вот и все. big_smile

Пусть у тебя пары:

1 3
2 4
1 2

По твоему алгоритму:

1 - в первую группу, 3 - во вторую.
2 - в первую группу, 4 - во вторую.
1 2 - уже в одной группе, выводим 0.

Правильный ответ:
1
1 4
2 3

П.С. Извини если я не так понял твой алгоритм....


ICQ 339203772  - Если что-нибудь срочно необходимо - стучитесь, я отвечу! smile
----------------
Основная проблема с программистами заключается в том, что вы никогда не можете сказать, чем они занимаются, до тех пор, пока не будет слишком поздно.

Поза форумом

 

#6 2007-01-05 11:23:08

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Обсуждение решения задачи Conflict (только после 23:59 04.01.07)

именно - не понял. ну да ладно, я просто не полностью обьяснил.
если один полярник есть в первой группе, то запихиваем другого во вторую
(или если один полярник есть во второй группе, то запихиваем другого в первую)
Это у меня в коде предусмотрено. Мож показать? big_smile

Поза форумом

 

#7 2007-01-05 11:27:02

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Обсуждение решения задачи Conflict (только после 23:59 04.01.07)

блииин... а ведь действительно не работает ... а я то думал sad smile sad smile

Поза форумом

 

#8 2007-01-05 20:17:49

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

Re: Обсуждение решения задачи Conflict (только после 23:59 04.01.07)

Идея такова: создать графы с пронумерованными вершинами и с ребрами между поссоренными парами.В любой вершине 1-го графа записать "1" ,в соседние "поссоренные" вершины записать -1. Просмотреть все -1, в соседние 1.Если в какую либо вершину надо поставить и 1, и -1, то вывести 0. Если успешно пройден весь цикл, то в 1-й группе все 1, во второй - все -1 (и нули - ни с кем не поссоренные полярники).
Наверное, напартачил шо-то в проге, а то 25 б дали hmm. Могу дать код, если надо.
(хорошо, все обошлось - я 56 ...  )big_smile

Поза форумом

 

#9 2007-01-06 19:27:10

xbit
Новий користувач
Зареєстрований: 2006-10-05
Повідомлень: 16

Re: Обсуждение решения задачи Conflict (только после 23:59 04.01.07)

JurasSic написав:

Могу дать код, если надо.

покажи код плз

Поза форумом

 

#10 2007-01-06 19:37:48

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Обсуждение решения задачи Conflict (только после 23:59 04.01.07)

FireTiger написав:

guest1 написав:

Я просто просматриваю все конфликтные пары, и одного из полярников я помещаю в одну группу, а другого - в другую. Если окажется, что полярники из очередной конфликтной пары уже есть в одной группе, тогда их невозможно нормально разместить, и я вывожу 0. Если же я посмотрел все конфликтные пары, но не просмотрел всех полярников, тогда я одного непросмотренного полярника помещаю во вторую группу (если конфликтных пар не было и вторая группа вдруг окажется пустой) а всех остальных непросмотренных - в первую. Вот и все. big_smile

Пусть у тебя пары:

1 3
2 4
1 2

По твоему алгоритму:

1 - в первую группу, 3 - во вторую.
2 - в первую группу, 4 - во вторую.
1 2 - уже в одной группе, выводим 0.

Правильный ответ:
1
1 4
2 3

П.С. Извини если я не так понял твой алгоритм....

Спасибо, понял, исправил. Теперь на твоем тесте и на базовых выдает правильный результат.
П. С. К сожалению, послав переделанный код в онлайн, я набрал на три балла меньше чем в прошлый раз sad (три WA и остальные TL - итого 15 балов вместо 18)
буду думать что делать дальше... хотя в принципе я и так прохожу big_smile

Поза форумом

 

#11 2007-01-08 16:31:43

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

Re: Обсуждение решения задачи Conflict (только после 23:59 04.01.07)

Пожалуйста, вот код. Напишите, пожалуйста,если найдете ошибку roll

Код:

program FERRYisBACK;
const maxpol=10000;
type pol=array[1..maxpol] of    record 
                                                                p:integer;
                                                                u:boolean;
                                                            end;    
         spnter=^sso;
         sso=record
                      x:integer;
                     p:spnter;
                 end;    
         ssor=array[1..maxpol] of spnter; 
         group=array[0..maxpol-1] of integer;

var pp:pol;
        ss:ssor;
        e,f:group;
        n:integer;

procedure rss(q:integer;var s:ssor);
var i,m,k,j:integer;
        a,prev:spnter;
begin
    read(m);
    for i:=1 to maxpol do
    s[i]:=nil;
    for k:=1 to m do
    begin 
        read(i,j);
        a:=s[i];
        prev:=nil;
        while a<>nil do 
        begin
            prev:=a;
            a:=a^.p;
        end;    
        new(a);
        a^.x:=j;
        if prev=nil then
        begin
        new(s[i]);
        s[i]^.p:=a;
        end
        else
        prev^.p:=a;
        a:=s[j];
        prev:=nil;
        while a<>nil do 
        begin
            prev:=a;
            a:=a^.p;
        end;    
        new(a);
        a^.x:=i;
        if prev=nil then
        begin
            new(s[j]);
            s[j]^.p:=a;
        end
        else    
        prev^.p:=a;
    end;    
end;

function findf(a,q:integer;p:pol):integer;
var i:integer;
begin
    i:=1;
    while ((p[i].u)or(p[i].p<>a))and(i<=q) do inc(i);
    if i=q+1 then
    begin
    i:=1;
    while (p[i].u)and(p[i].p<>0) do inc(i);
    end;
    findf:=i;
end;

function allus(q:integer;p:pol):boolean;
var i:integer;
begin
    i:=1;
    while p[i].u do inc(i);
    allus:=i>q;
end;

function is(i,j:integer;s:ssor):boolean;
var a:spnter;
begin
a:=s[i];
while (a<>nil) and (a^.x<>j) do
begin
    a:=a^.p;
end;    
is:=a<>nil;
end;

function polarn(s:ssor;q:integer;var p:pol):integer;
var i,l,last:integer;
begin
    p[1].p:=1;
    p[1].u:=true;
    for i:=2 to q do
        if is(1,i,s) then
            p[i].p:=-1;
    last:=1;
    while not allus(q,p) do
        begin
            l:=findf(0-last,q,p);
            if p[l].p=0 then p[l].p:=1;
            p[l].u:=true;
            for i:=1 to q do
                if is(i,l,s) then
                    if p[i].p<>p[l].p then
                    begin
                        p[i].p:=0-p[l].p
                    end
                    else
                    begin
                        polarn:=0;
                        exit;
                    end;
            last:=0-last;
        end;
    polarn:=1;
end;    

procedure grouping(a:pol;q:integer;var b,c:group);
var k,l,i:integer;
begin
k:=1;l:=1;
for i:=1 to q do
    if a[i].p=1 then
        begin
            b[k]:=i;
            inc(k);
        end
    else
        begin
            c[l]:=i;
            inc(l);
        end;
b[0]:=k-1;
c[0]:=l-1;
if b[0]=0 then 
begin
    b[0]:=1;
    b[1]:=c[c[0]];
    dec(c[0]);
end;    
if c[0]=0 then 
begin
    c[0]:=1;
    c[1]:=b[b[0]];
    dec(b[0]);
end;    
end;

procedure wrgr(b,c:group);
var i:integer;
begin
    for i:=1 to b[0] do
        write(b[i],' ');
    writeln;
    for i:=1 to c[0] do
        write(c[i],' ');
    writeln;
end;

begin
read(n);
rss(n,ss);
if polarn(ss,n,pp)=1 then
begin
    grouping(pp,n,e,f);
    writeln('1');
    wrgr(e,f);
end
else
writeln('0');
end.

smile

Поза форумом

 

#12 2007-01-09 07:39:29

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

Re: Обсуждение решения задачи Conflict (только после 23:59 04.01.07)

Я сильно протупил. Мучился с указателями во избежание Segmentation Fault ( BadData ) , а maxpol=1000!

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt