LINUX.ORG.RU
ФорумTalks

Russian Code Cup: разбор задачки про сообщение инопланетян.


0

1

Здравствуйте, ребята!

Вот задачка:

После многих лет безуспешных попыток ученые наконец-то смогли установить связь с разумной цивилизацией в космосе и выяснили, что алфавит инопланетян состоит всего из двух букв: a и b. Для приема сообщений был сконструирован специальный приемник, который выдает символы a, b, а также специальный символ ?, если разобрать, какой символ был передан, не удалось.

Анализ показал, что инопланетяне передают все свои сообщения в виде двух одинаковых записанных подряд строк. Например, строки «abab» или «aaaaaa» могут быть сообщениями инопланетян, а «abba» или «aaa» — нет.

Прибор, сконструированный учеными, получив на вход потенциальное сообщение инопланетян, выдает все возможные способы прочитать строку без учета описанного выше свойства. Например, получив строку «ab??» прибор выдает строки «abaa», «abab», «abba» и «abbb», из них на самом деле только строка «abab» может быть сообщением от инопланетян, а остальные три не могут.

Для улучшения качества прибора ученые хотят узнать, сколько строк из тех, которые выведены прибором, не могут быть сообщением инопланетян. Помогите им это сделать.

Формат входных данных

В первой строке содержится натуральное число n — число слов в сообщении, полученного учеными.

В каждой из следующих n строк содержится слово из сообщения, состоящее из символов a, b и ?. Гарантируется, что все слова имеет четную длину, а также, что в каждом слове есть хотя бы один ?. Суммарная длина всех слов не превышает 200000. Не гарантируется, что есть хотя бы один способ расшифровать каждое слово как сообщение инопланетян.

Формат выходных данных

Выведите n строк. В i-ой строке выведите число способов заменить ? на буквы a, b так, чтобы i-е слово не было корректным сообщением инопланетян. Так как число способов может быть очень большим, необходимо выводить его по модулю 10^9+7.

Примеры

Входные данные

3
ab?b
baa?
abb???

Выходные данные

1
2
7

А вот предлагаемый алгоритм решения:

Заметим, что ответ равен числу всех возможных сообщений, минус число тандемных повторов. Обозначим за m число вопросов в строке, а за 2l длину строки. Тогда количество всех возможных сообщений равно 2^m. Число тандемных повторов можно найти из следующих рассуждений. Если на позиции i стоит знак вопроса, а на позиции i + l a или b, то в тандемном повторе, на позиции i должна стоять та же буква. Если же на обеих позициях i и i + l стоят знаки вопроса, то ответ нужно домножить на два. Аналогично рассматривается ситуация, когда знак вопроса стоит на позиции i + l. Если на позициях i и i + l стоят различные буквы, то тандемных повторов для такой строки не существует.

Время работы O(длины сообщения).

Вопрос: является ли описываемый алгоритм правильным решением?

★★★★★

Последнее исправление: Xintrea (всего исправлений: 1)

В разборе задачи сказано: «Заметим, что ответ равен числу всех возможных сообщений, минус число тандемных повторов». Далее сказано как считать число тандемных повторов.

Но ответ должен быть равен совершенно другому числу, а именно: «сколько строк из тех, которые выведены прибором, не могут быть сообщением инопланетян?».

Рассморим примеры

Пример: «a?ab?a» - в первой позиции в первой части имеем a, во второй части - b. Машина, согласно условиям, нагенерирует сообщения:

aaabaa
aaabba
ababaa
ababba

И это все 4 неправильных сообщения.

А если в первой позиции основной строки и повтора будет правильный символ, например «a?aa?a», машина нагенерирует такие сообщения:

aaaaaa
aaaaba
abaaaa
abaaba

И из них 2 сообщения правильных, два сообщения неправильных.

А описываемый в разборе задачи алгоритм высчитает для обоих этих случаев одинаковое число 4, что не соответствует поставленному в задаче вопросу «сколько строк из тех, которые выведены прибором, не могут быть сообщением инопланетян?».

Таким образом выходит, что вышенаписанный алгоритм неправильный.

Правильно я понимаю или где-то ошибся?

Xintrea ★★★★★
() автор топика
Ответ на: комментарий от Xintrea

Правильно я понимаю или где-то ошибся?

В решении предполагается, что только пара соответствующих вопросительных знаков на i-м и (i+L)-м местах делают свой вклад в ответ. В сообщении ?? ответ должен быть 2, и ты его получишь, если пробежишься до середины строки и сравнишь соотвествующие символы.

metar ★★★
()
Ответ на: комментарий от metar

В решении ничего не предполагается. Вопрос должен быть поставлен однозначно.

В вашем случае машина нагенерирует:

aa
ab
ba
bb

Варианты ab и ba не могут быть сообщением инопланетян, значит ответ 2, так как вопрос был «сколько строк из тех, которые выведены прибором, не могут быть сообщением инопланетян?».

Так что повторяю вопрос. Правильный ли дан алгоритм в разборе задачи, или он некорректен поставленному вопросу?

Xintrea ★★★★★
() автор топика

Вначале, нужно было бы форматировать решение нормально(я долго пытался понять откуда взялось 2m).

И еще я так и не понял что такое «тандемный повтор». Вроде, «ответ равен числу всех возможных сообщений, минус число корректных сообщений»

hired777
()
Ответ на: комментарий от Deleted

Там гарантируется, что есть хотя бы одна верная интерпретация.

Это где гарантируется? Я не нашел.

Гарантируется только то, что все слова имеет четную длину, а также, что в каждом слове есть хотя бы один знак вопроса.

Xintrea ★★★★★
() автор топика
Ответ на: комментарий от Xintrea

Это где гарантируется? Я не нашел.

Если все варианты неверны, то пришельцы гонят какую-то чушь вместо осмысленных сигналов.

Sadler ★★★
()
Ответ на: комментарий от Xintrea

Не гарантируется, что есть хотя бы один способ расшифровать каждое слово как сообщение инопланетян.

Ааай. Вредно быстро читать. Тогда согласен, решение неполное - необходимо проверять существование верной интерпретации. И в случае с двумя вопросительными знаками нужно домножать только один раз.

Deleted
()
Ответ на: комментарий от Sadler

Если все варианты неверны, то пришельцы гонят какую-то чушь вместо осмысленных сигналов.

Ну, и что? Количество этих вариантов и будет решением согласно поставленным условиям.

Xintrea ★★★★★
() автор топика
Ответ на: комментарий от Deleted

Извиняюсь второй раз. Решение верное.

Deleted
()
Ответ на: комментарий от Xintrea

Пример: «a?ab?a» - в первой позиции в первой части имеем a, во второй части - b. Машина, согласно условиям, нагенерирует сообщения:

aaabaa
aaabba
ababaa
ababba

И это все 4 неправильных сообщения.

Сравниваем нулевой и третий символ, получаем, что они разные => сообщение некорректно, можно смело возвращать ноль.

Deleted
()
Ответ на: комментарий от Xintrea

В решении ничего не предполагается.

Это предполагается в _вашем_ решении. То, что публикуют на сайте, называется разбор, призвано подсказать вам идею и решением не является.

metar ★★★
()

С той стороны сидит малолетний инопланетянин и посылает всякий флуд. В сообщениях нет смысла.

the_green
()
Ответ на: комментарий от Deleted

Сравниваем нулевой и третий символ, получаем, что они разные => сообщение некорректно, можно смело возвращать ноль.

Именно, некорректно, поэтому оно не может быть сообщением инопланетян. И нам нужно указать количество строк, которые не могут быть сообщением инопланетян. То есть решение в этом примере - 4.

Xintrea ★★★★★
() автор топика

Алгоритм верный.

Так как число способов может быть очень большим, необходимо выводить его по модулю 10^9+7.

Facepalm

segfault ★★★★★
()
Ответ на: комментарий от Xintrea

И да, в разборе нет алгоритма. Там есть несколько утверждений:

1. Если на позиции i стоит знак вопроса, а на позиции i + l a или b, то в тандемном повторе, на позиции i должна стоять та же буква.

2. Если же на обеих позициях i и i + l стоят знаки вопроса, то ответ нужно домножить на два.

3. Аналогично рассматривается ситуация, когда знак вопроса стоит на позиции i + l. (единственное, к чему можно придраться, это предложение нужно перенести в пункт 1)

4. Если на позициях i и i + l стоят различные буквы, то тандемных повторов для такой строки не существует.

Для строки a?aa?a один раз выполняется условие 2, остальные условия не выполняются ни разу => для этой строки существует только две верных интерепретации.

2^2 - 2 == 2

Deleted
()

Если же на обеих позициях i и i + l стоят знаки вопроса, то ответ нужно домножить на два.

это как? Что будет если скормить строку

«a??ba??b»

?

dikiy ★★☆☆☆
()
Последнее исправление: dikiy (всего исправлений: 1)

@тред не читал.

Прежде чем допускать математиков к работе с молодежью...
Необходимо устраивать проф.отбор у психиатров.

Задание писали сами инопланетяне, они освоили 22/32 буквы алфавита быстрее, чем земляне разодрали их двухбуквенную бинопись.

Deleted
()
Последнее исправление: RTP (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.