Разбор задачи C4 (демо ЕГЭ 2011)

Время выполнения-60 мин, уровень сложности-высокий

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

Если требуемое число составить невозможно, то программа должна вывести на экран слово “NO”. А если возможно, то в первой строке следует вывести слово “YES”, а во второй – искомое симметричное число. Если таких чисел несколько, то программа должна выводить максимальное из них. Например, пусть на вход подаются следующие символы:
Do not 911 to 09 do.
В данном случае программа должна вывести
YES
91019

Решение:

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

Программа написана на языках:

Паскаль (среда разработки Turbo Pascal 7.0),
Бейсик (среда разработки Quick Basic 4.5),
Си (среда разработки Borland C++ 3.1),
Алгоритмический язык (среда разработки Кумир 1.9.0).

Чтобы прочесть комментарии к программе, наведите мышью на соответствующую строку. Строки, снабженные комментарием, выделены фиолетовым цветом.

Напротив названия языка программирования в скобках содержатся ссылки на скачку исходников и ехе (исполняемых файлов).

Паскаль (исходник, exe-файл)	Алгоритмический язык(исходник)
var a:array['0'..'9'] of integer; c, c_centr: 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_centr := 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 write(char(13)+char(10)); 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_centr); for c := '0' to '9' do for i := 1 to a[c] div 2 do write(c); end end.	алг нач целтаб a[0:9] сим с цел i, j, k, int_c, с_centr лог f, usp нц для i от 0 до 9 a[i]:=0 кц ввод с нц пока с<>"." int_c:=лит_в_цел(с,usp) если usp=да то a[int_c]:=a[int_c]+1 все ввод с кц k:=0 нц для i от 0 до 9 если mod(a[i],2)=1 то k:=k+1 c_centr:=c все кц f:=(a[0]=1) нц для i от 1 до 9 если (а[i]>1) или (a[i]=1) и (a[0]=0) то f:=да все кц если (k>1) или не f то вывод 'NO' иначе вывод 'YES', нс нц для i от 9 до 0 шаг -1 нц для j от 1 до div(a[i],2) вывод i кц кц если k=1 то вывод c_centr все нц для i от 0 до 9 нц для j от 1 до div(a[i],2) вывод i кц кц все кон
Бейсик (исходник)	СИ (исходник, exe-файл)
DIM k, i, j, ccentr, a(9), f AS INTEGER DIM c AS STRING FOR i = 0 TO 9 a(i) = 0 NEXT i INPUT c DO WHILE (c <> ".") IF c >= "0" AND c <= "9" THEN a(ASC(c) - ASC("0")) = a(ASC(c) - ASC("0")) + 1 END IF INPUT c LOOP k = 0 FOR i = 0 TO 9 IF a(i) MOD 2 = 1 THEN k = k + 1 ccentr = i END IF NEXT i IF a(0) = 1 THEN f = 1 ELSE f = 0 FOR i = 1 TO 9 IF a(i) > 1 OR a(i) = 1 AND a(0) = 0 THEN f = 1 NEXT i IF k > 1 OR f = 0 THEN PRINT "NO" ELSE PRINT "YES" FOR i = 9 TO 0 STEP -1 FOR j = 1 TO a(i) / 2 PRINT i; NEXT j NEXT i IF k = 1 THEN PRINT ccentr; FOR i = 0 TO 9 FOR j = 1 TO a(i) / 2 PRINT i; NEXT j NEXT i END IF END	#include <stdio.h> #include <string.h> #include <conio.h> #include <alloc.h> #include <ctype.h> #define false (0) #define true (!false) typedef unsigned char bool; void main() { int a[10],i,j,int_c,k,c_centr; char c; bool f; for(i=0;i<10;i++){ a[i]=0; } scanf("\n%c",&c); while(c!='.'){ if(isdigit(c)){ int_c=c-'0'; a[int_c]=a[int_c]+1; } scanf("%c",&c); } k=0; for(i=0;i<10;i++){ if(a[i]%2==1){ k=k+1; c_centr=i; } } f=(a[0]==1); for(i=1;i<10;i++){ if((a[i]>1)\|\|(a[i]==1)&& (a[0]==0)) f=true; } if((k>1)\|\|!f ) printf("\nNO"); else{ printf("\nYES\n"); for(i=9;i>-1;i--){ for(j=1;j<(a[i]/2+1);j++){ printf("%d",i); } } if (k==1) printf("%d",c_centr); for(i=0;i<10;i++){ for(j=1;j<(a[i]/2+1);j++){ printf("%d",i); } } } getch(); }