Послание внеземного разума 2

@789GoDDeM · Регистрация: 15.10.2020

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

Нужна помощь, помогаю малому

Профессор Персиков снова получил послание внеземного разума. Он по-прежнему считает, что доказательством этого является его периодичность. При этом период должен быть равен “константе Персикова” - числу PP. К сожалению, послание не совсем периодичное. Если сказать более точно, то оно совсем не периодичное. Однако, это никак не останавливает исследователя космических глубин. Он говорит, что некоторые сигналы были неправильно откалиброваны, отфильтрованы и интерпретированы. По-прежнему мы будем считать что все сигналы отображаются малыми буквами латинского алфавита, но в данной задаче все они распознаны и знаков вопроса нет. Тем не менее профессор, согласно своей теории, может заявить, что все вхождения такой-то буквы интерпретированы неверно и их все следует заменить на вхождения какой-то другой (одной и той же) буквы. Более строго: пусть на позициях p_{i_1}, p_{i_2}, \ldots p_{i_k}pi1,pi2,…pik и только на них в последовательности находится одна и та же буква. Профессор может выбрать любую другую букву (как встречающуюся в слове, так и не встречающуюся) и поставить её во всех этих позициях. Например в слове qqzbbacabadabaqqzbbacabadaba он может выбрать все вхождения буквы bb и заменить их на букву aa, получив слово qqzaaacaaadaaaqqzaaacaaadaaa (это считается одной заменой, независимо от числа вхождений). Очевидно, что таким образом любое послание можно сделать PP-периодическим, но профессор заинтересован сделать как можно меньше таких замен. При этом он хочет получить лексикографически минимальное послание.

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

В первой строке содержится число PP — константа Персикова (1 \leq P \leq 10^5 1≤ P≤105 ). В следующей строке содержится непустая последовательность, состоящая из малых букв латиницы. Длина этой строки не превосходит 2*10^22∗102.

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

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

Sample Input:
4
qqzbbacabadaba
Sample Output:
aacaaacaaacaaa

@Vladimir. · 20.10.2020, 01:17

Сообщение от 789GoDDeM

Нужна помощь, помогаю малому

Сообщение от 789GoDDeM

2*10^22∗102.

Явно какая-то ошибка в задании, вероятно, при копировании. Перепишите используя тег LATEX или просто руками вбейте

Не по теме:

все не мог понять, почему в валидаторах используют ограничение

P≤105

Сейчас до меня дошло, что это 10^5

@789GoDDeM · 20.10.2020, 01:23 **[ТС]**

Надеюсь теперь все верно

Профессор Персиков снова получил послание внеземного разума. Он по-прежнему считает, что доказательством этого является его периодичность. При этом период должен быть равен “константе Персикова” - числу PP. К сожалению, послание не совсем периодичное. Если сказать более точно, то оно совсем не периодичное. Однако, это никак не останавливает исследователя космических глубин. Он говорит, что некоторые сигналы были неправильно откалиброваны, отфильтрованы и интерпретированы. По-прежнему мы будем считать что все сигналы отображаются малыми буквами латинского алфавита, но в данной задаче все они распознаны и знаков вопроса нет. Тем не менее профессор, согласно своей теории, может заявить, что все вхождения такой-то буквы интерпретированы неверно и их все следует заменить на вхождения какой-то другой (одной и той же) буквы. Более строго: пусть на позициях p_i1, p_i2, ... p_in и только на них в последовательности находится одна и та же буква. Профессор может выбрать любую другую букву (как встречающуюся в слове, так и не встречающуюся) и поставить её во всех этих позициях. Например в слове qqzbbacabadabaqqzbbacabadaba он может выбрать все вхождения буквы bb и заменить их на букву aa, получив слово qqzaaacaaadaaaqqzaaacaaadaaa (это считается одной заменой, независимо от числа вхождений). Очевидно, что таким образом любое послание можно сделать PP-периодическим, но профессор заинтересован сделать как можно меньше таких замен. При этом он хочет получить лексикографически минимальное послание.

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

В первой строке содержится число P — константа Персикова (1 ≤ P≤10⁵ ). В следующей строке содержится непустая последовательность, состоящая из малых букв латиницы. Длина этой строки не превосходит 2*10².

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

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

Sample Input:
4
qqzbbacabadaba
Sample Output:
aacaaacaaacaaa

@Romiusse · 20.10.2020, 20:51

Крч. 1)представляем строку как граф, где вершины буквы. Вершины будут соединятся, если буквы зависят друг от друга, т.е если они одного периода. 2) находим компоненты связанности графа. 3) В каждой компоненте найдем наименьшую букву и заменем ей все буквы, которые есть в этой компоненте. 4) Выведем ответ.
(Это полное решение с ограничениями n<= 10^5)

@789GoDDeM · 20.10.2020, 22:07 **[ТС]**

Можете пожалуйста написать это кодом

@DarkSwwwan · 21.10.2020, 12:26

Rominusse]

Крч. 1)представляем строку как граф, где вершины буквы. Вершины будут соединятся, если буквы зависят друг от друга, т.е если они одного периода. 2) находим компоненты связанности графа. 3) В каждой компоненте найдем наименьшую букву и заменем ей все буквы, которые есть в этой компоненте. 4) Выведем ответ.
(Это полное решение с ограничениями n<= 10^5)

А как можно найти все компоненты связности? какой нибудь dfs?

@sveta1233 · 21.10.2020, 13:03

Сообщение от DarkSwwwan

Rominusse]

А как можно найти все компоненты связности? какой нибудь dfs?

я тоже не могу это понять

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

Сообщение от Romiusse

Крч. 1)представляем строку как граф, где вершины буквы. Вершины будут соединятся, если буквы зависят друг от друга, т.е если они одного периода. 2) находим компоненты связанности графа. 3) В каждой компоненте найдем наименьшую букву и заменем ей все буквы, которые есть в этой компоненте. 4) Выведем ответ.
(Это полное решение с ограничениями n<= 10^5)

Как представить строфу,как граф?я просто никогда не работала с графами

@Tishran · 21.10.2020, 13:42

Сообщение от Romiusse

т.е если они одного периода

Что значит одного периода? Т е если между ними расстояние кратное Р, или же они в одной группе(например qqzb, baca....)?

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

Сообщение от Romiusse

Крч. 1)представляем строку как граф, где вершины буквы. Вершины будут соединятся, если буквы зависят друг от друга, т.е если они одного периода. 2) находим компоненты связанности графа. 3) В каждой компоненте найдем наименьшую букву и заменем ей все буквы, которые есть в этой компоненте. 4) Выведем ответ.
(Это полное решение с ограничениями n<= 10^5)

я попробовал так, но по времени не один тест в С2 не проходит

@lolbaby · 21.10.2020, 13:48

Сообщение от Tishran

Что значит одного периода? Т е если между ними расстояние кратное Р, или же они в одной группе(например qqzb, baca....)?

Расстояние между двумя элементами, которые выбрали равно P

@Tishran · 21.10.2020, 13:51

Сообщение от lolbaby

Расстояние между двумя элементами, которые выбрали равно P

в таком случае код, написанный по логике:

Сообщение от DarkSwwwan

Крч. 1)представляем строку как граф, где вершины буквы. Вершины будут соединятся, если буквы зависят друг от друга, т.е если они одного периода. 2) находим компоненты связанности графа. 3) В каждой компоненте найдем наименьшую букву и заменем ей все буквы, которые есть в этой компоненте. 4) Выведем ответ.
(Это полное решение с ограничениями n<= 10^5)

выводит в sample output bacabacabacaba, а не aacaaacaaacaaa. Или же я что-то неправильно реализовал....

@lolbaby · 21.10.2020, 13:55

Сообщение от Tishran

в таком случае код, написанный по логике:

выводит в sample output bacabacabacaba, а не aacaaacaaacaaa. Или же я что-то неправильно реализовал....

в bacabacabacaba сделано на одну замену больше, хотя можно уложиться в меньшее количество замен.

@Tishran · 21.10.2020, 14:12

lolbaby, но как это сделать, логика Romiusse выше не работает получается?

@lolbaby · 21.10.2020, 14:23

Сообщение от Tishran

lolbaby, но как это сделать, логика Romiusse выше не работает получается?

по идее логика Romiusse должна работать, но почему-то идёт лишняя замена. Нужно смотреть код, скорее всего программа просто не нашла путь короче

@Tishran · 21.10.2020, 14:25

lolbaby,

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
p = int(input())
string = input()
 
n = len(string)
graph = {}
comps = []
 
used = [False] * n
 
 
def dfs(v):
    used[v] = True
    comps[-1].append(v)
 
    for u in graph[v]:
        if not used[u]:
            dfs(u)
 
 
# if len(string) < p:
#     print(string)
# else:
letters = list(string)
words = []
 
for i in range(n):
    graph[i] = []
    for j in range(n):
        if abs(i - j) % p == 0 and i != j:
            graph[i].append(j)
 
for i in range(n):
    if not used[i]:
        comps.append([])
 
        dfs(i)
 
for i in comps:
    for j in range(len(i)):
        i[j] = ord(string[i[j]])
 
for i in range(len(comps)):
    comps[i] = [min(comps[i])] * len(comps[i])
 
res = ''
for i in range(p):
    for j in comps:
        try:
            res += chr(j[i])
        except IndexError:
            pass
 
print(res)

моя реализация

@LiveisFpv · 21.10.2020, 14:45

У меня тоже одну лишнюю замену делает, никак не могу понять почему...

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
p = int(input())
msg = input()
used = set()
msg_answer = list(msg)
mat = [[[0, msg[i]] for i in range(len(msg))] for j in range(len(msg))]
 
ex = set()  # множество посещенных вершин
comps = list(list())  # список компонент связности
 
per4 = list(list())
for i in range(p):
    per4.append([i])
    count = i
    while count + p < len(msg):
        per4[i].append(count + p)
        count += p
 
#print(per4)
 
def dfs(node):  # start - начальная вершинка
    ex.add(node)
    comps[-1].append(node)
    for coherence in range(len(mat)):
        if mat[node][coherence][0] == 1 and coherence not in ex:
            dfs(coherence)
 
 
for i in range(len(msg)):
    for j in range(len(msg)):
        if mat[i][i][1] == mat[i][j][1] and abs(i - j) % p == 0 and i != j:
            mat[i][j][0] += 1
 
# поиск в глубину
for i in range(len(msg)):
    comps.append([])
    dfs(i)
 
for i in range(len(comps)):
    if len(comps[i]) > 1:
        minindx=150
        kk=comps[i][0]%p
        while kk < len(msg):
                if minindx > ord(msg[kk]):
                    minindx = ord(msg[kk])
                    ii=kk
                kk+=p   
        if msg_answer[comps[i][0]] != msg_answer[ii] and msg_answer[comps[i][0]] not in used:
            used.add(letter)
            for v in comps[i]:
                msg_answer[v] = msg_answer[ii]
 
# поиск наименьшей буквы
for i in range(len(per4)):
    min_letter = msg_answer[per4[i][0]]
    for j in range(len(per4[i])):
        if min_letter > msg_answer[per4[i][j]]:
            min_letter = msg_answer[per4[i][j]]
    for v in per4[i]:
        msg_answer[v] = min_letter
 
 
# # вывод списка компонент связности
# for i in range(len(comps)):
#     print(comps[i])
#
# # вывод матрицы
# for i in range(len(msg)):
#     print(mat[i])
 
# вывод ответа
print(*msg_answer, sep='')

Вот моя реализация

@lolbaby · 21.10.2020, 15:02

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

@DarkSwwwan · 21.10.2020, 15:20

Хз, у меня всё работает, но медленно(я dfs криво написал)

@Gdez · 21.10.2020, 19:30

DarkSwwwan, сервис тестировщика доступен?

@Romiusse · 22.10.2020, 13:07

DarkSwwwan, Да, это dfs, можите почитать на eemax.

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <string>
#include <map>
#include <numeric>
#include <queue>
#include <functional>
#include <stack>
#include <iomanip>
#include <bitset>
using namespace std;
 
 
vector<vector<long long>> g;
vector<long long> color;
void dfs(int u, int c) {
    color[u] = c;
    for (auto i : g[u]) {
        if (color[i] == -1) {
            dfs(i, c);
        }
    }
}
int main()
{
    long long n; cin >> n;
    string s; cin >> s;
    g.resize(26); color.resize(26,-1);
    for (int i = 0; i < n; i++) {
        set<long long> r;
        vector<long long> v;
        for (int j = i; j < s.size(); j += n) {
            r.insert(s[j] - 'a');
        }
        for (auto j : r) v.push_back(j);
        for (int j = 0; j < v.size(); j++) {
            for (int k = j + 1; k < v.size(); k++) {
                g[v[j]].push_back(v[k]);
                g[v[k]].push_back(v[j]);
            }
        }
    }
    int cnow = 0;
    for (int i = 0; i < 26; i++) {
        if (color[i] == -1) {
            dfs(i, cnow);
            cnow++;
        }
    }
    map<int, int> ma; for (int i = 0; i < 26; i++) ma[i] = i;
    vector<vector<int>> colors(26);
    for (int i = 0; i < 26; i++) {
        colors[color[i]].push_back(i);
    }
    for (int i = 0; i < 26; i++) sort(colors[i].begin(), colors[i].end());
    for (int i = 0; i < 26; i++) {
        for (int j = 1; j < colors[i].size(); j++) ma[colors[i][j]] = colors[i][0];
    }
    for (int i = 0; i < s.size(); i++) {
        cout << char(ma[s[i] - 'a'] + 'a');
    }
    cout << endl;
}

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

Сообщение от Tishran

Что значит одного периода?

Смотри, есть период t. Это ознеачает, что через t символов должна быть одна и та же буква.

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

Сообщение от sveta1233

Как представить строфу,как граф?я просто никогда не работала с графами

Можите почитать на eemax или другом сайте, но чтоб не путаться лучше сначала поработать с простейшими графами

Добавлено через 1 минуту
Tishran, lolbaby, Может это уже поздно, но вы можите посмотреть мой код с моей логикой, к сожалению питона не знаю

Добавлено через 2 минуты
Gdez, к сожалению нет, это закрытый курс на степике

@Tishran · 22.10.2020, 17:06

Romiusse,

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа 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. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .

@789GoDDeM -16 / 1 / 0 Регистрация: 15.10.2020 Сообщений: 18

	Послание внеземного разума 2 20.10.2020, 00:57. Показов 5872. Ответов 19 Метки нет (Все метки) Нужна помощь, помогаю малому Профессор Персиков снова получил послание внеземного разума. Он по-прежнему считает, что доказательством этого является его периодичность. При этом период должен быть равен “константе Персикова” - числу PP. К сожалению, послание не совсем периодичное. Если сказать более точно, то оно совсем не периодичное. Однако, это никак не останавливает исследователя космических глубин. Он говорит, что некоторые сигналы были неправильно откалиброваны, отфильтрованы и интерпретированы. По-прежнему мы будем считать что все сигналы отображаются малыми буквами латинского алфавита, но в данной задаче все они распознаны и знаков вопроса нет. Тем не менее профессор, согласно своей теории, может заявить, что все вхождения такой-то буквы интерпретированы неверно и их все следует заменить на вхождения какой-то другой (одной и той же) буквы. Более строго: пусть на позициях p_{i_1}, p_{i_2}, \ldots p_{i_k}pi1,pi2,…pik и только на них в последовательности находится одна и та же буква. Профессор может выбрать любую другую букву (как встречающуюся в слове, так и не встречающуюся) и поставить её во всех этих позициях. Например в слове qqzbbacabadabaqqzbbacabadaba он может выбрать все вхождения буквы bb и заменить их на букву aa, получив слово qqzaaacaaadaaaqqzaaacaaadaaa (это считается одной заменой, независимо от числа вхождений). Очевидно, что таким образом любое послание можно сделать PP-периодическим, но профессор заинтересован сделать как можно меньше таких замен. При этом он хочет получить лексикографически минимальное послание. Формат входных данных В первой строке содержится число PP — константа Персикова (1 \leq P \leq 10^5 1≤ P≤105 ). В следующей строке содержится непустая последовательность, состоящая из малых букв латиницы. Длина этой строки не превосходит 2*10^22∗102. Формат выходных данных Вывести строку, которая получается из исходной путем минимального числа операций замены вхождений всех букв одного вида на вхождения какой-то (одной и той же) другой буквы. Итоговая строка должна быть PP-периодической, то есть любые две её буквы, расстояние между которыми кратно PP должны совпадать. Среди всех таких строк вывести лексикографически минимальную (первую в алфавитном порядке). Sample Input: 4 qqzbbacabadaba Sample Output: aacaaacaaacaaa 0

@789GoDDeM -16 / 1 / 0 Регистрация: 15.10.2020 Сообщений: 18
	20.10.2020, 01:23 [ТС]
	Надеюсь теперь все верно Профессор Персиков снова получил послание внеземного разума. Он по-прежнему считает, что доказательством этого является его периодичность. При этом период должен быть равен “константе Персикова” - числу PP. К сожалению, послание не совсем периодичное. Если сказать более точно, то оно совсем не периодичное. Однако, это никак не останавливает исследователя космических глубин. Он говорит, что некоторые сигналы были неправильно откалиброваны, отфильтрованы и интерпретированы. По-прежнему мы будем считать что все сигналы отображаются малыми буквами латинского алфавита, но в данной задаче все они распознаны и знаков вопроса нет. Тем не менее профессор, согласно своей теории, может заявить, что все вхождения такой-то буквы интерпретированы неверно и их все следует заменить на вхождения какой-то другой (одной и той же) буквы. Более строго: пусть на позициях p_i1, p_i2, ... p_in и только на них в последовательности находится одна и та же буква. Профессор может выбрать любую другую букву (как встречающуюся в слове, так и не встречающуюся) и поставить её во всех этих позициях. Например в слове qqzbbacabadabaqqzbbacabadaba он может выбрать все вхождения буквы bb и заменить их на букву aa, получив слово qqzaaacaaadaaaqqzaaacaaadaaa (это считается одной заменой, независимо от числа вхождений). Очевидно, что таким образом любое послание можно сделать PP-периодическим, но профессор заинтересован сделать как можно меньше таких замен. При этом он хочет получить лексикографически минимальное послание. Формат входных данных В первой строке содержится число P — константа Персикова (1 ≤ P≤10⁵ ). В следующей строке содержится непустая последовательность, состоящая из малых букв латиницы. Длина этой строки не превосходит 2*10². Формат выходных данных Вывести строку, которая получается из исходной путем минимального числа операций замены вхождений всех букв одного вида на вхождения какой-то (одной и той же) другой буквы. Итоговая строка должна быть PP-периодической, то есть любые две её буквы, расстояние между которыми кратно PP должны совпадать. Среди всех таких строк вывести лексикографически минимальную (первую в алфавитном порядке). Sample Input: 4 qqzbbacabadaba Sample Output: aacaaacaaacaaa 0

@Romiusse 20 / 19 / 2 Регистрация: 19.06.2019 Сообщений: 45
	20.10.2020, 20:51
	Крч. 1)представляем строку как граф, где вершины буквы. Вершины будут соединятся, если буквы зависят друг от друга, т.е если они одного периода. 2) находим компоненты связанности графа. 3) В каждой компоненте найдем наименьшую букву и заменем ей все буквы, которые есть в этой компоненте. 4) Выведем ответ. (Это полное решение с ограничениями n<= 10^5) 2

@789GoDDeM -16 / 1 / 0 Регистрация: 15.10.2020 Сообщений: 18
	20.10.2020, 22:07 [ТС]
	Можете пожалуйста написать это кодом 0

@Tishran 0 / 0 / 0 Регистрация: 09.06.2020 Сообщений: 18
	21.10.2020, 14:12
	lolbaby, но как это сделать, логика Romiusse выше не работает получается? 0

@lolbaby 0 / 0 / 0 Регистрация: 21.10.2020 Сообщений: 5
	21.10.2020, 15:02
	В некоторых случаях решения правильно обрабатывают строку, вообщем не всегда ваши программы делают лишнюю замену 0

@DarkSwwwan 3 / 3 / 0 Регистрация: 19.10.2020 Сообщений: 11
	21.10.2020, 15:20
	Хз, у меня всё работает, но медленно(я dfs криво написал) 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	21.10.2020, 19:30
	DarkSwwwan, сервис тестировщика доступен? 0

@Tishran 0 / 0 / 0 Регистрация: 09.06.2020 Сообщений: 18
	22.10.2020, 17:06
	Romiusse, 0