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

Задача « 38 Попугаев »

Попугаи пронумерованы различными целыми числами от 1 до п. Каждый из них сумел выдрать одно перо из чьего-то хвоста, и у каждого попугая было выдрано ровно одно перо. Для наведения порядка удав может проглотить несколько попугаев, а остальных рассадить поровну в две клетки так, чтобы ни один попугай не попал в одну клетку со своим обидчиком. Необходимо подсчитать наименьшее количество попугаев, которое должен проглотить удав, и выяснить, на какие две клетки рассадить остальных попугаев так, чтобы ни один попугай не оказался в одной клетке со своим обидчиком. Формат входного файла input.txt В первой строке записано единственное целое число п - количество попугаев (2 < п < 105). Следующая строка содержит п различных целых чисел от 1 до п, i-oe число в ней означает номер попугая, у которого выдрал перо попугай с номером i. Формат выходного файла output.txt Первая строка должна содержать одно число - наименьшее количество попугаев, которое нужно проглотить удаву для наведения порядка. В следующих двух строках записаны номера попугаев, которые должны находиться в первой и второй клетках соответственно. Количество попугаев в клетках должно быть одинаковым. Если решений несколько, выведите любое из них.

INPUT.TXT

2
2 1

OUTPUT.TXT

0
1
2

INPUT.TXT

2
3 1

OUTPUT.TXT

2

посмотреть решение здесь

предложено Песковым Аркадием Геннадьевичем, МОУ «Сюкеевская средняя общеобразовательная школа»
Камско-Устьинского муниципального района РТ

var p,z,i,j,n,m,t,k:longint;
a,b:array[0..100003]of longint;
begin
 assign(input,'input.txt');
reset(input);
 assign(output,'output.txt');
rewrite(output);
 read(n);
 for i:=1 to n do
 read(a[i]);
 k:=1;
 for i:=1 to n do
 begin
  if a[i]>0 then
  begin
   m:=i;z:=0;
   while a[m]<>0 do
   begin
   inc(z);
    b[m]:=k;
    k:=3-k;
    t:=m;
    m:=a[m];
    a[t]:=0;
   end;
   if  odd(z) then begin inc(p);k:=1;b[t]:=0;end;
  end;
 end;
 writeln(p);
 for i:=1 to n do
 if b[i]=1 then write(i,' ');
 writeln;
 for i:=1 to n do
 if b[i]=2 then write(i,' ');
end.

close

Разбор задачи №1 "Угадайка"

Упорядочим попугаев по такому правилу. Взяв первым произвольного попугая, поставим за ним его обидчика, за ним - его обидчика и т.д. пока обидчиком не станет первый выбранный попугай.

Если упорядочено чётное количество попугаев, то объединив в одну группу попугаев с четными, а в другую с нечётными номерами, получим требуемое разбиение на 2 группы.

Если же упорядоченных попугаев нечетное число, то у последнего попугая обидчик и обиженный окажутся в разных группах, и он не может войти ни в одну из них.

Значит, его придётся включить в третью группу - проглоченных удавом. После этого некоторые из попугаев могут остаться неупорядоченными.

Продолжим упорядочивание по тому же принципу, взяв за следующего любого из оставшихся попугаев. Повторяем до тех пор, пока есть неупорядоченные попугаи. Ясно, что съедено будет столько попугаев, сколько циклов с нечётным количеством попугаев мы получим в процессе упорядочивания.

Выведем в первой строке количество съеденных попугаев , во второй - с номерами из первой группы, в третьей - из второй.

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

Разбор и решение задач муниципального уровня

Задача « 38 Попугаев »

Разбор задачи №1 "Угадайка"

Содержание