На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
Сторінок: 1
Здесь я предлагаю обсудить решение задачи Conflict
Если вы собрались написать сообщение в этой теме пожалуйста прочитайте следующие правила:
1. Постить только после окончания приёма решений. (без комментариев)
2. Постите код только если вас об этом попросили. (обилие кода делает тему нечитабельной)
3. Обсуждайте только задачу, которая указана в теме.
Надеюсь эти простые правила сделают обмен мнениями более плодотворным.
Відредаговано FireTiger (2007-01-04 20:36:06)
Поза форумом
Ідея базується на стандартному алгоритмі пошуку в ширину чи в глибину. Трохи змінити ці алгоритми і ми отримаємо рішення задачі Конфлікт
Поза форумом
Я просто просматриваю все конфликтные пары, и одного из полярников я помещаю в одну группу, а другого - в другую. Если окажется, что полярники из очередной конфликтной пары уже есть в одной группе, тогда их невозможно нормально разместить, и я вывожу 0. Если же я посмотрел все конфликтные пары, но не просмотрел всех полярников, тогда я одного непросмотренного полярника помещаю во вторую группу (если конфликтных пар не было и вторая группа вдруг окажется пустой) а всех остальных непросмотренных - в первую. Вот и все.
Поза форумом
Я теж просто робив цю задачу. Для кожного полярника записував з ким він конфліктує. Тепер в мене утворилася таблиця.
Лишається тільки вибрати: в яку групу i-того полярника відправити, а в яку його ворогів. Якщо це не можливо, то вивести 0.
Також потрібно передбачити коли немає конфліктних пар, то тоді потрібно одного з першої групи перевести в другу, щоб вона була не пуста.
Надіюсь цей спосіб праивльний
Поза форумом
guest1 написав:
Я просто просматриваю все конфликтные пары, и одного из полярников я помещаю в одну группу, а другого - в другую. Если окажется, что полярники из очередной конфликтной пары уже есть в одной группе, тогда их невозможно нормально разместить, и я вывожу 0. Если же я посмотрел все конфликтные пары, но не просмотрел всех полярников, тогда я одного непросмотренного полярника помещаю во вторую группу (если конфликтных пар не было и вторая группа вдруг окажется пустой) а всех остальных непросмотренных - в первую. Вот и все.
Пусть у тебя пары:
1 3
2 4
1 2
По твоему алгоритму:
1 - в первую группу, 3 - во вторую.
2 - в первую группу, 4 - во вторую.
1 2 - уже в одной группе, выводим 0.
Правильный ответ:
1
1 4
2 3
П.С. Извини если я не так понял твой алгоритм....
Поза форумом
именно - не понял. ну да ладно, я просто не полностью обьяснил.
если один полярник есть в первой группе, то запихиваем другого во вторую
(или если один полярник есть во второй группе, то запихиваем другого в первую)
Это у меня в коде предусмотрено. Мож показать?
Поза форумом
Идея такова: создать графы с пронумерованными вершинами и с ребрами между поссоренными парами.В любой вершине 1-го графа записать "1" ,в соседние "поссоренные" вершины записать -1. Просмотреть все -1, в соседние 1.Если в какую либо вершину надо поставить и 1, и -1, то вывести 0. Если успешно пройден весь цикл, то в 1-й группе все 1, во второй - все -1 (и нули - ни с кем не поссоренные полярники).
Наверное, напартачил шо-то в проге, а то 25 б дали . Могу дать код, если надо.
(хорошо, все обошлось - я 56 ... )
Поза форумом
JurasSic написав:
Могу дать код, если надо.
покажи код плз
Поза форумом
FireTiger написав:
guest1 написав:
Я просто просматриваю все конфликтные пары, и одного из полярников я помещаю в одну группу, а другого - в другую. Если окажется, что полярники из очередной конфликтной пары уже есть в одной группе, тогда их невозможно нормально разместить, и я вывожу 0. Если же я посмотрел все конфликтные пары, но не просмотрел всех полярников, тогда я одного непросмотренного полярника помещаю во вторую группу (если конфликтных пар не было и вторая группа вдруг окажется пустой) а всех остальных непросмотренных - в первую. Вот и все.
Пусть у тебя пары:
1 3
2 4
1 2
По твоему алгоритму:
1 - в первую группу, 3 - во вторую.
2 - в первую группу, 4 - во вторую.
1 2 - уже в одной группе, выводим 0.
Правильный ответ:
1
1 4
2 3
П.С. Извини если я не так понял твой алгоритм....
Спасибо, понял, исправил. Теперь на твоем тесте и на базовых выдает правильный результат.
П. С. К сожалению, послав переделанный код в онлайн, я набрал на три балла меньше чем в прошлый раз (три WA и остальные TL - итого 15 балов вместо 18)
буду думать что делать дальше... хотя в принципе я и так прохожу
Поза форумом
Пожалуйста, вот код. Напишите, пожалуйста,если найдете ошибку
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.
Поза форумом
Я сильно протупил. Мучился с указателями во избежание Segmentation Fault ( BadData ) , а maxpol=1000!
Поза форумом
Сторінок: 1