ПРОГРАММИРОВАНИЕ решить задачу на C++/Python
G. Браконьеры
ограничение по времени на тест: 1.5 секунд
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Алиса и Боб — два браконьера, которые рубят лес.
Лес это набор (возможно пустой) деревьев. Дерево — это связный граф без циклов. Подвешенное дерево имеет специальную вершину — корень. Родителем вершины v называется следующая вершина на кратчайшем пути от v до корня. Детьми вершины v называются вершины, для которых v является родителем. Вершина называется листом, если у неё нет детей.
В этой задаче мы определим глубину вершины как количество вершин на простом пути от этой вершины до корня. Рангом дерева назовем минимальную глубину его листа.
Изначально дан непустой лес подвешенных деревьев. Алиса и Боб играют в игру на этом лесе. Они ходят по очереди, Алиса ходит первой. В начале каждого хода игрок выбирает дерево из леса. Далее игрок выбирает положительное целое число — глубину разреза, которая не превосходит ранга выбранного дерева. Затем игрок удаляет из дерева все вершины, чьи глубины меньше либо равны глубине разреза. Все остальные вершины разбиваются на набор подвешенных деревьев, корнем каждого становится вершина, имевшая наименьшую глубину в дереве до разреза. Все эти деревья добавляются в лес и игра продолжается.
Игрок проигрывает, если на момент начала его хода лес пуст.
Определите, может ли Алиса победить, если оба игрока играют оптимально.
Входные данные
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число t (1≤t≤5⋅105) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка набора входных данных содержит одно целое число n (1≤n≤5⋅105) — суммарное количество вершин в деревьях изначального леса.
Вторая строка содержит n целых чисел p1,p2,…,pn (0≤pi≤n) — описание леса. Если pi=0, то i-я вершина дерева является корнем, иначе pi является родителем вершины i. Гарантируется, что p задает корректный лес подвешенных деревьев.
Гарантируется, что сумма значений n по всем наборам входных данных не превосходит 5⋅105.
Выходные данные
Для каждого набора входных данных выведите «YES» (без кавычек), если Алиса может победить, иначе выведите «NO» (без кавычек). Вы можете выводить каждую букву в любом регистре.
Пример
входные данные
4
4
0 1 0 3
7
0 1 2 0 4 5 6
4
0 1 1 2
7
0 1 1 2 2 3 3
выходные данные
NO
YES
NO
YES
Структура программы в Pascal
Итак, на предыдущей странице мы определились со следующими понятиями: program, integer, real, const, var, begin, end, write, writeln, read, readln. Давайте напишем программы на Паскале с их использованием. Но сначала выясним, из каких частей состоит программа на Паскале.
Любая программа на языке программирования Pascal имеет три составляющие: 1) заголовок; 2) раздел описаний; 3) тело программы.
✎ 1) Заголовок – это слово Program , после которого идет название программы латиницей и точка с запятой в конце. Название не может начинаться с цифры, не должно совпадать с зарезервированными словами (begin, end, integer и т.п.) или с названиями переменных из раздела описаний (см. ниже), а также недопустимо использование каких бы то ни было символов (‘@’, ‘%’, ‘&’ и т.п.), кроме подчеркивания. Название желательно давать со смыслом, которое отображало бы суть самой программы. Но заголовок писать не обязательно.
✎ 2) Раздел описаний – Поскольку сначала мы будем рассматривать задачи, то у нас во втором разделе будет находиться или описание констант, или переменных (см. пп. 4 и 5 статьи Введение в Pascal).
✎ 3) Тело программы – блок операторов, в котором записываются команды для выполнения. Начинается этот блок словом begin («начало»), а заканчивается словом end. («конец») с точкой в конце(пп. 6, 7 той же статьи).
Таким образом, в общем случае программа на Паскале выглядит следующим образом:
Код Pascal
1
2
3
4
5
6
7
8
9
10
Program <название программы>;
<раздел описаний>
begin
<оператор 1>;
<оператор 2>;
. . . . . . .
<оператор N>;
end.
При решении задач ограничимся сначала целыми числами. Перед тем как начать программировать, укажем действия над числами в Паскале: «+» − сложение, «-» − вычитание, «*» − умножение, «/» − деление. Как видим, в программировании и математике элементарные действия над числами обозначаются одинаково. Решим следующую задачу:
Объяснение:
//PascalABC.NET
uses GraphABC;
var c: integer;
begin
window.IsFixedSize := true;//запрет изменения размера экрана
window.Clear(cllightblue);//очистка экрана синим цветом
pen.Color := clred;//меняем цвет пера на красный
for var i := 0 to 19 do//цикл для отрисовки линий
begin
c := (window.Height div 19) * i;//сдвиг линнии по y
line(0, 0 + c, window.Width, window.Height - c);//рисуем линию
end;
end.
Объяснение:
uses graphabc;
begin
circle(50,50,50);
circle(50,50,20);
circle(150,50,50);
circle(150,50,20);
circle(250,50,50);
circle(250,50,20);
circle(350,50,50);
circle(350,50,20);
circle(450,50,50);
circle(450,50,20);
circle(550,50,50);
circle(550,50,20);
end.