А
Size: a a a
2020 May 05
DE
дфс - метод поиска на графе, сама задача вот:
Однажды n детей в школе решили поиграть в игру. Каждый ребенок записала на своем листочке свой порядковый номер (начиная с 1), затем каждый записал свое любимое число. Если i-й ребенок ходит, то она может заменить свой листочек на листочек j-го ребенка если | i - j | = Di, где di - любимое число i-го ребенка. «Игроки» ходят в любом порядке. Количество ходов не ограничено.
Вам дано перестановку чисел от 1 до n и любимые числа детей. Ваша задача ответить: может игра зайти в такое состояние.
Тесты:
7
4 3 5 1 2 7 6
4 6 6 1 6 6 1
ответ нет
7
4 2 5 1 3 7 6
4 6 6 1 6 6 1
ответ да
Однажды n детей в школе решили поиграть в игру. Каждый ребенок записала на своем листочке свой порядковый номер (начиная с 1), затем каждый записал свое любимое число. Если i-й ребенок ходит, то она может заменить свой листочек на листочек j-го ребенка если | i - j | = Di, где di - любимое число i-го ребенка. «Игроки» ходят в любом порядке. Количество ходов не ограничено.
Вам дано перестановку чисел от 1 до n и любимые числа детей. Ваша задача ответить: может игра зайти в такое состояние.
Тесты:
7
4 3 5 1 2 7 6
4 6 6 1 6 6 1
ответ нет
7
4 2 5 1 3 7 6
4 6 6 1 6 6 1
ответ да
Что значит "вам дано перестановку чисел"?
Что такое ДФС ты не ответил?
Что такое ДФС ты не ответил?
А
Что значит "вам дано перестановку чисел"?
Что такое ДФС ты не ответил?
Что такое ДФС ты не ответил?
ВЛ
Что значит "вам дано перестановку чисел"?
Что такое ДФС ты не ответил?
Что такое ДФС ты не ответил?
вроде вначале написал, но вот: Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно.
ВЛ
перестановка дана во второй строке, начальные позиции от 1 до n
DE
перестановка дана во второй строке, начальные позиции от 1 до n
Перестановка — это как?
А
перестановка дана во второй строке, начальные позиции от 1 до n
мне даже интересно поймут ли тебя)
DE
7 — ?
4 3 5 1 2 7 6 — нач позиции
4 6 6 1 6 6 1 — ?
4 3 5 1 2 7 6 — нач позиции
4 6 6 1 6 6 1 — ?
ВЛ
Перестановка — это как?
первый пример:
начальная перестановка это числа от 1 до 5, т.е.
1 2 3 4 5
потом во второй строке дана итоговая перестановка
5 4 3 2 1
в третьей даны любимые числа, с помощью них мы можем менять местами элементы
начальная перестановка это числа от 1 до 5, т.е.
1 2 3 4 5
потом во второй строке дана итоговая перестановка
5 4 3 2 1
в третьей даны любимые числа, с помощью них мы можем менять местами элементы
ВЛ
из 1 2 3 4 5 нужно получить 5 4 3 2 1
DE
Понял
DE
Меняться может в любую сторону и это никак не обозначено?
ВЛ
только когда модуль разности чисел - любимое число первого
DE
Любимые числа идут в таком же порядке что и 1234567?
ВЛ
да, по порядку
DE
1 4
2 6
3 6
4 1
5 6
6 6
7 1
То есть первоначально было так?
2 6
3 6
4 1
5 6
6 6
7 1
То есть первоначально было так?