Give me test data I had WA #1 as I printed loops. In other words, if my program had to output a path of length K it would print 1 1 1 2 2 2 2 3 ... (K - 1) (K - 1) (K - 1) K Having deleted them, I secured my AC :P I got AC with a somehow optimized backtracking that generated partitions for N. When I reached a partition with K critical edges -> solution. But with a value of K well chosen (maximum K for which we do not have all pairs critical) this approach should TLE. Test is N = 100, K = 4947 Your test was added. Finally AC, very nice problem! Replaced the backtracking with a recursive formula, used also the first two of the Viete relations. Edited by author 14.07.2011 19:33 Please add this test: 100 4950 On my computer my solution works 1.68sec, but I got AC with 1 sec. Test set contains this test. Your solution works 1 sec on it. Maybe your computer is slower than testing computer. the graph is simple!!! input: 2 0 output: -1 GOOD LUCK!!! [code deleted] Edited by moderator 28.07.2006 10:35 I have Fail (Validator) on Test#5 using CPP. Submit ID is 892128. What is the problem? I rewrote program in Pascal and got AC! I think validator should be fixed. Program is Here: Program Ural1169(Input,Output); Const MaxN=100; Type IntTypeNum1=Longint; IntTypeNum3=Shortint; SolutionType=array [1..MaxN] of IntTypeNum1; Var n,k,Total:IntTypeNum1; Found:Boolean; Sol:SolutionType; Procedure Init; begin readln(n,k); end; Procedure Search(Left,Need:IntTypeNum1); var l,Temp:IntTypeNum1; begin if Need=0 then begin Found:=True; Exit; end; if Left*(Left-1) div 2<Need then Exit; for l:=3 to Left do begin Temp:=l*(l-1) div 2; inc(Total); Sol[Total]:=l; if Need>=Temp then Search(Left-l,Need-Temp) else begin dec(Total); Break; end; if Found then Exit; dec(Total); end; end; Procedure Main; var i,L1,L2,Cur:IntTypeNum1; begin if (n=1) and (k=0) then Exit; if n=2 then begin if k=0 then writeln(-1); if k=1 then writeln(1,' ',2); Exit; end; Found:=False; Total:=0; Search(n,n*(n-1) div 2-k); if not Found then begin writeln(-1); Exit; end; Cur:=0; for i:=1 to Total do begin if i<>1 then writeln(1,' ',Cur+1); for L1:=Cur+1 to Cur+Sol[i] do for L2:=L1+1 to Cur+Sol[i] do writeln(L1,' ',L2); inc(Cur,Sol[i]); end; for L1:=Cur+1 to n do writeln(1,' ',L1); end; Begin Init; Main; End. And I got WA on Test 18! How 郁闷 I am!!!(Who can Translate the Chinese to English...) Please help me. Thanks. I got AC... So fast. I have a Stupid error!!! Add a Line before the Last Line of "Procedure Main" After the Sentence "for L1:=Cur+1 to n do" Insert a Sentence: "if L1<>1 then " Thus, the Program can Got AC!!! Who can explain me the problem ???????? My programme is: const nnn=100; var n,k,b,c,d,f:integer; a:array[1..nnn,0..(nnn-1)*nnn div 2] of shortint; e:array[1..100] of integer; begin readln(n,k); k:=n*(n-1) div 2-k; for b:=1 to n do e[b]:=(b-1)*b div 2; for b:=1 to n do begin for c:=0 to e[n] do a[b,c]:=-1; a[b,e[b]]:=0; end; for b:=1 to n do for c:=0 to e[b]-1 do for f:=b-1 downto 1 do begin d:=f; if c<e[b-d] then break; if a[d,c-e[b-d]]>=0 then begin a[b,c]:=d; break; end; end; if a[n,k]<0 then writeln(-1) else while n>0 do begin for b:=a[n,k]+1 to n-1 do writeln(b,' ',b+1); if a[n,k]+1<>n then writeln(n,' ',a[n,k]+1); if a[n,k]<>0 then writeln(a[n,k],' ',a[n,k]+1); b:=k; dec(k,e[n-a[n,k]]); n:=a[n,b]; end; end. I suppose you forgot that there are no cycles with 2 computers. try this input: 3 2 your output: 2 3 1 2 2 1 1 and 2 are connected twice, which is impossible. Hope this will help you. By the way, after you change your program, try such an input: 22 169 The answer is not -1 Good luck! I've got ac. Thank you for your help! I'm sorry but I think the answer for 22 169 is not -1. It is possible to construct such a graph. It's like this: 1-2-[3..6]-[7..14]-[15..22] ([a..b] means the clique of node a,a+1,...,b) Am I right? Or Is this graph wrong? And my program got AC. {This is my program} program p1169; const maxn=100; maxd=maxn*(maxn-1) div 2; var d,f:array [0..maxd] of longint; b:array [1..maxn] of longint; n,e,i,delta,j,k,p,tail,top:longint; begin read(n,e); e:=(n*(n-1) div 2)-e; for i:=0 to maxd do d[i]:=maxlongint; fillchar(f,sizeof(f),0); d[0]:=0; for i:=3 to maxn do begin delta:=i*(i-1) div 2; for j:=maxd downto 0 do if d[j]<>maxlongint then begin k:=j+delta; p:=d[j]+i; while k<=maxd do begin if p<d[k] then begin d[k]:=p; f[k]:=i; end; k:=k+delta; p:=p+i; end; end; end; if d[e]>n then begin writeln(-1); exit; end; tail:=0; i:=e; while i>0 do begin inc(tail); b[tail]:=f[i]; i:=i-(f[i]*(f[i]-1) div 2); end; top:=0; for i:=1 to tail do begin writeln(top+1,' ',top+b[i]); for j:=top+2 to top+b[i] do writeln(j-1,' ',j); top:=top+b[i]; end; for i:=top+1 to n do if i<>1 then writeln(i,' ',1); end. I have answers to all your questions :) -1 [2] // Problem 1169. Pairs 4 Mar 2002 00:15 > I think it has a solution like this 1 2 2 3 3 4 4 1 2 4 critical pair is 1 and 3, connection is 1 2 4 3 u r misunderstanding problem description :) "connection" means a direct connection between two computers If you have any difficulties,welcome to email to "hyz12345678@163.com".But in your first email,you should give a brief introduce of yourself. Program Network; Const Max=100; Mr=Max*Max Div 2; Var i,j,n,k,p,v,st:Longint; a,b:Array[0..Mr] Of Longint; Begin a[0]:=0; b[0]:=0; For i:=1 To Mr Do Begin a[i]:=Max+1; For j:=3 To Max Do Begin v:=i-j*(j-1) Div 2; If v>=0 Then If a[v]+j<=a[i] Then Begin a[i]:=a[v]+j; b[i]:=j; End; End; End; Readln(n,k); k:=n*(n-1) Div 2 - k; If a[k]>n Then Writeln(-1) Else Begin p:=1; v:=k; While v>0 Do Begin st:=p; If st<>1 Then Writeln('1 ',st); For i:=1 To b[v]-1 Do Begin Writeln(p,' ',p+1); Inc(p); End; Writeln(p,' ',st); Inc(p); Dec(v,b[v]*(b[v]-1) Div 2); End; While p<=n Do Begin If p<>1 Then Writeln('1 ',p); Inc(p); End; End; End. Here is my new program: Program Network; Const Max=100; Mr=Max*Max Div 2; Var i,j,n,k,p,v,st:Longint; a,b:Array[0..Mr] Of Longint; Begin a[0]:=0; b[0]:=0; For i:=1 To Mr Do Begin a[i]:=Max+1; For j:=3 To Max Do Begin v:=i-j*(j-1) Div 2; If v>=0 Then If a[v]+j<=a[i] Then Begin a[i]:=a[v]+j; b[i]:=j; End; End; End; Readln(n,k); k:=n*(n-1) Div 2 - k; If a[k]>n Then Writeln(-1) Else Begin p:=1; v:=k; While v>0 Do Begin st:=p; If st<>1 Then Writeln('1 ',st); For i:=1 To b[v]-1 Do Begin Writeln(p,' ',p+1); Inc(p); End; Writeln(p,' ',st); Inc(p); Dec(v,b[v]*(b[v]-1) Div 2); End; While p<=n Do Begin Writeln('1 ',p); Inc(p); End; End; End. Here is my program. Could anyone at least give me some test data so my program would give incorrect answers? Program Network; Const Max=100; Mr=Max*Max Div 2; Var i,j,n,k,p,v:Longint; a,b:Array[0..Mr] Of Longint; Begin a[0]:=0; b[0]:=0; For i:=1 To Mr Do Begin a[i]:=Max+1; For j:=3 To Max Do Begin v:=i-j*(j-1) Div 2; If v>=0 Then If a[v]+j<=a[i] Then Begin a[i]:=a[v]+j; b[i]:=j; End; End; End; Readln(n,k); k:=n*(n-1) Div 2 - k; If a[k]>n Then Writeln(-1) Else Begin p:=2; v:=k; While v>0 Do Begin Writeln('1 ',p); For i:=1 To b[v]-2 Do Begin Writeln(p,' ',p+1); Inc(p); End; Writeln(p,' 1'); Inc(p); Dec(v,b[v]*(b[v]-1) Div 2); End; While p<=n Do Begin Writeln('1 ',p); Inc(p); End; End; End. x*(x-1)/2 + y*(y-1)/2 <> (x+y)*(x+y-1)/2 => the cycle length x and the cycle length y should not share the vertex 1 :) But cycles give us non-critical pairs, then why can't different cycles share the same vertex? Can you give me an example so maybe I would understand? assume that ur program find out two cycles length x and length y such that x(x-1)/2+y*(y-1)/2 = k (the number of non-critical pair) and x+y <= n (the number of vertex)
If two cycles don't share any vertex , the number of non-critical pair is x(x-1)/2+y*(y-1)/2 (correct) But if two cycles share vertex 1 , the number of non-critical pair is (x+y-1)*(x+y-2)/2 (wrong) Is it possible for a pair of computers to be linked directly by more than one connection? e.g. for input 3 2 Is the following an acceptable output? 1 2 2 3 2 3 Or is the output -1 ? Thanks. The output IS -1. Sorry, just got 3 WAs because of this. > Is it possible for a pair of computers to be linked directly by more > than one connection? > > e.g. for input > 3 2 > > Is the following an acceptable output? > > 1 2 > 2 3 > 2 3 > > Or is the output -1 ? > > Thanks. |
|