ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1169. Pairs

Why WA? Could anyboy help me?
Послано sillyboy 23 дек 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...
Послано shitty.Mishka 23 дек 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!
Послано sillyboy 24 дек 2001 16:59
I've got ac.
Thank you for your help!
Re: For example...
Послано A New Start 5 май 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.