Show all threads Hide all threads Show all messages Hide all messages | WA #1 | Zamytin | 1169. Pairs | 21 Aug 2018 14:49 | 2 | WA #1 Zamytin 13 Feb 2017 23:11 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 | wa18,can someone give some test data? | ateow | 1169. Pairs | 23 Jul 2013 21:07 | 1 | | weak tests | morbidel | 1169. Pairs | 14 Jul 2011 15:34 | 3 | 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 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 | Admins, please add this test | Orfest (Novosibirsk SU) | 1169. Pairs | 4 Jan 2011 22:46 | 2 | 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. | WA#2 | hoan | 1169. Pairs | 18 Dec 2010 21:39 | 1 | WA#2 hoan 18 Dec 2010 21:39 the graph is simple!!! input: 2 0 output: -1 GOOD LUCK!!! | Why WA 2? | starrich | 1169. Pairs | 27 Jul 2006 21:36 | 1 | [code deleted] Edited by moderator 28.07.2006 10:35 | Fail (Validator) | UNKNOWN_LAMER | 1169. Pairs | 10 Aug 2005 01:57 | 3 | 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. | I need help very much... | 198808xc | 1169. Pairs | 6 Jul 2005 08:47 | 2 | 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!!! | DP could got AC... | Yu Yuanming | 1169. Pairs | 16 Jun 2005 14:31 | 3 | | HHEELLPP !!! Who can explain me the problem ???????? | GodZilla | 1169. Pairs | 28 Jul 2003 00:41 | 1 | Who can explain me the problem ???????? | Why WA? Could anyboy help me? | sillyboy | 1169. Pairs | 5 May 2003 11:39 | 4 | 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. | Why I have got Wrong Answer? Could someone give me some tests? | Koala | 1169. Pairs | 2 Mar 2003 17:01 | 1 | {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. | Can you give some test to me? | Tony | 1169. Pairs | 11 Oct 2002 16:19 | 1 | | what is output if n = 4 and k = 1 | raxtinhac | 1169. Pairs | 4 Mar 2002 16:37 | 4 | -1 I have answers to all your questions :) 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 | What should I output if N=1 and K=0 | hajime | 1169. Pairs | 19 Dec 2001 12:56 | 2 | 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. | To xyz: I'm sorry to disturb you, but can you please tell me what's now wrong with my program | shitty.Mishka | 1169. Pairs | 19 Dec 2001 04:20 | 2 | 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. | To xyz: I'm sorry to disturb you, but can you please tell me what's now wrong with my program | shitty.Mishka | 1169. Pairs | 19 Dec 2001 04:14 | 1 | 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. | Please help me with this problem. I think my solution is so obvisous, I can't understand how can I get WA? Can anybody have a look at my program please? | shitty.Mishka | 1169. Pairs | 19 Dec 2001 03:58 | 5 | 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. WA because... I have answers to all your questions :) 18 Dec 2001 23:21 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.... shitty.Mishka 19 Dec 2001 00:04 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? Re: But.... I have answers to all your questions :) 19 Dec 2001 00:39 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) | Need a clarification for Pairs (1169) | Christopher Moh | 1169. Pairs | 18 Dec 2001 00:13 | 2 | 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. |
|
|