На вход программе подается набор символов, заканчивающийся точкой (в программе на языке Бейсик символы можно вводить по одному в строке, пока не будет введена точка, или считывать данные из файла). Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая сначала будет определять, есть ли в этом наборе символы, соответствующие десятичным цифрам. Если такие символы есть, то можно ли переставить их так, чтобы полученное число было симметричным (читалось одинаково как слева направо, так и справа налево). Ведущих нулей в числе быть не должно, исключение – число 0, запись которого содержит ровно один ноль.
Если требуемое число составить невозможно, то программа должна вывести на экран слово «NO». А если возможно, то в первой строке следует вывести слово «YES», а во второй – искомое симметричное число. Если таких чисел несколько, то программа должна выводить максимальное из них. Например, пусть на вход подаются следующие символы:
Do not 911 to 09 do.
В данном случае программа должна вывести
YES
91019
Программа читает все входные символы до точки один раз, подсчитывая в массиве, хранящем 10 целых чисел, количество каждой из цифр. Сами входные символы при этом не запоминаются. Затем проверяется — сколько в этом массиве нечетных элементов. Если больше одного, то задача решения не имеет. При наличии решения сначала печатается половина имеющихся цифр 9 (если таковые имеются, в случае нечетного числа цифр — меньшая половина), затем 8 и т. д. до 0, потом печатается цифра, которая встречается во входных данных нечетное число раз, а затем — оставшаяся половина цифр 0 (если таковые имеются, в случае нечетного числа цифр — меньшая половина), 1, и т. д. до 9. Если никаких цифр, кроме 0, во входных данных нет, то задача имеет решение, только если этот ноль единственный. Если нулей четное число, а ненулевая цифра единственная, то решения не существует.
Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая (например, для строк, состоящих не более чем из 255 символов), или которая умеет только определять, имеет ли задача решение.
Пример правильной и эффективной программы на языке Паскаль:
Приведём решение задачи на языке Pascal.
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(c);
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.
Приведём решение Сергея Донец на языке PascalABC.NET.
begin
var s := ReadSeqStringWhile(x->x<>'.').JoinToString;
var num := s.Where(c->c.IsDigit);
if num.Any
then begin
var n:=num.JoinToString;
var d:=n.Permutations(n.Length).Distinct.Where(c->c=ReverseString(c));
if d.Any
then writeln('YES',NewLine,d.Max)
else writeln('NO');
end
else writeln('NO');
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