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

@salvator19 · Регистрация: 28.03.2014

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

У Максима есть слово 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

@John Prick · 11.07.2014, 13:52

C++

/*
У Максима есть слово 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;
            *curr1 = *curr2;
            ++curr1;
            ++curr2;
        }
    }
 
    std::cout << "\nResult: ";
    if (n <= k)
    {
        std::reverse(second_part.begin(), second_part.end());
        std::cout << first_part << second_part;
    } else
        std::cout << "NO";
    std::cout << std::endl;
 
    system("pause");
    return 0;
}

@SlavaSSU · 11.07.2014, 14:11

John Prick, неправильно работает. я ввел ему abc 2, ответ aaa, у тебя вывел cbc.

@John Prick · 11.07.2014, 14:22

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

я ввел ему abc 2, ответ aaa, у тебя вывел cbc.

Почему ответ именно aaa, а не, к примеру, aba , ccc или bbb?

Добавлено через 6 минут
Воткнул. Забыл про лексографическую минимальность.
Тогда пара исправлений:

C++

/*
У Максима есть слово 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;
        }
    }
 
    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;
}

@SlavaSSU · 11.07.2014, 14:26

John Prick, неправильно на тесте bbbb 3(Ответ видимо abba, у тя выводит bbbb)
да и на тесте bbbb 4 утя выводит bbbb хотя должен aaaa

@John Prick · 11.07.2014, 14:36

SlavaSSU, ну тогда доработай сам.

Добавлено через 1 минуту
Надо просто добавить ещё один цикл на оставшееся число замен и менять символы в первой и второй на 'a'.

Добавлено через 1 минуту
Ладно, сам сделаю.

C++

/*
У Максима есть слово 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)
    {
        *curr1++ = 'a';
        *curr2++ = 'a';
        ++n;
    }
 
    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;
}

@salvator19 · 11.07.2014, 14:38 **[ТС]**

John Prick, SlavaSSU, Спасибо.

@John Prick · 11.07.2014, 14:40

salvator19, погоди, посл.вариант нерабочий.

@salvator19 · 11.07.2014, 14:41 **[ТС]**

John Prick, уже вижу)

@John Prick · 11.07.2014, 14:41

Вот рабочий вариант:

C++

/*
У Максима есть слово 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;
}

@SlavaSSU · 11.07.2014, 14:44

John Prick, ЛОЛ. на тесте bbbb 3 выводит aaaa(т.е. он сделал 4 замены)

ладно щас погоди я попробую написать и тогда ты уже будешь заваливать меня тестами!)

@John Prick · 11.07.2014, 14:45

Теперь, вроде правильно работает.

Добавлено через 17 секунд
SlavaSSU, я исправил это.

@salvator19 · 11.07.2014, 14:50 **[ТС]**

John Prick, Большое спасибо!

Добавлено через 3 минуты
John Prick, не проходит еще один тест) не хватает чего то еще

@SlavaSSU · 11.07.2014, 14:52

salvator19, попробуй пошли мой код.

C++ (Qt)

#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
 
char a[111111];
bool used[111111];
 
int main()
{
    string s;
    getline(cin, s);
    int n = s.length();
    int k;
    cin >> k;
    for(int i = 0; i < n; i++)
        a[i + 1] = s[i];
 
    for(int i = 1; i <= n / 2; i++)
    {
        if(a[i] != a[n - i + 1])
        {
            char mn = min(a[i], a[n - i + 1]);
            a[i] = a[n - i + 1] = mn;
            used[i] = used[n - i + 1] = true;
            k--;
        }
    }
 
    if(k < 0)
    {
        cout << "NO" << endl;
        return 0;
    }
 
    for(int i = 1; i <= n / 2; i++)
    {
        if(a[i] > 'a')
        {
            if(!used[i])
            {
                if(k >= 2)
                {
                    k -= 2;
                    a[i] = a[n - i + 1] = 'a';
                }
            }
            else
            {
                if(k >= 1)
                {
                    k--;
                    a[i] = a[n - i + 1] = 'a';
                }
            }
        }
    }
 
    if(n % 2 == 1)
    {
        if(a[(n / 2) + 1] != 'a' && k > 0)
        {
            k--;
            a[(n / 2) + 1] = 'a';
        }
    }
 
    string ans;
    ans.erase();
    for(int i = 1; i <= n; i++)
        ans += a[i];
 
    cout << ans << endl;
    return 0;
}

@John Prick · 11.07.2014, 14:56

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

не проходит еще один тест

Какой?

@salvator19 · 11.07.2014, 14:56 **[ТС]**

SlavaSSU, твой прошел! Спасибо

Добавлено через 29 секунд
John Prick, там дальше не видно тестов. но походу этот bbbb 3

@SlavaSSU · 11.07.2014, 14:58

salvator19, а что за сайт кстати?

@John Prick · 11.07.2014, 14:58

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

там дальше не видно тестов. но походу этот bbbb 3

Выдаёт abba. А какой должен быть ответ?

@SlavaSSU · 11.07.2014, 15:00

John Prick, ответ abba да. Кто вам сказал, что решение падает именно на этом тесте?

@salvator19 · 11.07.2014, 15:01 **[ТС]**

John Prick, вводим bbbb и 3 замены. Он делал 4 замены aaaa

@John Prick 2277 / 1768 / 741 Регистрация: 27.07.2012 Сообщений: 5,251
	11.07.2014, 14:45	12
	Теперь, вроде правильно работает. Добавлено через 17 секунд SlavaSSU, я исправил это. 0

@salvator19 1 / 1 / 1 Регистрация: 28.03.2014 Сообщений: 58
	11.07.2014, 14:56 [ТС]	16
	SlavaSSU, твой прошел! Спасибо Добавлено через 29 секунд John Prick, там дальше не видно тестов. но походу этот bbbb 3 0

@John Prick 2277 / 1768 / 741 Регистрация: 27.07.2012 Сообщений: 5,251
	11.07.2014, 14:58	18
	Сообщение от salvator19 там дальше не видно тестов. но походу этот bbbb 3 Выдаёт abba. А какой должен быть ответ? 0

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

Решение

Решение

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	11.07.2014, 14:11	3
	John Prick, неправильно работает. я ввел ему abc 2, ответ aaa, у тебя вывел cbc. 1

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	11.07.2014, 14:26	5
	Сообщение было отмечено salvator19 как решение Решение John Prick, неправильно на тесте bbbb 3(Ответ видимо abba, у тя выводит bbbb) да и на тесте bbbb 4 утя выводит bbbb хотя должен aaaa 1

@salvator19 1 / 1 / 1 Регистрация: 28.03.2014 Сообщений: 58
	11.07.2014, 14:38 [ТС]	7
	John Prick, SlavaSSU, Спасибо. 0

@John Prick 2277 / 1768 / 741 Регистрация: 27.07.2012 Сообщений: 5,251
	11.07.2014, 14:40	8
	salvator19, погоди, посл.вариант нерабочий. 0

@salvator19 1 / 1 / 1 Регистрация: 28.03.2014 Сообщений: 58
	11.07.2014, 14:41 [ТС]	9
	John Prick, уже вижу) 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	11.07.2014, 14:44	11
	John Prick, ЛОЛ. на тесте bbbb 3 выводит aaaa(т.е. он сделал 4 замены) ладно щас погоди я попробую написать и тогда ты уже будешь заваливать меня тестами!) 0

@salvator19 1 / 1 / 1 Регистрация: 28.03.2014 Сообщений: 58
	11.07.2014, 14:50 [ТС]	13
	John Prick, Большое спасибо! Добавлено через 3 минуты John Prick, не проходит еще один тест) не хватает чего то еще 0

@John Prick 2277 / 1768 / 741 Регистрация: 27.07.2012 Сообщений: 5,251
	11.07.2014, 14:56	15
	Сообщение от salvator19 не проходит еще один тест Какой? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	11.07.2014, 14:58	17
	salvator19, а что за сайт кстати? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	11.07.2014, 15:00	19
	John Prick, ответ abba да. Кто вам сказал, что решение падает именно на этом тесте? 0

@salvator19 1 / 1 / 1 Регистрация: 28.03.2014 Сообщений: 58
	11.07.2014, 15:01 [ТС]	20
	John Prick, вводим bbbb и 3 замены. Он делал 4 замены aaaa 0