Длинный диктант - вычеркнуть букву, чтобы число букв "A" на четных и нечетных местах было одинаковым.
Эта задача не из ЕГЭ, но алгоритм решения получился красивым, поэтому хотелось бы им поделиться.
Задача формулируется следующим образом:
Есть длинная (до миллиона символов) строка, состоящая из букв "A" и "B". Надо вычеркнуть из неё один символ так, чтобы количество букв "A", стоящих на нечетных местах, было бы равно количеству букв "A" на четных местах.
Простой способ решения - подсчитать для каждой позиции в строке, сколько букв "A" на нечетных и четных местах до этой позиции включительно. Тогда при вычеркивании какой-либо буквы нечетные места после неё станут чётными и наоборот. Нужно сложить сумму нечетных до и сумму четных после, а также сумму четных до и сумму нечетных после. Если эти числа совпадут, то данная буква годится для вычеркивания.
Приведем законченную программу на С.
#include <stdio.h>
#include <string.h>
#define N 1000000
char s[(N)+2];
int acount[2][(N)+2];
int main()
{
int i,l;
acount[0][0]=0;
acount[1][0]=0;
scanf("%s",s);
l = strlen(s);
for(i=0; i < l; i++)
{
acount[0][i+1]=acount[0][i];
acount[1][i+1]=acount[1][i];
if( s[i] == 'A' ) acount[i%2][i+1]++;
}
for(i=1; i<=l; i++)
if( acount[0][i-1] + (acount[1][l] - acount[1][i]) == acount[1][i-1] + (acount[0][l] - acount[0][i]) ) printf("%d ", i);
printf("\n");
return 0;
}
На Питоне эта программа может выглядеть так:
s=input()
l = len(s)
acountodd=[0]
acounteven=[0]
for i in range(l):
acountodd.append(acountodd[i])
acounteven.append(acounteven[i])
if s[i] == 'A':
if i%2 == 0: acounteven[i+1] += 1
else: acountodd[i+1] += 1
for i in range(1,l+1):
if acounteven[i-1] + (acountodd[l] - acountodd[i]) == acountodd[i-1] + (acounteven[l] - acounteven[i]): print(i, end=' ')
print(' ')
(c) Ю.Д.Красильников 2021
Комментарии
Отправить комментарий