ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1169. Pairs

Why WA? Could anyboy help me?
Posted by sillyboy 23 Dec 2001 15:21
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.
For example...
Posted by shitty.Mishka 23 Dec 2001 16:14
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!
Thanks!
Posted by sillyboy 24 Dec 2001 16:59
I've got ac.
Thank you for your help!
Re: For example...
Posted by A New Start 5 May 2003 11:39
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.