0 / 0 / 0
Регистрация: 27.10.2018
Сообщений: 30
1

Определить кто победит на заданном графе, если каждый из ребят играет оптимально

04.10.2020, 15:25. Показов 494. Ответов 3

Author24 — интернет-сервис помощи студентам
Сегодня у Даши День Рождения! В честь такого праздника Денис подарил ей новую игру на ориентированном ациклическом графе. Правила игры очень простые. Изначально в вершине 1 есть фишка; двое игроков по очереди передвигают фишку по одному ребру графа за ход. Каждый игрок может за игру сделать не более одного «суперхода». «Суперходом» называется перемещение фишки последовательно на не более чем k рёбер (но хотя бы по одному ребру нужно пройти). Проигрывает тот, кто не может сделать ход.
Денис и Даша решили сыграть в эту игру. Первой ходит Даша (потому что девочкам надо уступать). Скажите, кто победит на заданном графе, если каждый из ребят играет оптимально.
Формат ввода

В первой строке даны три целых числа n, m и k (1 ≤ n ≤ 105, 0 ≤ m ≤ 106, 1 ≤ k ≤ n) — количество вершин, рёбер и максимальная длина «суперхода» соответственно.
В следующих m строках находится по два целых числа v и u (1 ≤ v, u ≤ n), обозначающие наличие ориентированного ребра из v в u в графе. Гарантируется, что граф ацикличный.
Формат вывода

В единственной строке выведите «Dasha», если победит Даша и «Denis», если победит Денис.
Пример 1

Ввод Вывод
5 5 1
1 2
2 3
2 4
4 3
4 5
Denis
Пример 2

Ввод Вывод
7 8 2
1 2
2 3
3 4
2 5
3 6
4 6
5 6
6 7
Dasha
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.10.2020, 15:25
Ответы с готовыми решениями:

Определить кто из кандидатов в президенты победит на выборах
Определить кто из кандидатов в президенты победит на выборах,если приняли участие в выборах 50%...

Кто из учеников играет, а кто не играет в шахматы
3. Кто из учеников А, В, С и D играет, а кто не играет в шахматы, если известно следующее: 1) если...

Пирсон или армия: кто победит?
Помогите пожалуйста решить,решается судьба. Правила, 5.16, 5.18. Задания набирать ручками. Один...

Определить степень каждой вершины в графе, заданном матрицей инцидентности
Приветствую! :) Такая вот задача:"Определите степень каждой вершины в графе, заданном матрицей...

3
Параллельный Кот
1905 / 827 / 350
Регистрация: 25.03.2016
Сообщений: 2,045
04.10.2020, 15:32 2

Не по теме:

скоро сказка сказывается, да не скоро дело делается


Такое впечатление, что филологов начали "учить" программированию. Даже грустно стало...
0
Annemesski
05.10.2020, 17:37
  #3

Не по теме:


valen10, все куда хуже, по ходу филологи начали учить программированию.

0
из племени тумба-юбма
2467 / 1790 / 417
Регистрация: 29.11.2015
Сообщений: 8,690
Записей в блоге: 15
05.10.2020, 17:45 4
эм.... без наглядного мануала не могу понять игру
0
05.10.2020, 17:45
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.10.2020, 17:45
Помогаю со студенческими работами здесь

Определить смежные вершины к вершине Е в графе, заданном матрицей смежности
Определить смежные вершины к вершине Е в графе, заданном матрицей смежности: ***** A B C D E A 0...

В заданном графе необходимо определить, существует ли цикл, проходящий по каждому ребру графа ровно 1 раз
В заданном графе необходимо определить, существует ли цикл, проходящий по каждому ребру графа ровно...

Кто играет в покер?
Кто-нибудь играет?) Я вконтакте порой поигрываю))))

Кто играет в Last Chaos?
Кто играет в Last Chaos???

Кто играет в Доту?
я начал играть в доту нужно пати

Кто играет в Fallout 3?
кто то играет в Fallout 3 ? или нет?


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru