Задача в неделю (стр. 6 )

б) 1 искаженная колонка. Тогда в каждом тексте искажен один и тот же символ и восстановить текст нельзя.

в) 0 искаженных колонок. Такое может быть лишь в случае, когда во всех трех текстах возникла одна и та же ошибка. Текст восстановить нельзя.

г) 2 искаженных колонки. Этот случай самый нетривиальный. В каждой искаженной колонке найдутся либо два одинаковых символа, либо все три попарно различны. Рассмотри все возможные случаи:

1) В обеих колонках символы попарно различны. Такое не может произойти, т. к. получается 4 ошибочных символа.

2) В обеих колонках по 2 совпадающих символа. Тогда возможны два случая:

А Б

А Б - восстановление не однозначно,

В Г

А Г

А Б - такого случая не может быть,

В Б

3) В одной колонке 2 совпадающих, а в другой - все попарно различные символы. В этом случае текст восстанавливается однозначно:

А В - ошибочный символ

А Г - ошибочный символ

ошибочный символ - Б Д

Программа после чтения текстов T[1], T[2], T[3], заполняет n - число искаженных колонок, и для каждой искаженной колонки элемент массива

B : Array [1..3] Of Record

num : Integer ; - номер позиции в тексте,

max : 1..2 ; - количество совпадающих символов в колонке num,

pos : 1..3 ; - в случае max=2, то номер текста, в котором символ

отличен от двух других.

End ;

 Var

T : array [1..3] of string;

V : string;

s : integer;

Bad : array [1..3] of record

num : integer;

max : 1..2;

pos : 1..3

end;

n : integer;

i, j, k : integer;

 Procedure Vost (i, bad:Integer);

begin

if bad=1 then V[i]:=T[2][i]

else V[i]:=T[1][i]

end;

begin

assign(input,'input. txt'); reset(input);

assign(output,'output. txt'); rewrite(output);

readln(T[1]);

readln(T[2]);

readln(T[3]);

s:=length(T[1]);

n:=0;

for i := 1 to s do

if (T[1][i]<>T[2][i]) or (T[2][i]<>T[3][i] ) Then

with Bad [n+1] do

begin

n:=n+1;

num:=i;

max:=1;

for j:=1 to 2 do

for k:=j+1 to 3 do

if T[j][i]=T[k][i] then

begin

max:=2;

pos:=6-j-k;

end;

end;

if (n=0) or (n=1) then write ('NO')

else if n=3 then

begin

V:=T[1];

for i:=1 to 3 do

Vost (Bad[i].num, Bad[i].pos);

write(V)

end

else

if (Bad[1].max=2) and (Bad[2].max=2) then

write ('NO')

else begin

V:=T[1];

if Bad[1].max=2 then

begin

Vost (Bad[1].num, Bad[1].pos);

V[Bad[2].num]:=T[Bad[1].pos, Bad[2].num];

end else begin

Vost (Bad[2].num, Bad[2].pos);

V[Bad[1].num]:=T[Bad[2].pos, Bad[1].num];

end;

write(V)

end;

end.

Задача J. "Делимость на 7" (20 баллов)

Петя Васечкин хочет выяснить, делится ли на семь двоичное число, состоящее не более чем из 10000 цифр.

Требуется написать программу, которая выполняет желание Пети и выводит 0, если число делится на 7, или выводит минимальное число, записанное в десятичной системе счисления, которое нужно добавить к исходному двоичному числу, чтобы получилось число кратное семи.

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

Ограничение по времени тестирования: по 3 секунды на один тест.

Формат входных данных:

В единственной строке входного файла задается двоичное число, запись которого завершается точкой.

Формат выходных данных:

В выходной текстовый файл OUTPUT. TXT записывается 0 или найденное число.

Пример файла входных данных:

111.

Пример файла выходных данных (для приведенного выше входного файла):

0

Разбор задачи № J

Запишем двоичное число в массив и воспользуемся следующим признаком делимости двоичных чисел на 7:

если вспомнить, что признаком деления на 9 в десятичной системе счисления является делимость на 9 суммы цифр числа, то аналогично получаем, что признаком деления на 7 в системе счисления с базисом 8 будет делимость на 7 суммы всех восьмеричных цифр числа. Поэтому разбиваем двоичное число справа налево на триады, которые однозначно можно преобразовать в восьмеричные цифры, находим их сумму и делим ее на 7. Если остаток равен 0, то введенное число делится на 7, иначе – нет, а тогда для делимости числа на 7 надо добавить к нему разность 7 и этого остатка.

var

r : longint;

i, j, n : integer;

s : array[1..10001] of byte;

c : char;

begin

assign(input,'input. txt');reset(input);

assign(output,'output. txt');rewrite(output);

n:=0;

repeat

read(c);

if c<>'.' then

begin

n:=n+1;

s[n]:=ord(c)-48;

end;

until c='.';

j:=1;

r:=0;

for i:=n downto 1 do

begin

r:=r+s[i]*j;

j:=j*2;if j=8 then j:=1;

end;

r:=r mod 7;

if r<>0 then r:=7-r;

write(r)

end.

Задача K. "Вирус" (20 баллов)

Колония клеток представляет собой квадратную матрицу порядка N (N < 500). В колонию проникает M (M < 11) вирусов, которые поражают клетки с координатами (X1, Y1), … (Xm, Ym). За одну единицу времени вирус проникает в клетки, соседние с зараженными (соседними считаются клетки, имеющие общую сторону).

Требуется написать программу, которая определит время заражения всей колонии.

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

Ограничение по времени тестирования: по 10 секунд на один тест.

Формат входных данных:

В строках входного файла INPUT. TXT задаются:

1 строка — N

2 строка — M

3 строка — X1 Y1

4 строка — X2 Y2

…

M+2 строка — Xm Ym.

Формат выходных данных:

В выходной текстовый файл OUTPUT. TXT записывается найденное число – время заражения.

Пример файла входных данных:

5

2

1 2

5 5

Пример файла выходных данных (для приведенного выше входного файла):

4

Разбор задачи № K

Если вирус находится в какой-то клетке, то через один момент времени он заражает клетки, координаты которых отличаются на единицу от координат вируса в любом из четырех направлений. В следующий момент заражаются клетки, у которых сумма сдвигов по направлениям равна 2. Назовем расстоянием между двумя клетками колонии сумму абсолютных величин разностей координат этих клеток по обеим осям. Найдем расстояние от клетки до каждого из вирусов и возьмем минимальное из них. Это число и будет временем заражения этой клетки. Осталось найти максимум таких расстояний по всем клеткам колонии.

var

i, j, k, n,m, max, t, t1 : integer;

x, y : array[1..10] of integer;

begin

assign(input,'input. txt');reset(input);

assign(output,'output. txt');rewrite(output);

readln(n);

readln(m);

for i:=1 to m do

readln(x[i],y[i]);

max:=0;

for i:=1 to n do

for j:=1 to n do

begin

t:=2*n;

for k:=1 to m do

begin

t1:=abs(x[k]-i)+abs(y[k]-j);

if t1<t then t:=t1

end;

if t>max then max:=t

end;

write(max)

end.

Задача L. "Маска" (20 баллов)

Введем понятие маски - строки из N символов, каждый из которых имеет следующий смысл:

? — в этой позиции может находиться любая цифра (кроме 0, если это первая цифра числа);

цифра — в этой позиции может находиться только эта цифра;

заглавная латинская буква — в этой позиции может находиться любая цифра, не использованная по предыдущему правилу, и разным буквам соответствуют разные цифры, а одинаковым буквам — одинаковые цифры.

Число принадлежит множеству, если его цифры удовлетворяют маске.

Требуется написать программу, которая определит количество чисел в этом множестве.

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

Ограничение по времени тестирования: по 5 секунд на один тест.

Формат входных данных:

Во входном файле INPUT. TXT в единственной строке задается маска, в которой не более 20 символов.

Формат выходных данных:

В выходной текстовый файл OUTPUT. TXT записывается найденное число – количество элементов.

Пример файла входных данных:

?X?45X

Пример файла выходных данных (для приведенного выше входного файла):

720

Задача M. "Пятерки" (20 баллов)

Задано натуральное N.

Требуется написать программу, которая определит количество цифр 5 в записи всех натуральных чисел от 1 до N включительно.

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

Ограничение по времени тестирования: по 2 секунды на один тест.

Формат входных данных:

Во входном файле INPUT. TXT в единственной строке задается число N£100 000 000.

Формат выходных данных:

В выходной текстовый файл OUTPUT. TXT записывается найденное число – количество пятерок.

Пример файла входных данных:

27

Пример файла выходных данных (для приведенного выше входного файла):

3

Задача N. "Выборы" (20 баллов)

В одном из государств все решения традиционно принимались простым большинством голосов на общем собрании граждан, которых, к счастью, было не очень много. Одна из местных партий, стремясь прийти к власти как можно более законным путем, смогла добиться некоторой реформы избирательной системы. Главным аргументом было то, что население острова в последнее время значительно возросло, и проведение общих собраний перестало быть легкой задачей.

Суть реформы состояла в следующем: с момента введения ее в действие все избиратели острова делились на K групп (необязательно равных по численности). Голосование по любому вопросу теперь следовало проводить отдельно в каждой группе, причем считалось, что группа высказывается "за", если "за" голосует более половины людей в этой группе, а в противном случае считалось, что группа высказывается "против". После проведения голосования в группах подсчитывалось количество групп, высказавшихся "за" и "против", и вопрос решался положительно в том и только том случае, когда групп, высказавшихся "за", оказывалось более половины общего количества групп.