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

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

Войти
Регистрация
Восстановить пароль
 
Tenday
0 / 0 / 0
Регистрация: 19.10.2015
Сообщений: 16
#1

Либо удваивая одиночные, либо заменяя сдвоенные одним символом, привести строку к заданному виду - C++

20.10.2016, 14:59. Просмотров 282. Ответов 5
Метки нет (Все метки)

Помогите решить эту задачу, я написал решение, но оно получилось огромным (73 строчки), непонятным и страшным. Это пятая задача из муниципального этапа олимпиады, она не должна быть очень сложной:

Даны три строки, состоящие из строчных латинских букв. С этими строками можно
производить следующие операции: либо заменить один символ строки на два таких же символа
(например, заменить символ «a» на «aa»), либо, наоборот, заменить два подряд идущих
одинаковых символа на один такой же символ.
Необходимо при помощи этих операций сделать все три строки равными какой-то другой
общей строке S либо определить, что это сделать невозможно. При этом нужно минимизировать
общее количество операций.
Программа получает на вход три строки, состоящие из строчных букв латинского алфавита.
Длина каждой строки не превышает 100 символов.
Если при помощи указанных операций возможно сделать все три строки равными, выведите
такую строку S, что суммарное число операций, необходимых для преобразования всех трёх
данных строк к строке S, будет минимальным. Если этого сделать нельзя, программа должна
вывести одно слово IMPOSSIBLE (заглавными буквами).
Примеры:
Ввод:
aaaza
aazzaa
azzza
Вывод:
aazza

Ввод:
xy
xxyy
yx
Вывод:
IMPOSSIBLE
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.10.2016, 14:59
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Либо удваивая одиночные, либо заменяя сдвоенные одним символом, привести строку к заданному виду (C++):

При изменении каких либо данных программа либо вылетает, либо просто не изменяет данные - C++
Добрый вечер. Только недавно начал заниматься С++. И вот возникли проблемы. При изменении каких либо данных. Программа либо вылетает(Qt),...

две прямые либо паралельны либо совпадают либо не существуют - C++
Д даны числа a1, b1, c1, a2, b2, c2. Напечатать координаты точки пересечения прямых, описываемых уравнениями a1x+b1y=c1 и a2x+b2y=c2, либо...

Что-то интересное. Или программа, которая принимает либо 1, либо 2 числа - C++
Программа - консольное приложение, в качестве параметров при вызове принимает одно или два целых числа. Как это реализовать на C++? Проще...

Можно ли передать в функцию либо вектор, либо список, если да, то как? - C++
Можно ли передать в функцию либо вектор, либо список, если да, то как?

Найти либо максимум, либо минимум для трех задаваемых чисел - C++
Написать программу, которая находит максимум, либо минимум для трех задаваемых чисел. Вопрос: не могу понять что за минимум и максимум...

Проверка открытия файла либо работает, либо уходит в бесконечность - C++
string A=Enterway('t');//функция ввода адреса файла fstream str(A.c_str(), ios::in ); for(;;){ if (!str){ cout << "ERROR!!! Файл...

5
Invader0x7F
Helper C/C++
281 / 158 / 61
Регистрация: 22.09.2016
Сообщений: 518
Завершенные тесты: 5
20.10.2016, 16:26 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот решил. Посмотрите:
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <conio.h>
#include <string.h>
 
#include <iostream>
 
using namespace std;
 
void get_freq(const char* str, char* pchars)
{
    for (int index = 0; str[index] != '\0'; index++)
    {
        int count = 0; char ch = str[index];
        for (int nindex = index; str[nindex] != '\0'; nindex++)
            if (str[nindex] == ch) count++;
 
        if (pchars[ch] <= 0) pchars[ch] = count;
    }
}
 
void main(void)
{
    const int N = 3;
 
    char input[N][256] = { "aaaza", "aazzaa", "azzza" };
    char output[256] = "aazza";
 
    char pchars[N + 1][256] = { { 0 } };
    get_freq(output, pchars[0]);
 
    int op_cnts[3] = { 0 };
    for (char ch = 'a'; ch <= 'z'; ch++)
    {
        int count = -1;
        if ((count = pchars[0][ch]) > 0)
        {
            for (int index = 0; index < N; index++)
            {
                get_freq(input[index], pchars[index + 1]);
                if (pchars[0][ch] < pchars[index + 1][ch])
                {
                    while (pchars[0][ch] != pchars[index + 1][ch])
                    {
                        int nindex = 0; bool found = false;
                        while (input[index][nindex] != '\0' && !found)
                            if (input[index][nindex++] == ch)
                            {
                                int t_index = nindex - 1;
                                while (input[index][t_index] != '\0')
                                {
                                    input[index][t_index] = input[index][t_index + 1];
                                    t_index++;
                                }
 
                                found = true;
                            }
 
                        pchars[index + 1][ch]--; op_cnts[index]++;
                    }
                }
 
                else if (pchars[0][ch] > pchars[index + 1][ch])
                {
                    while (pchars[0][ch] != pchars[index + 1][ch])
                    {
                        int nindex = 0;
                        while (input[index][nindex] != ch &&
                            input[index][nindex] != '\0') nindex++;
 
                        int rindex = strlen(input[index]) - 1;
                        while (rindex >= nindex)
                        {
                            input[index][rindex + 1] = input[index][rindex];
                            rindex--;
                        }
 
                        pchars[index + 1][ch]++; op_cnts[index]++;
                    }
                }       
            }
        }
    }
 
    int count = 0, min_op = -1;
    for (int index = 0; index < N; index++)
        if (strcmp(input[index], output) == 0) count++;
 
    for (int index = 0; index < N && count > 0; index++)
        if ((strcmp(input[index], output) == 0 && 
            op_cnts[index] < op_cnts[min_op]) || (min_op == -1))
        {
            min_op = index;
        }
 
    if (count <= 0) std::cout << "IMPOSSIBLE" << endl;
    else std::cout << "string = " << input[min_op] << " op_count = " << op_cnts[min_op] << endl;
 
    _getch();
}
Это пятая задача из муниципального этапа олимпиады, она не должна быть очень сложной:
Данная задача очень сложная и NP-hard пропорциональная. Это один из возможных вариантов решения (не оптимизированный). Пробуйте.
1
Миниатюры
Либо удваивая одиночные, либо заменяя сдвоенные одним символом, привести строку к заданному виду  
Tenday
0 / 0 / 0
Регистрация: 19.10.2015
Сообщений: 16
20.10.2016, 16:39  [ТС] #3
Спасибо, попробую разобраться в Вашем решении
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
21.10.2016, 14:05 #4
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
///////////////////////////////////////////////////////////////////////////////
//1.
///////////////////////////////////////////////////////////////////////////////
//Даны три строки, состоящие из строчных латинских букв. С этими строками можно
//производить следующие операции: либо заменить один символ строки на два таких же символа
//(например, заменить символ «a» на «aa»), либо, наоборот, заменить два подряд идущих
//одинаковых символа на один такой же символ.
//Необходимо при помощи этих операций сделать все три строки равными какой-то другой
//общей строке S либо определить, что это сделать невозможно. При этом нужно минимизировать
//общее количество операций.
//Программа получает на вход три строки, состоящие из строчных букв латинского алфавита.
//Длина каждой строки не превышает 100 символов.
//Если при помощи указанных операций возможно сделать все три строки равными, выведите
//такую строку S, что суммарное число операций, необходимых для преобразования всех трёх
//данных строк к строке S, будет минимальным. Если этого сделать нельзя, программа должна
//вывести одно слово IMPOSSIBLE (заглавными буквами).
//Примеры:
//Ввод:
//aaaza
//aazzaa
//azzza
//Вывод:
//aazza
 
//Ввод:
//xy
//xxyy
//yx
//Вывод:
//IMPOSSIBLE
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <set>
#include <string>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::string                     T_str;
typedef std::vector     < T_str     >   T_strings;
typedef std::multiset   < int       >   T_sizes;
///////////////////////////////////////////////////////////////////////////////
class   T_super_letter
{
    //-------------------------------------------------------------------------
    char        letter_;
    T_sizes     sizes_;
    //-------------------------------------------------------------------------
public:
    //-------------------------------------------------------------------------
    T_super_letter
        (
            char    letter,
            int     size
        )
        :
        letter_( letter )
    {
        sizes_.emplace( size );
    }
    //-------------------------------------------------------------------------
    bool    operator==  ( T_super_letter    const   &   R )                 const
    {
        return      letter_
                ==  R.letter_;
    }
    //-------------------------------------------------------------------------
    T_super_letter  &   operator+=  ( T_super_letter    const   &   R )
    {
        sizes_.insert   (
                            R.sizes_    .begin  (),
                            R.sizes_    .end    ()
                        );
 
        return  *this;
    }
    //-------------------------------------------------------------------------
    T_str   to_string()                                                     const
    {
        auto    it  =   sizes_.begin();
 
        std::advance    (
                            it,
                            sizes_.size() / 2
                        );
 
        return  T_str   (
                            *it,
                            letter_
                        );
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
typedef std::vector     < T_super_letter    >   T_super_letters;
///////////////////////////////////////////////////////////////////////////////
class   T_super_word
{
    //-------------------------------------------------------------------------
    bool                is_valid_;
    T_super_letters     super_letters_;
    //-------------------------------------------------------------------------
public:
    //-------------------------------------------------------------------------
    T_super_word    (
                        T_str   const   &   s     =   {}
                    )
        :
        is_valid_( true )
    {
        auto    it          =   s.begin();
        auto    it_next     =   s.begin();
 
        while   (
                        (
                            it_next     =   find_if
                                                (
                                                    it,
                                                    s.end(),
 
                                                    [=]  ( auto  elem )
                                                    {
                                                        return  elem    !=  *it;
                                                    }
                                                )
                        )
 
                    !=  it
                )
        {
            super_letters_.emplace_back     (
                                                T_super_letter  (
                                                                    *it,
                                                                    it_next - it
                                                                )
                                            );
 
            std::swap( it,  it_next );
        }//for
    }
    //-------------------------------------------------------------------------
    T_super_word    &   operator+=  ( T_super_word  const   &   R )
    {
        if  (
                super_letters_.empty()
            )
        {
            *this   =   R;
        }
        else
        {
            is_valid_   =       is_valid_
 
                            &&      super_letters_
                                ==  R.super_letters_;
 
            if( is_valid_ )
            {
                auto    it  =   super_letters_.begin();
 
                for( auto   const   &   sup_lett    :   R.super_letters_ )
                {
                    *it     +=  sup_lett;
                    ++it;
                }
            }//if
        }//else
 
        return  *this;
    }
    //-------------------------------------------------------------------------
    T_str   to_string()                                                     const
    {
        T_str   res;
 
        if( is_valid_ )
        {
            for( auto   const   &   sup_lett    :   super_letters_ )
            {
                res     +=  sup_lett.to_string();
            }
        }
        else
        {
            res     =   "IMPOSSIBLE";
        }
 
        return  res;
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
T_str   best_overall_line( T_strings    const   &   strings )
{
    T_super_word    res;
 
    for( auto   const   &   s   :   strings )
    {
        res     +=  T_super_word(s);
    }
 
    return  res.to_string();
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_strings   strings(3);
 
    for( auto   &   s   :   strings )
    {
        std::cin    >>  s;
    }
 
    std::cout   <<  std::endl
                <<  best_overall_line( strings )
                <<  std::endl;
}
1
Tenday
0 / 0 / 0
Регистрация: 19.10.2015
Сообщений: 16
21.10.2016, 14:28  [ТС] #5
Интересный стиль. Многие приемы и функции в Вашем коде для меня пока еще неизвестны, но думаю будет полезно разобраться в нем. Только у меня не компилируется в 97 строке, пишет "it does not name a type"
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
21.10.2016, 15:26 #6
Цитата Сообщение от Tenday Посмотреть сообщение
Только у меня не компилируется в 97 строке, пишет "it does not name a type"
Не знаю, у меня нормально компилируется. А С++11 подключили?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.10.2016, 15:26
Привет! Вот еще темы с ответами:

По условию вывести сумму либо чётных, либо нечётных разрядов заданного шестизначного числа - C++
Пользователь вводит шестизначное число. Если сумма четных разрядов больше суммы нечетных разрядов этого числа, вывести сумму четных...

Никак не могу найти ошибку, должен сосздать матрицу либо из звездочеку либо из пробелов - C++
#include &lt;iostream&gt; #include &lt;cmath&gt; #include &lt;ctime&gt; using namespace std; int main(){ char a; int zvezd,probel,b; int...

При потсроении пишет что конструктор либо недоступен либо объявлен как explicit - C++
/*Все обьекты содержимые в контейнерах без проблем выводятся через потоковые итераторы и алгоритм copy. Но когда речь идет о собственных...

Сделать либо так, чтобы в файл записывались рандомные матрица и вектор, либо из файла считывать - C++
ребят есть вот прога, она заполняет рандомами матрицу и вектор и перемножает. И есть соответственно проги для чтения из файла или записи в...


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

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

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