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

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

Показать все сообщения Спрятать все сообщения

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 дек 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 дек 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 дек 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)