Московская олимпиада по информатике - 2005: различия между версиями
Содержимое удалено Содержимое добавлено
Tegel (обсуждение | вклад) м Откат правок 69.195.124.132 (обс.) к версии Devwebtel |
Zabshk (обсуждение | вклад) Отмена правки 116570, сделанной участником 69.195.124.132 (обс.) |
||
Строка 89:
Существует множество других алгоритмов, решающих задачу за время ''O(N log N)'' или ''O(N²)'', что удовлетворяет приведенным в задаче ограничениям. Но реализация этих алгоритмов не проще, а зачастую сложнее приведенной в этом разборе реализации линейного алгоритма.
== Задача B. Палиндром ==
''Автор разбора — В. М. Гуровиц''
Подсчитаем, сколько раз во входном файле встречается каждая буква. Для этого можно воспользоваться массивом:
k : array ['A'..'Z'] of longint;
Соответствующая часть программы будет выглядеть примерно так:
readln(N);
for i:=1 to N do begin
read(ch);
Inc(k[ch]);
end;
Если в палиндроме общее количество символов четно, то для каждого символа найдется симметричный ему, поэтому каждая буква должна встречаться четное количество раз. Если же общее количество символов нечетно, то для каждого символа, кроме стоящего в центре палиндрома, найдется пара, поэтому все буквы кроме одной, должны встречаться четное число раз. Таким образом, если некоторая буква встречается во входном файле четное число раз, то мы можем использовать все ее вхождения, а из букв, которые встречаются нечетное число раз лишь одну (первую по алфавиту) мы сможем использовать нечетное число раз. Определим, какая буква встречается нечетное количество раз первой:
o:='-'; {Буква, встречающаяся нечетное число раз}
for ch:='Z' to 'A' do
if k[ch] mod 2=1 then o:=ch;
Если во входном файле нет букв, встречающихся нечетное число раз, то первый по алфавиту палиндром устроен следующим образом: сначала идет половина букв A, затем половина букв B, …, затем половина букв Z, далее вторая половина букв Z, вторая половина букв Y, …, вторая половина букв A:
if o='-' then begin
for ch:='A' to 'Z' do
for i:=1 to k[ch] div 2 do
write(ch);
for ch:='Z' downto 'A' do
for i:=1 to k[ch] div 2 do
write(ch);
end;
Если во входном файле есть буквы, встречающиеся нечетное число раз, то первый по алфавиту палиндром устроен так же, как и палиндром четной длины, за одним исключением: в центре палиндрома расположена буква, записанная в переменную <tt>o</tt>:
if o<>'-'; then begin
for ch:='A' to 'Z' do
for i:=1 to k[ch] div 2 do
write(ch);
'''write(o);'''
for ch:='Z' downto 'A' do
for i:=1 to k[ch] div 2 do
write(ch);
end;
== Задача C. Представление числа ==
| |||