0 / 0 / 1
Регистрация: 29.04.2013
Сообщений: 13
|
|
1 | |
Задача с кубиками23.05.2013, 23:35. Показов 17234. Ответов 23
Метки нет (Все метки)
Ребята, помогите решить задачку на зачет.
Родители подарили Пети набор детских кубиков. Поскольку Петя пойдет в школу, они купили ему кубики с буквами. На каждой из шести граней каждого кубика написана буква. Теперь Петя хочет похвастаться перед старшей сестрой, что умеет читать. Для этого он хочет составить из кубиков ее имя. Но это оказалось довольно сложно сделать - ведь разные буквы могут находиться на одном и том же кубике, и тогда Петя не сможет использовать обе буквы в слове. Правда, одна и та же буква может встречаться на разных кубиках. Дан набор кубиков и имя сестры. Выясните, можно выложить ее имя с помощью этих кубиков, и если да, то в каком порядке следует выложить кубики. Ввод: В первой строке входного файла находится число N (1 <N <100) - количество кубиков в наборе у Пети. Во второй строке записано имя Петиной сестры - слово, состоящее только из заглавных латинских букв, не более 100 символов. Следующие N строк содержат по 6 букв (только большие латинские буквы), которые написаны на соответствующем кубике. Вывод: В первой строке выходного файла выведите YES, если выложить имя Петина сестры данным кубиками можно, и N0 - в противном случае. Если ответ YES, то во второй строке выведите М различных чисел из диапазона l ... N, где М - количество букв в имени Петиной сестры, и-e число должно быть номером кубика, который следует положить на i-e место при составлении имени Петина сестры . Кубики нумеруются с 1, в том порядке, в котором они заданы во входном файле. Если решений несколько, выведите любое. Разделяйте числа пробелами. Пример ввода 4 ANN ANNNNN BCDEFG HIJKLM NOPQRS Пример вывода NO
0
|
23.05.2013, 23:35 | |
Ответы с готовыми решениями:
23
Школьная олимпиада. Задача с кубиками (самая сложная из всех задач) Задача с кубиками Олимпиадная задача с кубиками Игра с кубиками |
24.05.2013, 03:08 | 2 | |||||
Строится матрица. Для каждого кубика отмечаем все позиции, на которых он может стоять.
Если строки и столбцы матрицы можно переставить так, что будет заполнена главная диагональ подматрицы размера имени, то любая такая перестановка будет решением.
4
|
0 / 0 / 1
Регистрация: 29.04.2013
Сообщений: 13
|
|
24.05.2013, 18:41 [ТС] | 3 |
да я понял сам алгоритм, а вот закодить не получается(
ребят, может кто сможет помочь? через потоковые алгоритмы
0
|
24.05.2013, 19:30 | 4 |
Не похоже, что поняли.
И с учетом размера (1 <N <100), полный перебор невозможен. Почитайте про Поиск с возвратом.
0
|
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
|
|
24.05.2013, 21:30 | 5 |
Мне кажется, что эту задачу можно решить через графы
https://www.cyberforum.ru/atta... 1369416467 Думаю, что идея понятна. Другое вопрос реализация...
0
|
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
|
|
24.05.2013, 21:35 | 6 |
Допустим длина имени = 5, количество кубиков, на которых есть хотя бы одна буква из имени = 20, тогда нужно выбрать 5 кубиков без повторений (из всех 20) (таких сочетаний = 20! / ( 5! * (20 - 5)! ) и для всех вариантов расстановки этих пяти кубиков проверить диагональ (проверок = 5! = 120) и если диагональ заполнена, то эта комбинация подходит. Если нет, то выбрать следующие 5 кубиков и повторить. Правильный ход мыслей?
0
|
24.05.2013, 22:04 | 7 |
1. Граф или матрица - неважно, это эквивалентные представления.
2. Я думаю, тут возможны сокращающие перебор оптимизации. Например, можно вычеркнуть все кубики, не содержащие ни одной буквы имени. Для всех кубиков, содержащих только одну букву имени, их место уже определено. Можно убедиться, что "разных" кубиков не меньше чем разных букв в имени. Т.е., при "удачном" раскладе можно убедиться, что решения нет, без фактического решения задачи. Ну и, любой отброшенный кубик сокращает число вариантов для перебора. 3. Мне кажется, удобнее работать с деревом выбора. На каждом i-ом шаге есть r[i] (r < N) вариантов выбора кубика (т.е. r[i] дочерних узлов). Строим дерево и рекурсивно обходим его в глубину. Если на каком-то маршруте удалось построить имя - задача решена, выводим решение. Если нет - возвращаемся назад (по стеку) и пробуем следующий маршрут. Если обойдено все дерево и не удалось построить имя - нет решения.
1
|
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
|
|
24.05.2013, 22:55 | 8 |
А что делать с кубиками которые содержат больше одной буквы из имени ?
Имя: ANN Кубики: ANNNNN BCDEFG HIJKLM NOPQRS AAAAAA В таком случае под букву "А" можно взять как первый, так и последний, но если брать последний, то решение существует. Так что же делать с такими кубиками(которые могут заменить более одной буквы) в дереве?
0
|
24.05.2013, 23:18 | 9 |
IMHO, здесь возможен только перебор - то есть, как было написано, обход дерева либо до первого решения, либо до исчерпания вариантов (если решения нет).
Важно другое: заданная размерность (up to 100) настолько велика, что без специальных ухищрений и решения "по частям" ее ни впихнуть ни в компьютер, ни в нашу Вселенную. Поэтому все, что может уменьшить число вариантов перебора, должно быть использовано.
1
|
0 / 0 / 1
Регистрация: 29.04.2013
Сообщений: 13
|
|
25.05.2013, 00:24 [ТС] | 10 |
А если тут попробовать методом ветвей и границ? На сколько я помню метод на много меньше чем полным перебором
0
|
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
|
||||||
25.05.2013, 15:43 | 12 | |||||
вот мое решение (перебор с возвратом)
Пример:
0
|
0 / 0 / 1
Регистрация: 29.04.2013
Сообщений: 13
|
|
26.05.2013, 01:15 [ТС] | 13 |
А может кто-то знает как решить данную задачу через потоковые алгоритмы?
0
|
415 / 411 / 95
Регистрация: 06.10.2011
Сообщений: 832
|
||||||
26.05.2013, 12:28 | 14 | |||||
Исправил найденную ошибку и добавил предварительную проверку на количество кубиков.
Кликните здесь для просмотра всего текста
Что это такое? В гугле по такому запросу нахожу только алгоритмы шифрования и тп.
0
|
0 / 0 / 1
Регистрация: 29.04.2013
Сообщений: 13
|
|
26.05.2013, 16:07 [ТС] | 15 |
Мы сейчас проходим по программированию 4 потоковых алгоритма -
1) Эдмондса-Карпа - http://ru.wikipedia.org/wiki/А... са_—_Карпа 2)Алгоритм поиска увеличувающей цепи - http://on2.docdat.com/docs/198... ml?page=11 3)Алгоритм поиска потока минимальной стоимости - http://ru.wikipedia.org/wiki/П... _стоимости 4)и Алгоритмы нахождения максимального потока - http://algolist.manual.ru/maths/graphs/maxflows/ один из этих алгоритмов. Задача стоит именно с помощью этих алгоритмов развязать задачу
0
|
2 / 2 / 2
Регистрация: 13.02.2013
Сообщений: 90
|
|
30.05.2013, 16:48 | 16 |
Сообщение было отмечено TheCalligrapher как решение
Решение
Эта задача сводится к нахождению максимального паросочетания в двудольном графе.
Назовем кубики и буквы имени сестры вершинами нашего графа и соединим кубик ребром с буквой, если эта буква написана на этом кубике. Заметим, что граф действительно двудольный, а выбор кубиков для выкладывания имени эквивалентен по строению паросочетания. Поскольку число ребер в паросочетании не превышает числа вершин в меньшей доле, то искомое паросочетание действительно максимально. Для нахождения максимального паросочетания разработаны стандартные алгоритмы, хорошо освещенные в литературе
1
|
0 / 0 / 0
Регистрация: 06.07.2020
Сообщений: 6
|
||||||
06.07.2020, 21:31 | 17 | |||||
Родители подарили Пете набор детских кубиков. Поскольку Петя скоро пойдет в школу, они купили ему кубики с буквами. На каждой из шести граней каждого кубика написана буква. Вот начало решения.
0
|
661 / 662 / 106
Регистрация: 29.05.2015
Сообщений: 3,967
|
|
07.07.2020, 23:31 | 18 |
Начал с чего попроще - 30 случайных кубиков и слово из 10 букв. Программа для каждой буквы выбирает все возможные кубики. А как лучше теперь убрать лишнее? Есть идеи?
0
|
661 / 662 / 106
Регистрация: 29.05.2015
Сообщений: 3,967
|
|
11.07.2020, 15:11 | 19 |
Получилось. 26 случайных кубиков и латинский алфавит. Алгоритм аналитический, не перебором, поэтому скорость будет высокой. Пока прога работает в виде полуавтомата - что-то делает программа, что-то приходится делать человеку. Но алгоритм уже понятен, перенести в код дело техники:
0
|
2 / 2 / 0
Регистрация: 03.05.2020
Сообщений: 202
|
|
04.08.2021, 05:16 | 20 |
Актуально
0
|
04.08.2021, 05:16 | |
04.08.2021, 05:16 | |
Помогаю со студенческими работами здесь
20
Головоломка с кубиками Внести в игру c кубиками возможность жульничать Видеокарта, после подключения телевизора начала воспроизводить всё полосатыми кубиками Когда делаю видео в GIF то размытые фоны у видео становятся кубиками, или превращаются в отделенные цвета Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |