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

Палиндром. Почему WA1? - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Storage durations http://www.cyberforum.ru/cpp-beginners/thread1787259.html
Страшно обилие реализаций абстракции и правил их применения :) Лямбды, насколько я помню - это объекты (анонимные функтоуры?), создаются без нью, живут на стеке, делита не требуют... Или я все спутал...
C++ Множественное наследование Доброго времени суток. Есть ряд операций. Логически операции делятся на группы ( к примеру, запрос, ответ, чтение из буфера и .п.). В зависимости от группы, появляется специализация ( у всех... http://www.cyberforum.ru/cpp-beginners/thread1787242.html
Полицейские-рекруты C++
Недавно в вашем городе открылось отделение полиции. Сейчас идет набор кадров для работы в новом отделении. А тем временем, преступления все совершаются в городе. Достоверно известно, что один...
Найти число, не входящее в заданную последовательность натуральных чисел C++
Прошу помочь решить. Задано число N и последовательность из N-1 натуральных чисел. Все числа лежат в диапазоне и не повторяются. Это означает, что существует единственное число из , которого нет...
C++ Вывести результат последовательного применения циклического сдвига вправо заданной последовательности k раз http://www.cyberforum.ru/cpp-beginners/thread1787232.html
Циклическим сдвигом вправо последовательности называется последовательность, получаемая из исходной перемещением последнего элемента в начало. Заданы числа N и k и последовательность целых чисел...
C++ Распечатать все индексы вхождения числа х в последовательность а, начиная с последнего Задана длина N последовательности целых чисел a и сама последовательность. После этого задается некоторое число х. Распечатать все индексы вхождения числа х в последовательность а, начиная с... подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
31.07.2016, 15:42
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
219
220
221
///////////////////////////////////////////////////////////////////////////////
//3.
///////////////////////////////////////////////////////////////////////////////
//Палиндром
//(Время: 1 сек. Память: 16 Мб Сложность: 41%)
 
//Одно из известных развлечений со словами - составление палиндромов.
//Палиндромом называется предложение, которое, после удаления из него всех
//пробелов и знаков препинания, читается одинаково справа налево и слева
//направо. Создатели одного известного текстового редактора пишут новую
//версию модуля для проверки орфографии. Они хотят реализовать возможность
//вывода подсказки для пользователя на тот случай, если он допустил опечатку
//при наборе какого-нибудь палиндрома. Конечно же, они решили обратиться
//именно к вам.
 
//Более точно, по заданной строке нужно определить, может ли она быть
//результатом замены, удаления или добавления одного символа в некотором
//палиндроме. При этом строчные и прописные латинские буквы не различаются,
//а все остальные символы должны игнорироваться.
 
//Входные данные
 
//Во входном файле INPUT.TXT содержится заданная строка. Гарантируется,
//что она содержит хотя бы одну букву. Длина строки не превосходит 105.
 
//Выходные данные
 
//В первой строке выходного файла OUTPUT.TXT выведите YES, если строка
//может быть получена каким-нибудь из описанных выше преобразований
//из некоторого палиндрома, и NO в противном случае. В случае положительного
//ответа во второй строке выведите какой-нибудь из палиндромов, в которых мог
//допустить опечатку пользователь.
 
//Примеры
//№ INPUT.TXT                               OUTPUT.TXT
//1 Never odd or even                       YES
//                                          NeVErODDoREVen
 
//2 Eat it!                                 NO
 
//3 Mums are not set as a test on Erasmus.  YES
//                                          Sums are not set as a test on Erasmus.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <iterator>
#include <locale>
#include <string>
///////////////////////////////////////////////////////////////////////////////
typedef std::string         T_str;
typedef T_str::size_type    T_pos;
///////////////////////////////////////////////////////////////////////////////
bool    is_palindrom( T_str const   &   s )
{
    return  std::equal
                (
                    s.begin     (),
                    s.end       (),
                    s.rbegin    ()
                );
}
///////////////////////////////////////////////////////////////////////////////
void    trim_str( T_str    &   s )
{
    T_str   res;
 
    std::copy_if
        (
            s.begin             (),
            s.end               (),
            std::back_inserter  ( res ),
 
            []                  ( char  symb )
            {
                return  std::isalpha
                            (
                                symb,
                                std::locale("C")
                            );
            }
        );
 
    std::swap( s, res );
 
    for( auto   &   symb    :   s )
    {
        symb    =   std::tolower( symb );
    }
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_replace_symb
    (
        T_str   const   &   s,
        T_str           &   p,
        T_pos               pos,
        T_pos               last_pos
    )
{
    p           =   s;
    p[pos]      =   p[ last_pos - pos ];
    return  is_palindrom(p) ;
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_remove_front_symb
    (
        T_str   const   &   s,
        T_str           &   p,
        T_pos               pos,
        T_pos               last_pos
    )
{
    p   =   s;
    p.erase( pos, 1 );
    return  is_palindrom(p) ;
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_remove_back_symb
    (
        T_str   const   &   s,
        T_str           &   p,
        T_pos               pos,
        T_pos               last_pos
    )
{
    p   =   s;
    p.erase( last_pos - pos, 1 );
    return  is_palindrom(p) ;
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_make_palindrom
    (
        T_str   const   &   s,
        T_str           &   p,
        T_pos               pos,
        T_pos               last_pos
    )
{
    return      successfully_replace_symb
                    (
                        s,
                        p,
                        pos,
                        last_pos
                    )
 
            ||  successfully_remove_front_symb
                    (
                        s,
                        p,
                        pos,
                        last_pos
                    )
 
            ||  successfully_remove_back_symb
                    (
                        s,
                        p,
                        pos,
                        last_pos
                    );
}
///////////////////////////////////////////////////////////////////////////////
bool    successfully_set_palindrom
    (
        T_str       s,
        T_str   &   p
    )
{
    trim_str(s);
    p   =   s;
    bool    bool_res    =   is_palindrom(p);
 
    if( bool_res )
    {
        return  bool_res;
    }
 
    auto    last_pos    =   s.size() - 1;
 
    for( T_pos  pos{}; pos <= last_pos / 2; ++pos )
    {
        bool_res    =       s[ pos ]
                        ==  s[ last_pos - pos ];
 
        if( !bool_res )
        {
            return  successfully_make_palindrom
                        (
                            s,
                            p,
                            pos,
                            last_pos
                        );
        }
    }//for
 
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_str   s;
    getline( std::cin,  s );
 
    T_str   p;
 
    if  (
            successfully_set_palindrom( s, p )
        )
    {
        std::cout   <<  "YES"
                    <<  std::endl
                    <<  p
                    <<  std::endl;
    }
    else
    {
        std::cout   <<  "NO"
                    <<  std::endl;
    }
}
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru