Олимпиадная информатика

Задача «Давайте жить дружно»

2 секунды и 64 Мб памяти

Жители IТ-города - обычные люди, они дружат или враждуют между собой. Отношение дружбы и вражды в этом городе обладает свойством взаимности, то есть если А - друг (или враг) В, то В - друг (или враг) А.

Среди жителей города встречаются не только друзья, но и враждующие между собой. За один день только один из жителей может начать новую жизнь: перессориться со всеми своими друзьями и подружиться со всеми своими врагами. Если же у него нет ни одного друга (врага), то, начав новую жизнь, он может подружиться (поссориться) со всеми остальными жителями города.

Вам нужно вычислить наименьшее количество дней, за которое все жители города могут подружиться, а также составить список жителей, которым для этого нужно начать новую жизнь.

Формат входного файла input.txt

Первая строка содержит одно целое число N (3 <N <1000) - количество жителей города. В каждой i-ой из последующих N строк записаны: число Di, (0 <=Di, < N) - количество друзей i-го жителя, а затем, через пробел, D, различных целых чисел, не превосходящих N, - номера его друзей. (Все жители пронумерованы целыми числами от 1 до N.) Остальные жители враждуют с ним.

Формат выходного файла output.txt

Выведите число -1, если всех жителей города подружить невозможно. Иначе в первой строке запишите одно число - наименьшее количество дней, за которое все жители могут подружиться. Во второй строке - последовательность разделенных пробелом целых чисел - номеров жителей, которым для этого нужно начать новую жизнь. Если возможных решений несколько, выведите любое из них.

program aa;
var
  a: array[0..1002] of longint;
  max,s,d,imax,x,t,j,i,n:longint;
  z: array[0..1001, 0..1001] of byte;

begin
  assign(input, 'input.txt');reset(input);
  assign(output, 'output.txt');rewrite(output);
  read(n);
  max := 0;
  imax := 1;
  s:=0;
  for j := 1 to n do
  begin
    read(a[j]);
    if a[j] > max then
    begin
      max := a[j];
      imax := j;
    end;
    s:=s+a[j];
    for i := 1 to a[j] do
    begin
      read(x);
      z[j, x] := 1;
    end;
  end;
  s:=s div 2;
  
        d:=4*s+n+n-n*n;
        if (d<0)or(trunc(sqrt(d))*trunc(sqrt(d))<d) then
         begin
          write(-1);
          halt(0);
        end;
  writeln(n - 1 - max);
  for i := 1 to imax-1 do
    if z[imax, i] = 0 then write(i, ' ');
    for i := n downto imax+1 do
    if z[imax, i] = 0 then write(i, ' ');
  close(input);close(output);
end.





close
 

Разбор задачи №6 "Давайте жить дружно"

Расскажу, как я решал эту задачу. Сразу заметил, что если найдётся тройка жителей, в которой все враги, то они никогда не подружатся. Действительно, начав новую жизнь, один из них подружится с 2. Второй начиная новую жизнь, с первым поругается.

Получается всегда число дружественных связей в такой тройке чётное - 0 или 2. Отсюда такой алгоритм, проверяем все тройки, если нашлась с чётным числом дружественных связей - сообщаем, что всеобщее примирение невозможно и останавливаемся. Наверное, в противном случае положительный исход возможен. (Но строго доказать это не могу.) Тогда находим жителя с наибольшим числом друзей и заставляем его недругов с ним помириться, начав новую жизнь - тут-то и наступает всеобщее счастье. Тут как раз выложили тесты. Проверил - ура! - ни одного вердикта неверный ответ, но - увы - всего 31 балл - превышение времени на многих тестах.

Тогда решил подойти с другого конца взять за начальное положение то, когда каждый дружат с каждым и идти в обратную сторону - можно ли получить данное в задаче положение. Причём необязательно знать, как это достигается - мы уже имеем это делать: ищем самого дружелюбного и т.д. Сначала Дружеских связей (когда все дружат) N*(N-1)/2 =(N*N- N )/2. Начав новую жизнь 1 порывает N-1 связь и всего их остаётся (N*N- N )/2 - (N-1)= (N*N- 3*N+2)/2. Теперь у оставшихся по (N-2) и на следующем шаге будем иметь (N*N- 3*N+2)/2 - (N-2)+1= (N*N- 5*N+8)/2. Прибавляем 1, так как этот житель, начав новую жизнь. Восстановит дружеские отношения с первым. Для следующего будет (N*N- 5*N+8)/2 - (N-3)+2= (N*N- 5*N+18)/2 и т.д.

По индукции можно доказать, что на К-ом шаге число дружественных связей равно (N* - (2*К+1)*N+2*К*К)/2. Если кто-то начнет жить по-новому во второй раз - число связей возвращается к предыдущему значению. Значение N нам известно, количество дружеских связей S можно подсчитать параллельно с вводом данных. Остаётся решить квадратное уравнение (N* - (2*К+1)*N+2*К*К)/2 = S относительно переменной К. Если оно имеет натуральный корень, то подружить можно, в противном случае - нельзя.

Само уравнение решать ненужно, достаточно проверить, является ли его дискриминант точным квадратом. Исправляю код, проверяю - прекрасно, всё прошло 100 баллов. Конечно, этот код можно оптимизировать на пример не искать самого дружелюбного, вычислить и использовать значение К и т.п.