0 / 0 / 1
Регистрация: 29.04.2013
Сообщений: 13
|
|
1 | |
Задача с кубиками23.05.2013, 23:35. Показов 17192. Ответов 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
Школьная олимпиада. Задача с кубиками (самая сложная из всех задач) Задача с кубиками Олимпиадная задача с кубиками Игра с кубиками |
661 / 662 / 106
Регистрация: 29.05.2015
Сообщений: 3,964
|
|
07.08.2021, 09:40 | 21 |
1
|
661 / 662 / 106
Регистрация: 29.05.2015
Сообщений: 3,964
|
|
12.08.2021, 09:26 | 22 |
Задача оказалась сложнее, чем я предполагал.
1. Раскладываем кубики по буквам - к каждой букве имени все кубики, которые содержат эту букву. 2. Ищем "уникальные" кубики - т.е. если такая буква в имени одна и есть кубик, в котором совпадает только эта буква (а остальные никуда не подходят) - нужно оставлять именно его, потому что в других местах он бесполезен. 3. Ищем буквы, к которым подходит только один кубик - он безальтернативный, вычищаем его из других букв. 4. Повторяем п.2 и 3 до тех пор, пока ситуация меняется (улучшается - убираются "лишние" кубики). Далее может сложиться ситуация, когда убрано всё возможное лишнее, но задача не решена - остались буквы, под которыми несколько (много) кубиков - и нужно выбрать, где какой оставить. Я пробовал оставлять: - которых минимальное количество среди оставшихся - которых максимальное количество - выбирать букву, под которой меньше всего кубиков - и тупо оставлять первый (они отсортированы по алфавиту) Ни один из этих способов не даёт гарантированного результата. Нужен перебор - но боюсь, что при большом количестве кубиков это займёт много времени. Есть какие-то предложения? Или я вообще фигнёй занимаюсь, и есть другое более простое решение?
0
|
YUEN HOIFEF
|
12.08.2021, 12:02
#23
|
Не по теме:
0
|
alexu_007
|
12.08.2021, 16:03
Задача с кубиками
#24
|
Не по теме: Петя? Мне задача понравилась, я решил её решить. Разумеется, код для двоечников выкладывать не буду.
0
|
12.08.2021, 16:03 | |
Головоломка с кубиками Внести в игру c кубиками возможность жульничать Видеокарта, после подключения телевизора начала воспроизводить всё полосатыми кубиками Когда делаю видео в GIF то размытые фоны у видео становятся кубиками, или превращаются в отделенные цвета Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |