helpmepleasehelp1
08.04.2022 18:47

ПРОГРАММИРОВАНИЕ решить задачу на 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

Нажмите на рекламу ниже и сразу увидите ответ
Популярные вопросы:
Ответ:
alisherpitbul
09.05.2023 22:42

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

Ну, например, по заданию 1 могут быть варианты:

1. Написать программу, которая , при этом в каждом поединке победа присуждается с вероятностью 1/3, поражение с вероятностью 1/2, ничья с вероятностью 1/6. По окончании расчетов вывести турнирную таблицу в порядке занятого места.

 

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

 

2. Написать программу, которая, при этом участники каждого турнира выводятся на экран, а пользователь сам определяет его результат(победа, ничья, поражение). По окончании турниров программа віводит турнирную таблицу в порядке занятого места.

 

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

 

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

 

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

Успехов!

 

0,0(0 оценок)
Ответ:
Anonimka04
13.09.2021 21:33
Чисто по определениям (без примеров):
1) Платное - ты платишь за возможность использования полного функционала программы единажды.
Бесплатное - полный функционал программы распространяется бесплатно
Условно-беспланое - программное обеспечение, распространяемое бесплатно, но имеющее платные "модули"
2) Системное - все программы и компоненты, поставляемые вместе с операционной системы, загружаемые с загрузочного диска независимо от желания пользователя.
Прикладное - все программное обеспечение, установленное пользователем.
0,0(0 оценок)
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota Оформи подписку
logo
Начни делиться знаниями
Вход Регистрация
Что ты хочешь узнать?
Спроси ai-бота