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

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

Восстановить пароль Регистрация
 
Максим3456
0 / 0 / 0
Регистрация: 21.03.2016
Сообщений: 8
29.07.2016, 15:25     Палиндром. Почему WA1? #1
Одно из известных развлечений со словами - составление палиндромов. Палиндромом называется предложение, которое, после удаления из него всех пробелов и знаков препинания, читается одинаково справа налево и слева направо. Создатели одного известного текстового редактора пишут новую версию модуля для проверки орфографии. Они хотят реализовать возможность вывода подсказки для пользователя на тот случай, если он допустил опечатку при наборе какого-нибудь палиндрома. Конечно же, они решили обратиться именно к вам.

Более точно, по заданной строке нужно определить, может ли она быть результатом замены, удаления или добавления одного символа в некотором палиндроме. При этом строчные и прописные латинские буквы не различаются, а все остальные символы должны игнорироваться.

Входные данные

Во входном файле 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.

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
#include <iostream>
#include <cstdlib>
#include <string>
#include <cstdlib>
using namespace std;
string k;
string obr(string s)
{
  long long int i=0;
  while(s.length()!=i)
   {
    s[i]=tolower(s[i]);
    if(s[i]<'a' || s[i]>'z') 
    {
      s.erase(i,1);
    }
      else i++;
   }
   return s;
}
 
int pal(string s)
{
  long long int i=0,y=1,x;
  x=s.length();
  while((i<x/2) && (y==1))
  {
    if(s[i]!=s[x-i-1]) y=0;
    i++;
  }
  return y;
}
 
int zam(string s)
{
   string t;
   long long int i,x,y=0;
   x=s.length();
   t=s;
   for(i=0;i<x/2;i++)
    {
      s[i]=s[x-1-i];
      if(pal(s)==1) {y=1; k=s; break;}
      s=t;
    }
  return y;
}
 
int vir(string s)
{
    long long int i,x;
    int y=0;
    x=s.length();
    string t;
    t=s;
    for(i=0;i<s.length();i++)
   {
    s.erase(i,1);
    if(pal(s)==1) {y=1; k=s; break;}
    s=t;
    }
return y;
}
int main() {
  
  string s;
  getline(cin,s);
  s=obr(s);
   if(s.length()==0)
   {
    cout<<"NO";
   }
   else if(s.length()==1) 
  { cout<<"YES"<<endl;
    cout<<s;
  }
  else if(zam(s)==1) 
  { cout<<"YES"<<endl;
    cout<<k;
  }
  else if(vir(s)==1) 
   { cout<<"YES"<<endl;
    cout<<k;
  }
  else cout<<"NO";
 
    system("pause");
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2016, 15:25     Палиндром. Почему WA1?
Посмотрите здесь:

Палиндром... C++
C++ Палиндром.
C++ Палиндром
C++ Палиндром
Палиндром в С++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TheBig
-20 / 0 / 0
Регистрация: 28.07.2016
Сообщений: 41
29.07.2016, 16:05     Палиндром. Почему WA1? #2
Цитата Сообщение от Максим3456 Посмотреть сообщение
long long int i
Есть тип данных long, есть int, есть long long. А что такое long long int?
HighPredator
 Аватар для HighPredator
5349 / 1732 / 320
Регистрация: 10.12.2010
Сообщений: 5,119
Записей в блоге: 3
29.07.2016, 16:17     Палиндром. Почему WA1? #3
Максим3456, это конечно хорошо и замечательно что вы освоили ctrl+c и ctrl+v, но суть вопроса-то в чем?
Максим3456
0 / 0 / 0
Регистрация: 21.03.2016
Сообщений: 8
29.07.2016, 17:37  [ТС]     Палиндром. Почему WA1? #4
У меня на acmp WA1. А тесты все мои проходит. Не знаю, в чем ошибка
TheBig
-20 / 0 / 0
Регистрация: 28.07.2016
Сообщений: 41
29.07.2016, 17:39     Палиндром. Почему WA1? #5
В программе ошибка.
Максим3456
0 / 0 / 0
Регистрация: 21.03.2016
Сообщений: 8
29.07.2016, 17:41  [ТС]     Палиндром. Почему WA1? #6
Я исправил на long long. Все равно WA1
TheBig
-20 / 0 / 0
Регистрация: 28.07.2016
Сообщений: 41
29.07.2016, 17:42     Палиндром. Почему WA1? #7
WA1 это плохо.
Mr.X
Эксперт С++
 Аватар для Mr.X
2802 / 1578 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
31.07.2016, 15:42     Палиндром. Почему WA1? #8
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;
    }
}
pav1uxa
31.07.2016, 17:12
  #9

Не по теме:

Mr.X, этот код Вы писали? Как называется стиль такого написания кода (оформление кода)? Где-то можно почитать?

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2016, 17:51     Палиндром. Почему WA1?
Еще ссылки по теме:

C++ Палиндром
C++ Палиндром 2 С++

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

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
 Аватар для Mr.X
2802 / 1578 / 247
Регистрация: 03.05.2010
Сообщений: 3,666
31.07.2016, 17:51     Палиндром. Почему WA1? #10
Цитата Сообщение от pav1uxa Посмотреть сообщение
Как называется стиль такого написания кода (оформление кода)?
Ну, особого названия я не придумывал. Можно назвать стилем ленивого читателя, которому лень при чтении пересчитывать скобки и парсером работать.
Цитата Сообщение от pav1uxa Посмотреть сообщение
Где-то можно почитать?
Вот неплохие книжки.
Yandex
Объявления
31.07.2016, 17:51     Палиндром. Почему WA1?
Ответ Создать тему
Опции темы

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