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

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

Войти
Регистрация
Восстановить пароль
 
Максим3456
0 / 0 / 0
Регистрация: 21.03.2016
Сообщений: 8
#1

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

29.07.2016, 15:25. Просмотров 355. Ответов 9
Метки нет (Все метки)

Одно из известных развлечений со словами - составление палиндромов. Палиндромом называется предложение, которое, после удаления из него всех пробелов и знаков препинания, читается одинаково справа налево и слева направо. Создатели одного известного текстового редактора пишут новую версию модуля для проверки орфографии. Они хотят реализовать возможность вывода подсказки для пользователя на тот случай, если он допустил опечатку при наборе какого-нибудь палиндрома. Конечно же, они решили обратиться именно к вам.

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

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

Во входном файле 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;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2016, 15:25
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Палиндром. Почему WA1? (C++):

Палиндром - C++
разработать программу которая определяет является ли данный текст палиндромом в среде C++

Палиндром 2 С++ - C++
Задание: Напишите программу проверки, является ли введенное число палиндромом. Организуйте многократный ввод чисел для проверки, признак...

Палиндром... - C++
Палиндром ведь это слова одинаково читающееся в обоих направениях. Помогите разобрать метод?! string palindrome(string word){ ...

палиндром - C++
имеется 3 класса 1. проверяет является ли строка char* палиндромом 2. проверяет является ли vector&lt;int&gt; палиндромом 3. проверяет...

Палиндром - C++
Здравствуйте! Наткнулся на такую задачу. Дана строка и нужно посчитать сколько палиндрома можно из нее сделать. Например: ввод: ababc ...

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

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

Не по теме:

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

0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
31.07.2016, 17:51 #10
Цитата Сообщение от pav1uxa Посмотреть сообщение
Как называется стиль такого написания кода (оформление кода)?
Ну, особого названия я не придумывал. Можно назвать стилем ленивого читателя, которому лень при чтении пересчитывать скобки и парсером работать.
Цитата Сообщение от pav1uxa Посмотреть сообщение
Где-то можно почитать?
Вот неплохие книжки.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2016, 17:51
Привет! Вот еще темы с ответами:

Палиндром в С++ - C++
Нужно составить программу которая определяет, является ли строчка палиндромом или нет. Написал такую программу, несколько раз проводил...

Палиндром - C++
Дайте реализацию программы, определяющей является ли входная строка палиндромом, пожалуйста. Заранее спасибо.

Палиндром - C++
Здравствуйте. Пытаюсь написать программу которая проверяет является ли введёное число с клавиатуры палиндромом. Метод проверки...

Палиндром - C++
Программа находит палиндромы в файле, но не совсем правильно, а именно: проверяет на условие палиндрома только первое слово. Что нужно...


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

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

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