I see many people solved this with graph algorithms, there is also greedy approach. Let's build graph: u->v, if jedi u is winning v. You are doing n iterations, on every iteration you check, can current Jedi win, or not. There is greedy strategy to check this. You can eliminating enemies in order of the number of incoming edges. The fewer edges lead to a Jedi, the earlier we should eliminate him Edited by author 11.11.2021 22:35 Edited by author 11.11.2021 22:35 Edited by author 11.11.2021 22:36 Если вы используете DFS в итеративной форме, то вы можете получить TLE#4. Если вы перепишите DFS в рекурсивную форму и будете компилировать на Visual C++, то получите AC за менее чем 0.1 секунды. Алгоритм свой я оцениваю как O(N*N*N) по времени, Поскольку я N раз запускаю DFS по графу в котором O(N*N) ребер (В графе проведено ребро от джедая который может победить джедая X в схватке к джедаю Х) Короче,у нас проходит некий турнир.Правила таковы: мы выбираем любых двух джедаев из оставшихся ,они между собой сражаются,из них по условию ровно один побеждает,проигравший исчезает с турнира. И так далее: снова выбираем двух джедаев,один остается,и т.д. По условию либо Джедай А сильнее Джедая Б либо наоборот. Сильнее значит не менее чем по двум параметрам один джедай выигрывает у другого(т.е. соответствующие значения строго больше). Нам нужно найти всех возможных победителей,т.е. тех,кто останется последним. Мы можем как угодно формировать расписание турнира,т.е. выбирать кто с кем из оставшихся будет драться. Победитель может провести всего 1 бой,а может 2,а может 3,... .Расписание мы САМИ формируем!!! У кого нет идей,советую узнать про алгоритм Тарьяна и граф конденсации. Edited by author 31.08.2015 22:18 За N*logN решается, есличо)) 6 one 7 4 5 two 6 3 10 three 5 10 9 four 7 6 7 five 2 5 8 six 3 3 3 I think : one, two, three, four, five. Edited by author 18.03.2009 20:44 one two three four five test is incorrect, two and six have equal second parameter My solution is based on the concept of strong connectivity. I find connected components of the graph, then I print those jedis, that belong to the non-dominated component. It is npt very quick, but it works. I don't know, how BFS can help with this problem. Any explanation will be very much appreciated. (de bene esse: my e-mail is akhmed[at]astranet[dot]ru). for each start among knights mark all that can be reached from start thru winning if all are marked then print start's name To test your speed, you can use the following perl script to generate input: $n = 200; print "$n\n"; for(1..$n){ print "J$_"; print ' ', int(rand()*100000) for 1..3; print "\n" } O(N*log(N)) solution exists :) 3 q1 1 1 2 q2 1 2 1 q3 2 1 1 2 a1 1 1 1 a2 1 1 1 3 w1 6 6 6 w2 6 4 4 w3 5 5 5 great thanks! Edited by author 11.08.2010 04:41 Quote from statement: Is not possible a draw, because no Jedi any equal parameter may have. Therefore, incorrect all three your tests are. Maybe you give me tricky test? because I've got wa#4 ((( Сделайте нормальный человеческий перевод. Ну невозможно читать этот бред. "Are different the lightsaber, and Jedi different are" - вот как это понять, или " If looses a Jedi, must leave the tournament he." - лучше условие на русском сделайте, чем бредовое английское. Then, maybe, not Jedi English, but Yoda English =) #include<iostream> #include<string> #include<vector> using namespace std; struct node { string name; bool flag[205],temp[205]; vector<int> winto; int count ; long int x, y,z; bool canWinOver(struct node p) { int c=0; if( x > p.x ) c++; if( y > p.y ) c++; if( z > p.z ) c++; if( c > 1 ) return true; return false; } }; typedef struct node node; int main() { node jedi[205] ; int i , j , n , k , l; string s; long int p,q,r; cin >> n; for(i=1 ; i <= n ; i++ ) { cin >> s >> p >> q >> r; jedi[i].name=s; jedi[i].x=p; jedi[i].y=q; jedi[i].z=r; } for(i=1; i <= n ; i++) { for(j=i+1; j <= n ; j++) { if( jedi[i].canWinOver(jedi[j]) ) { jedi[i].flag[j]=true; jedi[i].winto.push_back(j); jedi[i].count++; } else { jedi[j].flag[i]=true; jedi[j].winto.push_back(i); jedi[j].count++; } } } for(i=1 ; i <= n ; i++ ) { for(j=1 ; j <= n ; j++ ) { if(i!=j && !(jedi[i].flag[j]) ) { for(k=0 ; k < jedi[i].count ; k++ ) { l = jedi[i].winto[k]; if(!(jedi[j].flag[l])) { jedi[j].winto.push_back(l); jedi[j].temp[l]=true; } } } } } for(i=1 ; i <= n ; i++ ) { int sum=0; for(j=1 ; j <= n ; j++ ) if( jedi[i].flag[j] || jedi[i].temp[j] ) sum++;
if(sum==n-1) cout << jedi[i].name << endl; } return 0; } PLS HELP I shocked! My program used 2 dfs(for find conecting components). Thats all. n<=200. Dfs work by O(n+m). Why I have TL??? Please help me, I really dont understand, where my mistakes. If you had TL#4 then increase your massivs. Because, if you use graf, then quantity of edges may 40000 What should we search? Components of strong connectivity or cycles? Please help me... If I search for components of strong connectivity that I receive WA#4. When I search for cycles I receive WA#5. What should I search? Please help me. Be careful!!! In the task said that "The parameters are ... not greater than 100000 by the ABSOLUTE value." So you need check not only if the letter, which in digit, is in ['0'..'9'], but '-' too. GOOD LUCK and have AC ) It's just your stupid checking input... :) All boys like to : 8_Ш3 <<<<<<<<< :) c3 I do not understand why at me the wrong answer 5. Somebody can help{assist} me? Here my code. Help{Assist} please, I cannot find my mistake{error}. Thanks beforehand!!! This Problem is not so hard, construct orientated graph that describes the situation and with DFS you can easily make it [code deleted] Edited by moderator 23.06.2006 17:14 I do not understand why at me the wrong answer 5. Somebody can help{assist} me? Here my code. Help{Assist} please, I cannot find my mistake{error}. Thanks beforehand!!! [code deleted] Edited by moderator 23.06.2006 17:14 Please, don't post your code. Just explain your algo... So it would be easier to help (assist =)) you. I do not understand why at me the wrong answer 5. Somebody can help{assist} me? Here my code. Help{Assist} please, I cannot find my mistake{error}. Thanks beforehand!!! [code deleted] Edited by moderator 23.06.2006 17:18 i use bfs too!!! i know no one will be patient to look over my code so i do not put it out or give me some texts!fu ck you very much~ Edited by author 14.11.2005 13:46 I suppose problem statement is not clear enought, because rules for pair composing weren't stated. For me, for instance, isn't obvious that one jedi of ,say, 500 can wait while others kill each other and then kill the last one, so he can take part only in one combat. I thought first time that it is smth like olympic system, I mean. program p1218; const mx = 500; var on,tw,th,good:array[1..mx] of longint; s:array[1..mx] of string; v:array[1..mx,1..mx] of boolean; n,k,i,j:integer; c:char; function win(i,j:integer):boolean; var res:integer; begin res := byte(on[i] > on[j]) + byte(tw[i] > tw[j]) + byte(th[i] > th[j]); if res > 1 then win := True else win := False; end; function fill(j:integer):boolean; var i:integer; b:boolean; begin b := True; for i:=1 to n do b := b and v[j,i]; if b then fill := True else fill := False; end; begin readln(n); for i:=1 to n do begin read(c); s[i]:=''; repeat s[i] := s[i] + c; read(c); until c = ' '; readln(on[i],tw[i],th[i]); end; for i:=1 to n do for j:=1 to n do v[i,j] := win(i,j); for k:=1 to n do for i:=1 to n do for j:=1 to n do if not v[i,j] then v[i,j] := v[i,k] and v[k,j]; for i:=1 to n do if fill(i) then writeln(s[i]); end. 'on' is a reserved keyword. here is my program. 1 i find a jedi which cannot be beaten by another jedi with the ekception of then some jedi which i already visited during DFS. 2 this jedi can be the winner and also jedi which can be reached from this vertex in both sides (can beat and be beaten) please mail your sugestions about this to p_s_@list.ru THANKS IN ADVANCE! VAR Name : ARRAY[1..510] OF String[32]; w1,w,good : ARRAY[1..510] OF integer; Stat : ARRAY[1..510, 0..2] OF LongInt; a:array[1..510,1..510] of integer; N,m,point,num, I, J, Sum,l,i1,k : LongInt; S : String; Ok : Boolean; PROCEDURE init; VAR J,i : LongInt; BEGIN fillchar(a,sizeof(a),0); fillchar(good,sizeof(good),0); for i:=1 to n do for j:=1 to n do if (i<>j)and (((Stat[I][0] > Stat[J][0]) AND (Stat[I][1] > Stat[J][1])) OR ((Stat[I][2] > Stat[J][2]) AND (Stat[I][1] > Stat[J][1])) OR ((Stat[I][0] > Stat[J][0]) AND (Stat[I][2] > Stat[J][2]))) THEN begin a[i,j]:=1; inc(good[i]); end; END; procedure find(i:integer); var j,max:integer; f:boolean; begin j:=1; for i:=2 to n do if good[j]<good[i] then j:=i; k:=j; end; procedure getting1; var j,i:integer; t:array[1..501] of integer; f:boolean; begin fillchar(t,sizeof(t),0); t[k]:=1; repeat f:=true; for i:=1 to n do if t[i]=1 then begin for j:=1 to n do if (a[i,j]=1)and(t[j]=0) then begin t[j]:=1; f:=false; end; end; if f then break; until false; for i:=1 to n do w[i]:=t[i]; end; procedure getting2; var j,i:integer; t:array[1..501] of integer; f:boolean; begin fillchar(t,sizeof(t),0); t[k]:=1; repeat f:=true; for i:=1 to n do if t[i]=1 then begin for j:=1 to n do if (a[j,i]=1)and(t[j]=0) then begin t[j]:=1; f:=false; end; end; if f then break; until false; for i:=1 to n do w1[i]:=t[i]; end; BEGIN ReadLn(N); FOR I := 1 TO N DO BEGIN ReadLn(S); S := S+' '; for j:=1 to length(s) do begin if (s[j]in['A'..'Z'])or(s[j] in ['a'..'z']) then begin insert(s[j],name[i],length(s)); k:=j; end; end; Delete(S, 1, k); WHILE (S[1] = ' ') DO Delete(S, 1, 1); Sum := 0; WHILE (S[1]<>' ') DO BEGIN Sum := Sum*10+Ord(S[1])-Ord('0'); Delete(S, 1, 1); END; WHILE (S[1] = ' ') DO Delete(S, 1, 1); Stat[I][0] := Sum; Sum := 0; WHILE (S[1]<>' ' ) DO BEGIN Sum := Sum*10+Ord(S[1])-Ord('0'); Delete(S, 1, 1); END; WHILE (S[1] = ' ') DO Delete(S, 1, 1); Stat[I][1] := Sum; Sum := 0; WHILE (S[1]<>' ' ) DO BEGIN Sum := Sum*10+Ord(S[1])-Ord('0'); Delete(S, 1, 1); END; Stat[I][2] := Sum; END; init; ok:=false; fillchar(w,sizeof(w),0); find(1); fillchar(w,sizeof(w),0); fillchar(w1,sizeof(w1),0); getting1; getting2; for i:=1 to n do begin if (w[i]=1)and(w1[i]=1) then writeln(name[i]); end; END. VAR Name, Win : ARRAY[1..510] OF String[32]; Flag, Killed : ARRAY[1..510] OF Byte; Stat : ARRAY[1..510, 0..2] OF LongInt; N, I, J, Sum : LongInt; S : String; Ok : Boolean; PROCEDURE Solve(I : LongInt); VAR J : LongInt; BEGIN IF Killed[I] = 1 THEN Exit; Killed[I] := 1; FOR J := 1 TO N DO IF (Killed[J] = 0) AND (I <> J) AND (((Stat[I][0] > Stat[J][0]) AND (Stat[I][1] > Stat[J][1])) OR ((Stat[I][2] > Stat[J][2]) AND (Stat[I][1] > Stat[J][1])) OR ((Stat[I][0] > Stat[J][0]) AND (Stat[I][2] > Stat[J][2]))) THEN BEGIN Solve(J); END; END; BEGIN ReadLn(N); FillChar(Flag, SizeOf(Flag), 0); FOR I := 1 TO N DO BEGIN ReadLn(S); S := S+' '; Name[I] := Copy(S, 1, Pos(' ', S)-1); Delete(S, 1, Pos(' ', S)); WHILE (S[1] = ' ') DO Delete(S, 1, 1); Sum := 0; WHILE (S[1] <> ' ') DO BEGIN Sum := Sum*10+Ord(S[1])-Ord('0'); Delete(S, 1, 1); END; WHILE (S[1] = ' ') DO Delete(S, 1, 1); Stat[I][0] := Sum; Sum := 0; WHILE (S[1] <> ' ') DO BEGIN Sum := Sum*10+Ord(S[1])-Ord('0'); Delete(S, 1, 1); END; WHILE (S[1] = ' ') DO Delete(S, 1, 1); Stat[I][1] := Sum; Sum := 0; WHILE (S[1] <> ' ') DO BEGIN Sum := Sum*10+Ord(S[1])-Ord('0'); Delete(S, 1, 1); END; Stat[I][2] := Sum; END; FOR I := 1 TO N DO BEGIN FillChar(Killed, SizeOf(Killed), 0); Solve(I); Ok := True; FOR J := 1 TO N DO IF Killed[J] = 0 THEN Ok := False; IF Ok THEN Flag[I] := 1; END; Sum := 0; FOR I := 1 TO N DO IF Flag[I] = 1 THEN BEGIN Inc(Sum); Win[Sum] := Name[I] END; FOR I := 1 TO Sum-1 DO WriteLn(Win[I]); Write(Win[Sum]); END. Why this WA, Plz Help! ---------------------------------------------------------------------- program a1218; const max=502; type xlist=integer; list=array[1..max]of xlist; atype=array[1..3]of list; gtype=array[1..max,1..max]of integer; ctype=array[1..max]of integer; var name:array[1..max]of string; a:atype; b:list; g:gtype; c:ctype; i,j,n,j1,k:integer; s:shortint; st1,st2:string; ti:boolean; procedure qsort(var a : ctype;lo,hi:integer); procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a[i]<x do inc(i); while x<a[j] do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); j:=j-1; end; until i>j; if l<j then sort(l,j); if i<r then sort(i,r); end; begin sort(lo,hi); end; function inarr(x:integer;var s:integer;t:integer):boolean; var i,s1,t1:integer; begin s1:=s;t1:=t;inarr:=false; for i:=s1 to t1 do if c[i]=x then begin s:=i; inarr:=true; exit; end; end; procedure printf(s,t:integer); var i:integer; begin qsort(c,s,t); for i:=s to t do writeln(name[c[i]]); end; procedure findcyc(x,dep:integer); begin for i:=1 to b[x] do begin j:=1; if inarr(g[x,i],j,dep) then begin printf(j,dep); halt; end else begin inc(dep); c[dep]:=g[x,i]; findcyc(g[x,i],dep); c[dep]:=0; dec(dep); end; end; end; begin fillchar(a,sizeof(a),0); readln(n); for i:=1 to n do begin readln(st1); st2:=''; for j:=1 to length(st1) do if st1[j]<>' ' then st2:=st2+st1[j] else break; name[i]:=st2; j1:=j;k:=0; for j:=j1 to length(st1) do if st1[j]=' ' then inc(k) else a [k][i]:=a[k][i]*10+ord(st1[j])-48; end; fillchar(b,sizeof(b),0); for i:=1 to n do for j:=1 to n do begin s:=0; for k:=1 to 3 do if a[k][j]>a[k][i] then s:=s+1; if s>=2 then begin inc(b[i]); g[i,b[i]]:=j; end; end; ti:=true; for i:=1 to n do if b[i]=0 then begin writeln(name[i]); ti:=false; end; if ti then begin c[1]:=1; findcyc(1,1); end; end. |
|