Задача С. Послание внеземного разума

@art_em_ · Регистрация: 09.10.2020

Студворк — интернет-сервис помощи студентам

Помогите пж)))
Задача С. Послание внеземного разума

Сенсация! Известный специалист по UFO профессор Персиков получил послание от внеземного разума. Во всяком случае он так считает. Послание представляет собой непрерывную последовательность из сигналов нескольких типов, каждый из этих типов для определенности можно обозначить малой буквой латинского алфавита. Профессор считает, что доказательством искусственности происхождения сигнала служит его периодичность. При этом период должен быть строго равен "константе Персикова" - числу PP. Такую последовательность назовём PP - периодичной.

К сожалению, некоторые сигналы из-за прохождения сквозь бездны пространства (а может даже и времени) были утеряны. Их заменили на знак вопроса. Теперь профессору для дальнейшей работы требуется выяснить, можно ли как-то заменить утерянные сигналы на буквы так, чтобы последовательность стала PP - периодичной. Для чистоты эксперимента, полученная из космоса последовательность была размещена среди себе подобных. Не подведите, в ваших руках -- будущее межгалактических взаимоотношений!

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

В первой строке содержится два числа через пробел: NN -- общее количество строк, которые вам нужно проверить на PP-периодичность и число PP -- константа Персикова (1 \leq P \leq 5*10^3 1≤ P≤5∗10
3
). Далее содержится NN непустых строк, состоящих из малых букв латиницы и знаков вопроса. 1 \leq N \leq 5*10^4 1≤ N≤5∗10
4
, суммарная длина всех строк не превосходит 2*10^52∗10
5
.

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

Вывести NN строк, в каждой из которых вывести либо "YES", если соответствующую строку можно сделать PP-периодичной путем замены всех знаков вопроса на некоторые буквы и "NO" в противном случае. Будем считать последовательность PP- периодичной, если для любых двух символов, расстояние между которыми кратно PP верно, что они совпадают.

Sample Input:

8 4
abacabaca
abracadabra
aa?aaa?aaaaaaaaaa
q
???????
q?er?w?
q?erw??
q?er?wer?werw?er
Sample Output:

YES
NO
YES
YES
YES
YES
NO
NO

@Gdez · 09.10.2020, 20:14

art_em_, Идеи или решения есть?

@korollicha · 09.10.2020, 20:34

Я решил

@Fury67 · 09.10.2020, 20:44

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def pp(n, a):
    for j in range(n):
        c = ''
        for i in range(0, len(a), n):
            if j + i < len(a):
                if a[j + i] != '?':
                    if c == '':
                        c = a[j + i]
                    else:
                        if a[j + i] != c:
                            return 'NO'
    return 'YES'
 
a = []
b = input().split()
for i in range(int(b[0])):
    a.append(pp(int(b[1]), input()))
print('\n'.join(a))

Добавлено через 21 секунду
Не очень красиво, конечно, но работает, вроде...

Добавлено через 1 минуту

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
8 4
abacabaca
abracadabra
aa?aaa?aaaaaaaaaa
q
???????
q?er?w?
q?erw??
q?er?wer?werw?er
 
YES
NO
YES
YES
YES
YES
NO
NO

@OHtuzh · 11.10.2020, 11:42

Я только начинаю кодить, поэтому если не сложно, то можешь объяснить зачем ты перебирал в цикле for значение параметра n, он же в условии - смещение P? Оно ведь постоянно и необходимо проверить смещение по данному P и кратным ему, а не меньшим. Ниже - моё решение, но оно даёт некорректные результаты и я не знаю в чём ошибка.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def f(a, p):
    ans = ''
    for i in range(len(a)):
        if (i + p < len(a)):
            if (a[i + p] != '?' or a[i] != '?'):
                if(a[i] != a[i + p]):
                    ans = 'NO'
    if (ans == 'NO'):
        return ans
    else:
        return 'YES'    
 
answer = []
inp = [int(i) for i in input().split()]
N, P = inp[0], inp[1]
 
for j in range(N):
    A = str(input())
    result = f(A, P)
    answer.append(result)

for i in range(len(answer)):
print(answer[i])

@Gdez · 11.10.2020, 13:26

OHtuzh, вылетает по типу такого ввода
q?er?wer?werw?er
Обрати внимание на периодичность первого символа
q***?***?***w***
У тебя в коде проверяется текущий с последующим
q -> ? - проходит
? -> ? - проходит
? -> w - проходит, но ведь q != w

Добавлено через 4 минуты
Алгоритм можно было построить проще - "выдернуть" символы из строки с периодичностью "р" либо циклом либо срезом [i::р]. Поместить в множество (повторяющиеся удалятся автоматом из множества). Добавить в множество "?" на случай отсутствия в строке этого знака.
А теперь проверить, если в множестве больше 2 элементов, то NO

Добавлено через 2 минуты
Возможно так

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def f(a, p):
    k = len(a)
    for i in range(p) :
        if i + p < k :
            ans = set([a[i] for i in range(i,k,p)])
            ans.add('?')
            if len(ans) > 2 :
                    return 'NO'
    return 'YES' 
 
N, P = map(int,input().split())
 
for j in range(N):
    A = input()
    print(f(A, P))

@OHtuzh · 11.10.2020, 17:11

Gdez, спасибо.

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .

@art_em_ 0 / 1 / 0 Регистрация: 09.10.2020 Сообщений: 8

	Задача С. Послание внеземного разума 09.10.2020, 19:43. Показов 6658. Ответов 6 Метки нет (Все метки) Помогите пж))) Задача С. Послание внеземного разума Сенсация! Известный специалист по UFO профессор Персиков получил послание от внеземного разума. Во всяком случае он так считает. Послание представляет собой непрерывную последовательность из сигналов нескольких типов, каждый из этих типов для определенности можно обозначить малой буквой латинского алфавита. Профессор считает, что доказательством искусственности происхождения сигнала служит его периодичность. При этом период должен быть строго равен "константе Персикова" - числу PP. Такую последовательность назовём PP - периодичной. К сожалению, некоторые сигналы из-за прохождения сквозь бездны пространства (а может даже и времени) были утеряны. Их заменили на знак вопроса. Теперь профессору для дальнейшей работы требуется выяснить, можно ли как-то заменить утерянные сигналы на буквы так, чтобы последовательность стала PP - периодичной. Для чистоты эксперимента, полученная из космоса последовательность была размещена среди себе подобных. Не подведите, в ваших руках -- будущее межгалактических взаимоотношений! Формат входных данных В первой строке содержится два числа через пробел: NN -- общее количество строк, которые вам нужно проверить на PP-периодичность и число PP -- константа Персикова (1 \leq P \leq 510^3 1≤ P≤5∗10 3 ). Далее содержится NN непустых строк, состоящих из малых букв латиницы и знаков вопроса. 1 \leq N \leq 510^4 1≤ N≤5∗10 4 , суммарная длина всех строк не превосходит 2*10^52∗10 5 . Формат выходных данных Вывести NN строк, в каждой из которых вывести либо "YES", если соответствующую строку можно сделать PP-периодичной путем замены всех знаков вопроса на некоторые буквы и "NO" в противном случае. Будем считать последовательность PP- периодичной, если для любых двух символов, расстояние между которыми кратно PP верно, что они совпадают. Sample Input: 8 4 abacabaca abracadabra aa?aaa?aaaaaaaaaa q ??????? q?er?w? q?erw?? q?er?wer?werw?er Sample Output: YES NO YES YES YES YES NO NO 1

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	09.10.2020, 20:14
	art_em_, Идеи или решения есть? 1

@korollicha 1 / 1 / 0 Регистрация: 10.05.2020 Сообщений: 3
	09.10.2020, 20:34
	Я решил 1

@OHtuzh 0 / 0 / 0 Регистрация: 11.10.2020 Сообщений: 7
	11.10.2020, 17:11
	Gdez, спасибо. 0