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

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

Восстановить пароль Регистрация
 
Tenday
0 / 0 / 0
Регистрация: 19.10.2015
Сообщений: 12
20.10.2016, 14:59     Либо удваивая одиночные, либо заменяя сдвоенные одним символом, привести строку к заданному виду #1
Помогите решить эту задачу, я написал решение, но оно получилось огромным (73 строчки), непонятным и страшным. Это пятая задача из муниципального этапа олимпиады, она не должна быть очень сложной:

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

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

C++ Сжать строку, заменяя несколько подряд стоящих пробелов одним
Никак не могу найти ошибку, должен сосздать матрицу либо из звездочеку либо из пробелов C++
Вывести в алфавитном порядке слова, которые присутствуют либо в первой строке, либо во второй, но не в обеих сразу. C++
Найти либо максимум, либо минимум для трех задаваемых чисел C++
Проверка открытия файла либо работает, либо уходит в бесконечность C++
C++ При потсроении пишет что конструктор либо недоступен либо объявлен как explicit
Сделать либо так, чтобы в файл записывались рандомные матрица и вектор, либо из файла считывать C++
C++ Можно ли передать в функцию либо вектор, либо список, если да, то как?

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Invader0x7F
Helper C/C++
 Аватар для Invader0x7F
264 / 141 / 56
Регистрация: 22.09.2016
Сообщений: 478
Завершенные тесты: 4
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 пропорциональная. Это один из возможных вариантов решения (не оптимизированный). Пробуйте.
Миниатюры
Либо удваивая одиночные, либо заменяя сдвоенные одним символом, привести строку к заданному виду  
Tenday
0 / 0 / 0
Регистрация: 19.10.2015
Сообщений: 12
20.10.2016, 16:39  [ТС]     Либо удваивая одиночные, либо заменяя сдвоенные одним символом, привести строку к заданному виду #3
Спасибо, попробую разобраться в Вашем решении
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
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;
}
Tenday
0 / 0 / 0
Регистрация: 19.10.2015
Сообщений: 12
21.10.2016, 14:28  [ТС]     Либо удваивая одиночные, либо заменяя сдвоенные одним символом, привести строку к заданному виду #5
Интересный стиль. Многие приемы и функции в Вашем коде для меня пока еще неизвестны, но думаю будет полезно разобраться в нем. Только у меня не компилируется в 97 строке, пишет "it does not name a type"
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
21.10.2016, 15:26     Либо удваивая одиночные, либо заменяя сдвоенные одним символом, привести строку к заданному виду #6
Цитата Сообщение от Tenday Посмотреть сообщение
Только у меня не компилируется в 97 строке, пишет "it does not name a type"
Не знаю, у меня нормально компилируется. А С++11 подключили?
Yandex
Объявления
21.10.2016, 15:26     Либо удваивая одиночные, либо заменяя сдвоенные одним символом, привести строку к заданному виду
Ответ Создать тему
Опции темы

Текущее время: 03:20. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru