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.
I have answers to all your questions :) WA because... [3] // Задача 1169. Pairs 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 :)
shitty.Mishka But.... [2] // Задача 1169. Pairs 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?
I have answers to all your questions :) Re: But.... [1] // Задача 1169. Pairs 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)