СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 27 № 3111

На вход программе подается набор символов, заканчивающийся точкой (в программе на языке Бейсик символы можно вводить по одному в строке, пока не будет введена точка, или считывать данные из файла). Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая сначала будет определять, есть ли в этом наборе символы, соответствующие десятичным цифрам. Если такие символы есть, то можно ли переставить их так, чтобы полученное число было симметричным (читалось одинаково как слева направо, так и справа налево). Ведущих нулей в числе быть не должно, исключение – число 0, запись которого содержит ровно один ноль.

Если требуемое число составить невозможно, то программа должна вывести на экран слово «NO». А если возможно, то в первой строке следует вывести слово «YES», а во второй – искомое симметричное число. Если таких чисел несколько, то программа должна выводить максимальное из них. Например, пусть на вход подаются следующие символы:

Do not 911 to 09 do.

В данном случае программа должна вывести

YES

91019

Решение.

Программа читает все входные символы до точки один раз, подсчитывая в массиве, хранящем 10 целых чисел, количество каждой из цифр. Сами входные символы при этом не запоминаются. Затем проверяется — сколько в этом массиве нечетных элементов. Если больше одного, то задача решения не имеет. При наличии решения сначала печатается половина имеющихся цифр 9 (если таковые имеются, в случае нечетного числа цифр — меньшая половина), затем 8 и т.д. до 0, потом печатается цифра, которая встречается во входных данных нечетное число раз, а затем — оставшаяся половина цифр 0 (если таковые имеются, в случае нечетного числа цифр — меньшая половина), 1, и т.д. до 9. Если никаких цифр, кроме 0, во входных данных нет, то задача имеет решение, только если этот ноль единственный. Если нулей четное число, а ненулевая цифра единственная, то решения не существует.

Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая (например, для строк, состоящих не более чем из 255 символов), или которая умеет только определять, имеет ли задача решение.

Пример правильной и эффективной программы на языке Паскаль:

var a:array['0'..'9'] of integer;

c, c_odd: char;

i, k: integer;

f: boolean;

begin

for c:='0' to '9' do a[c]:=0;

read(с);

while c<>'.' do

begin

if c in ['0' .. '9'] then a[c] := a[c] + 1;

read(c);

end;

k := 0; {количество цифр, встречающихся нечетное число раз}

for c := '0' to '9' do

if a[c] mod 2 = 1 then

begin

k := k + 1;

c_odd := c

end;

f := (a['0'] = 1);

for c := '1' to '9' do

if (a[c] > 1) or (a[c] = 1) and (a['0'] = 0) then f := true;

if (k > 1)or not f then writeln('NO') else

begin

writeln('YES');

for c := '9' downto '0' do

for i := 1 to a[c] div 2 do

write(c);

if k = 1 then

write(c_odd);

for c := '0' to '9' do

for i := 1 to a[c] div 2 do

write(c);

end

end.

 

Пример правильной и эффективной программы на языке Бейсик:

 

DIM k, i, j, iodd, a(9) AS INTEGER

FOR i = 0 TO 9

a(i) = 0

NEXT

INPUT c$

DO WHILE NOT (c$ = ".")

IF c$ >= "0" AND c$ <= "9" THEN

a(ASC(c$) - ASC("0")) = a(ASC(c$) - ASC("0")) + 1

ENDIF

INPUT c$

LOOP

k = 0

IF a(0) = 1 THEN f = 1 ELSE f = 0

FOR i = 0 TO 9

IF a(i) MOD 2 = 1 THEN

k = k + 1

iodd = i

END IF

IF i > 0 AND a(i) > 1 THEN f = 1

NEXT

IF k = 1 AND a(0) = 0 THEN f = 1

IF k > 1 OR f = 0 THEN

PRINT "NO"

END

ENDIF

PRINT "YES"

FOR i = 9 TO 0 STEP -1

FOR j = 1 TO a(i) \ 2

PRINT i;

NEXT

NEXT

IF k = 1 THEN PRINT iodd;

FOR i = 0 TO 9

FOR j = 1 TO a(i) \ 2

PRINT i;

NEXT

NEXT

END