М
Молодежь
К
Компьютеры-и-электроника
Д
Дом-и-сад
С
Стиль-и-уход-за-собой
П
Праздники-и-традиции
Т
Транспорт
П
Путешествия
С
Семейная-жизнь
Ф
Философия-и-религия
Б
Без категории
М
Мир-работы
Х
Хобби-и-рукоделие
И
Искусство-и-развлечения
В
Взаимоотношения
З
Здоровье
К
Кулинария-и-гостеприимство
Ф
Финансы-и-бизнес
П
Питомцы-и-животные
О
Образование
О
Образование-и-коммуникации
asellial
asellial
02.10.2020 20:48 •  Информатика

Минималистичная игра Вы играете в компьютерную игру. В этой игре есть n уровней. Изначально у вас открыт один уровень с номером 1. Для каждого уровня задан упорядоченный набор напрямую зависимых от него уровней. Уровень a называется косвенно зависимым от b, если либо a напрямую зависит от b, либо a косвенно зависит от одного из уровней, который напрямую зависит от b. Гарантируется, что каждый уровень косвенно зависим от первого, а также все уровни, кроме первого, зависимы напрямую от ровно одного другого уровня. Более формально, уровни представляют корневое дерево, с корнем - уровнем 1. При прохождении уровня i открывается первый уровень из набора напрямую зависимых от i уровней, после прохождения первого уровня и всех косвенно зависимых от него уровней открывается второй и так далее. Таким образом мы выполним все уровни. Более формально выполняется левый обход дерева, где самый левый сын - первый в списке. Для лучшего понимания посмотрите секцию с примечаниями.

У вас есть чит-код, который позволяет сделать не более k изменений. За одно изменение можно выбрать вершину, и поменять местами две соседних в наборе зависимых от нее вершин. Вам нужно сделать порядок посещения вершин минимально лексикографически возможным. Первый порядок лексикографически меньше второго, если для какого-то t (1 ≤ t ≤ n - 1) первые t уровней в порядках совпадают, а t + 1 уровень меньше в первом порядке.

Формат входных данных
В первой строке вводятся два целых числа n и k - количество уровней и ограничение на количество изменений (1 ≤ n ≤ 5 * 105, 0 ≤ k ≤ 1012).

В последующих n строках идет описание уровней. На i-й строке сначала вводится целое число ti (0 ≤ ti ≤ n - 1) - количество уровней напрямую зависимых от i-го, после чего вводится ti целых чисел - номера уровней напрямую зависимых от i-го.

Формат результата
Выведите n чисел - минимальный лексикографически возможный порядок после не более чем k изменений.

Примеры
Входные данные
5 1
2 3 2
2 5 4
0
0
0
Результат работы
1 2 5 4 3
Входные данные
5 2
2 3 2
2 5 4
0
0
0
Результат работы
1 2 4 5 3
Входные данные
5 4
4 5 3 2 4
0
0
0
0
Результат работы
1 2 3 4 5
Примечания
Система оценки:

Решения, работающие при n ≤ 10, будут набирать не менее 10% .

Решения, работающие, когда от каждого уровня напрямую зависит не более двух других уровней, будут набирать не менее 25% .

Решения, работающие при n ≤ 5000, будут получать не менее 30% .

Решения, работающие, когда все уровни напрямую зависимы от первого, будут получать не менее 35% .

Решения, работающие, когда от каждого уровня напрямую зависит не более десяти других уровней, будут набирать не менее 50% .

Решения, работающие при n ≤ 200000, будут получать не менее 65% .

Разбор примеров:
Зависимости уровней в первом и втором тесте из условия не отличаются, отличаются лишь значения k. Изначальный обход дерева выглядит следующим образом: 1 3 2 5 4.

Рисунок снизу соответствует одному изменению в первом примере

После этого изменения порядок посещения станет: 1 2 5 4 3.

Рисунок снизу соответствует второму изменения во втором примере

После этого изменения порядок посещения станет: 1 2 4 5 3. Можно показать, что порядок обхода лексикографичски меньше этого нельзя получить ни за какое количество действий.

👇
Открыть все ответы
Ответ:
topghalya228
topghalya228
02.10.2020
1) F=Av(¬A&B)
По закону дистрибутивности раскроем скобки
(Av¬A)&(AvB)
Av¬A = 1, значит остаётся AvB

2) F =A&(¬AvB)
По тому же закону раскрываем скобки
(A&¬A)v(A&B)
A&¬A = 0, значит остаётся A&B

3. (AvB)&(¬BvA)&(¬CvB)
По закону склеивания (AvB)&(¬BvA) = A , получается, что выражение принимает вид
A&(¬CvB)
Можно раскрыть скобки, получим
A&¬C v A&B

4) F =(1v(AvB))v((AC)&1) 
Скобка (1v(AvB)) = 1, так как 1 v ЧТОУГОДНО = 1
Получаем выражение
1v((AC)&1) = 1, так как 1 v ЧТОУГОДНО = 1
ответ 1
4,5(32 оценок)
Ответ:
vika2082
vika2082
02.10.2020
Program pr;
uses crt;

Var mas:array[1..1000, 1..1000] of integer;
N,M,i,j,k:integer;

Begin
Writeln('Введите размер матрицы N*M');
Write('N = ');
readln(N);
Write('M = ');
readln(M);

if (M>1000) or (N>1000) or (M<1) or (N<1)
then  
Writeln('Ошибка, указанные значения выходят за пределы матрицы')   else   
        Begin      
 Writeln('Введите элементы матрицы');      

k:=0; 
 for i:=1 to N do     
  for j:=1 to M do     
    Begin     
      readln(mas[i,j]);       
      if (mas[i,j] mod 2 = 0) then k:=k+1;     
    end; 
  
    Writeln();   
    Writeln('Исходная матрица');
   
   for i:=1 to N do   
     Begin     
       for j:=1 to M do     
          Begin     
             Write(mas[i,j], ' ')     
           end;     
      Writeln();   
     end;         

Writeln();   
Writeln('Количество четных элементов = ',k);      
 end;

readln;
end.
4,5(85 оценок)
Это интересно:
Новые ответы от MOGZ: Информатика
logo
Вход Регистрация
Что ты хочешь узнать?
Спроси Mozg
Открыть лучший ответ