Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
salvator19
1 / 1 / 0
Регистрация: 28.03.2014
Сообщений: 55
#1

Найти лексикографически минимальный палиндром, который можно получить из слова S - C++

11.07.2014, 13:31. Просмотров 1215. Ответов 27
Метки нет (Все метки)

У Максима есть слово S, и он очень хочет сделать из него палиндром, но не желает изменять слишлом большое количество символов. Помогите Максиму найти лексикографически минимальный палиндром, который можно получить из слова S заменой не более чем K символов.
Строка A лексикографически меньше строки B, если существует такой индекс j, что A[j] < B[j] и ∀i < j A[i] = B[i]

Входные данные:
Первая строка содержит слово S, состоящее из строчных латинских букв и имеющее длину не более 10^5 символов.
Вторая строка содержит целое число K (0 <= K <= 10^5) — максимально возможное количество замен.

Выходные данные:
В единственной строке выведите ответ на задачу. Если сформировать палиндром невозможно, выведите NO.

Пример: Входные данные: ozoxo
1
Выходные данные:oxoxo
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.07.2014, 13:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти лексикографически минимальный палиндром, который можно получить из слова S (C++):

Дан одномерный целочисленный массив. Определить, можно ли получить из данной последовательности симметричную (палиндром) путем перестановки в исходной - C++
Помогите написать код к данной задаче, пожалуйста Дан одномерный целочисленный массив. Определить, можно ли получить из данной...

Минимальный палиндром на с++ - C++

Можно ли из слова А получить слово Б - C++
Нужно проверить можно ли из слова А получить слово Б. #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;string&gt; using namespace...

Найти в файле все слова, которые можно сложить из букв заданного слова - C++
Дано слово р и файл f.найти в файле f все слова которые можна сложить с букв слова р.

Найти минимальный элемент первой последовательности, который не входит во вторую последовательность - C++
даны две последовательности по 30 целых чисел в каждой. Найти наименьшее среди тех чисел 1-ой последовательности, которые не входят во...

Найти минимальный элемент в динамическом массиве, который будет выше главной диагонали. - C++
Нужно найти минимальный элемент в динамическом массиве который будет выше главной диагонали. Получается что-то не то(( может проблема в...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
salvator19
1 / 1 / 0
Регистрация: 28.03.2014
Сообщений: 55
11.07.2014, 14:56  [ТС] #16
SlavaSSU, твой прошел! Спасибо

Добавлено через 29 секунд
John Prick, там дальше не видно тестов. но походу этот bbbb 3
0
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
11.07.2014, 14:58 #17
salvator19, а что за сайт кстати?
0
John Prick
801 / 734 / 145
Регистрация: 27.07.2012
Сообщений: 2,107
Завершенные тесты: 3
11.07.2014, 14:58 #18
Цитата Сообщение от salvator19 Посмотреть сообщение
там дальше не видно тестов. но походу этот bbbb 3
Выдаёт abba. А какой должен быть ответ?
0
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
11.07.2014, 15:00 #19
John Prick, ответ abba да. Кто вам сказал, что решение падает именно на этом тесте?
0
salvator19
1 / 1 / 0
Регистрация: 28.03.2014
Сообщений: 55
11.07.2014, 15:01  [ТС] #20
John Prick, вводим bbbb и 3 замены. Он делал 4 замены aaaa
0
John Prick
801 / 734 / 145
Регистрация: 27.07.2012
Сообщений: 2,107
Завершенные тесты: 3
11.07.2014, 15:02 #21
SlavaSSU, топик-стартер. Как бы в этой теме только нас трое.

Добавлено через 1 минуту
salvator19, возьмите ещё раз последнюю версию моего кода.
C++
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
72
73
74
75
76
77
/*
У Максима есть слово S, и он очень хочет сделать из него палиндром, 
но не желает изменять слишлом большое количество символов.
Помогите Максиму найти лексикографически минимальный палиндром,
который можно получить из слова S заменой не более чем K символов.
Строка A лексикографически меньше строки B, если существует такой
индекс j, что A[j] < B[j] и i < j A[i] = B[i]
 
Входные данные:
Первая строка содержит слово S, состоящее из строчных латинских букв и имеющее длину не более 10^5 символов.
Вторая строка содержит целое число K (0 <= K <= 10^5) — максимально возможное количество замен.
 
Выходные данные:
В единственной строке выведите ответ на задачу. Если сформировать палиндром невозможно, выведите NO.
*/
 
#include <iostream>
#include <algorithm>
#include <string>
 
int main(void)
{
    std::string input;
    int k;
    std::cout << "Enter String: ";
    std::cin >> input;
    std::cout << "Enter Number Of Substitutions: ";
    std::cin >> k;
 
    std::string first_part(input.begin(), input.begin() + input.size() / 2);
    std::string second_part(input.begin() + input.size() / 2, input.end());
    std::reverse(second_part.begin(), second_part.end());
 
    int n = 0;
    std::string::iterator curr1 = first_part.begin();
    std::string::iterator curr2 = second_part.begin();
    while (curr1 != first_part.end())
    {
        std::pair<std::string::iterator, std::string::iterator> curr =
            std::mismatch(curr1, first_part.end(), curr2);
        curr1 = curr.first;
        curr2 = curr.second;
        if (curr1 != first_part.end())
        {
            ++n;
            if (*curr1 < *curr2)
                *curr2 = *curr1;
            else
                *curr1 = *curr2;
            ++curr1;
            ++curr2;
        }
    }
 
    curr1 = first_part.begin();
    curr2 = second_part.begin();
    while ((n < k - 1) && (curr1 != first_part.end()))
    {
        *curr1++ = 'a';
        *curr2++ = 'a';
        n += 2;
    }
 
    std::cout << "\nResult: ";
    if (n <= k)
    {
        std::reverse(second_part.begin(), second_part.end());
        if ((n < k) && (first_part.size() != second_part.size()))
            second_part[0] = 'a';
        std::cout << first_part << second_part;
    } else
        std::cout << "NO";
    std::cout << std::endl;
 
    system("pause");
    return 0;
}
0
salvator19
1 / 1 / 0
Регистрация: 28.03.2014
Сообщений: 55
11.07.2014, 15:04  [ТС] #22
John Prick, работает тоже
0
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
11.07.2014, 15:04 #23
John Prick, как бы в проверяющих системах обычно нельзя смотреть тесты, это был риторический вопрос!
вот ща потестил и нашел тест:
abcddcba
4
ответ
aaaddaaa
твой ответ
aacddcaa

и таких тестов куча...
0
salvator19
1 / 1 / 0
Регистрация: 28.03.2014
Сообщений: 55
11.07.2014, 15:05  [ТС] #24
SlavaSSU, John Prick, хотите еще порешать задачки))) Попробуйте вникнуть в логику шпионов и рассекретить их переписку. Панграмма
0
John Prick
801 / 734 / 145
Регистрация: 27.07.2012
Сообщений: 2,107
Завершенные тесты: 3
11.07.2014, 15:29 #25
Цитата Сообщение от SlavaSSU Посмотреть сообщение
вот ща потестил и нашел тест:
abcddcba
4
ответ
aaaddaaa
твой ответ
aacddcaa
C++
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
72
73
74
75
76
77
78
79
80
81
82
83
/*
У Максима есть слово S, и он очень хочет сделать из него палиндром, 
но не желает изменять слишлом большое количество символов.
Помогите Максиму найти лексикографически минимальный палиндром,
который можно получить из слова S заменой не более чем K символов.
Строка A лексикографически меньше строки B, если существует такой
индекс j, что A[j] < B[j] и i < j A[i] = B[i]
 
Входные данные:
Первая строка содержит слово S, состоящее из строчных латинских букв и имеющее длину не более 10^5 символов.
Вторая строка содержит целое число K (0 <= K <= 10^5) — максимально возможное количество замен.
 
Выходные данные:
В единственной строке выведите ответ на задачу. Если сформировать палиндром невозможно, выведите NO.
*/
 
#include <iostream>
#include <algorithm>
#include <string>
 
int main(void)
{
    std::string input;
    int k;
    std::cout << "Enter String: ";
    std::cin >> input;
    std::cout << "Enter Number Of Substitutions: ";
    std::cin >> k;
    std::cout << "\nResult: ";
 
    std::string first_part(input.begin(), input.begin() + input.size() / 2);
    std::string second_part(input.begin() + input.size() / 2, input.end());
    std::reverse(second_part.begin(), second_part.end());
 
    int n = 0;
    std::string::iterator curr1 = first_part.begin();
    std::string::iterator curr2 = second_part.begin();
    while (curr1 != first_part.end())
    {
        std::pair<std::string::iterator, std::string::iterator> curr =
            std::mismatch(curr1, first_part.end(), curr2);
        curr1 = curr.first;
        curr2 = curr.second;
        if (curr1 != first_part.end())
        {
            ++n;
            if (*curr1 < *curr2)
                *curr2 = *curr1;
            else
                *curr1 = *curr2;
            ++curr1;
            ++curr2;
        }
    }
 
    if (n > k)
        std::cout << "NO";
    else
    {
        curr1 = first_part.begin();
        curr2 = second_part.begin();
        while ((n < k - 1) && (curr1 != first_part.end()))
        {
            if (*curr1 != 'a')
            {
                *curr1 = 'a';
                *curr2 = 'a';
                n += 2;
            }
            ++curr1;
            ++curr2;
        }
 
        std::reverse(second_part.begin(), second_part.end());
        if ((n < k) && (first_part.size() != second_part.size()))
            second_part[0] = 'a';
        std::cout << first_part << second_part;
    }
    std::cout << std::endl;
 
    system("pause");
    return 0;
}
Цитата Сообщение от SlavaSSU Посмотреть сообщение
и таких тестов куча...
Так вот проверить бы все. Мне просто в голову особо не приходят разные варианты.
0
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
11.07.2014, 15:32 #26
John Prick, dcbc 4(ответ aaaa, твой ответ abba) xD
0
John Prick
801 / 734 / 145
Регистрация: 27.07.2012
Сообщений: 2,107
Завершенные тесты: 3
11.07.2014, 15:47 #27
Ясно. Алгоритм должен быть другим. Просто изначально стал поправлять имеющийся алгоритм под лексикографический минимум.
0
Trwsdf
Заблокирован
11.07.2014, 16:30 #28
C++
1
2
3
4
5
6
 string init;
    cin>>init;
    int k = (cin>>k, k), j = 0;
    for (int i = init.size() - 1; i >= std::round(init.size() / 2) && j <= k; i--)
        if (init[i] != init[init.size() - 1 - i]) init[init.size() - 1 - i] = init[j++, i];
    cout << ((j > k) ? "NO" : init);
Добавлено через 38 секунд
Цитата Сообщение от salvator19 Посмотреть сообщение
хочет сделать из него палиндром
Получается, изначально - не полиндром. Для тех кто забывает условие задания.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.07.2014, 16:30
Привет! Вот еще темы с ответами:

Определить, можно ли из букв первого слова получить второе - C++
Даны два слова. Определить, можно ли из букв первого из них получить второе. повторяющиеся буквы второго слова могут в первом слове не...

Проверьте, можно ли вычеркиванием букв из одного слова получить другое - C++
Нужна помощь,заранее спасибо!!! Проверьте, можно ли вычеркиванием букв из одного слова получить другое.

Имеются слова доноры (из монитор можно получить мотор, рот, тир ) - C++
Имеются слова доноры (из монитор можно получить мотор, рот, тир ). Определить слова, полученных из введенного донора. Подскажите...

В матрице найти минимальный элемент. Получить матрицу порядка n+1 - C++
В заданной действительной квадратной матрице порядка n найти минимальный элемент. Получить матрицу порядка n + 1 путем добавления к каждой...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
11.07.2014, 16:30
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru