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

begin

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

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

readln(f1,n); ss:=0;

for i:=1 to n do

for j:=1 to n do

begin read(f1,s); ss:=ss+s; a[i, j]:=s end;

for i:=0 to n do p[i]:=i;

max:=0;

repeat

m:=0; for i:=1 to n do m:=m+a[i, p[i]];

if m>max then begin max:=m; pmax:=p end;

j:=n; repeat j:=j-1 until p[j]<p[j+1];

if j>0 then

begin

i:=n+1; repeat i:=i-1 until p[i]>p[j];

s:=p[i]; p[i]:=p[j]; p[j]:=s;

for i:=j+1 to (n+j+1) div 2 do

begin s:=p[i]; p[i]:=p[n+j+1-i]; p[n+j+1-i]:=s end

end

until j=0;

for i:=1 to n do write(f2,chr(pmax[i]-1+ord('A')));

writeln(f2);

write(f2,ss-max);

close(f2)

end.

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

Задача 8. "Шахматная" (20 баллов)

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

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

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

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

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

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

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

Входной файл INPUT. TXT состоит из 2-х строк. В первой строке записаны координаты ферзя, во второй - коня.

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

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

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

a1

h8

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

22

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

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

var

f, k, s : string;

a : array [-1..10,-5..14] of byte;

b : array [1..2,1..8] of integer;

i, j, ife, jfe, ik, jk, ch : integer;

f1, f2 : text;

begin

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

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

s:='abcdefgh';

b[1,1]:= 1; b[2,1]:= 2;

b[1,2]:= 1; b[2,2]:=-2;

b[1,3]:= 2; b[2,3]:= 1;

b[1,4]:= 2; b[2,4]:=-1;

b[1,5]:=-2; b[2,5]:= 1;

b[1,6]:=-2; b[2,6]:=-1;

b[1,7]:=-1; b[2,7]:= 2;

b[1,8]:=-1; b[2,8]:=-2;

readln(f1,f); readln(f1,k);

jfe:=pos(f[1],s); ife:=ord(f[2])-48;

jk:=pos(k[1],s); ik:=ord(k[2])-48;

for i:=1 to 8 do

for j:=1 to 8 do a[i, j]:=0;

for i:=1 to 8 do

for j:=1 to 8 do

begin

if (i=ife) then a[i, j]:=1;

if (j=jfe) then a[i, j]:=1;

if ( i-j=ife-jfe ) then a[i, j]:=1;

if ( i+j=ife+jfe ) then a[i, j]:=1;

end;

for i:=1 to 8 do

a[ik+b[1,i], jk+b[2,i]]:=1;

a[ife, jfe]:=0; a[ik, jk]:=0;

if ife=ik then

if jfe<jk then for j:=jk+1 to 8 do a[ife, j]:=0

else for j:=1 to jk-1 do a[ife, j]:=0;

if jfe=jk then

if ife<ik then for i:=ik+1 to 8 do a[i, jfe]:=0

else for i:=1 to ik-1 do a[i, jfe]:=0;

if ife-jfe=ik-jk then

if ife<ik then for i:=ik+1 to 8 do a[i, i-ik+jk]:=0

else for i:=1 to ik-1 do a[i, jk+i-ik]:=0;

if ife+jfe=ik+jk then

if ife<ik then for i:=ik+1 to 8 do a[i, jk+ik-i]:=0

else for i:=1 to ik-1 do a[i, jk-i+ik]:=0;

ch:=0;

for i:=1 to 8 do

for j:=1 to 8 do ch:=ch+a[i, j];

{Печать поля для проверки

for i:=8 downto 1 do

begin

write(i,' ');

for j:=1 to 8 do

if (i=ife) and (j=jfe) then write('Ф') else

if (i=ik) and (j=jk) then write('К') else

if a[i, j]=1 then write('+') else write(' ');

writeln

end;

writeln(' abcdefgh');

}

writeln(f2,ch); close(f2)

end.

Задача 9. "Фибоначчиева система счисления" (20 баллов)

Числа Фибоначчи U1, U2, … определяются начальными значениями и соотношением:

U1=1; U2=2; Un=Un-1+Un-2.

Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы, весами являются не степени двойки 1, 2, 4, 8, 16, …, а числа Фибоначчи 1, 2, 3, 5, 8, 13, …. В этой системе счисления каждое положительное целое число единственном способом представляется в виде строки из нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.

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

Например, исходные строки 10101 и 100 представляют числа 1*8+0*5+1*3+0*2+1*1=8+3+1=12 и 1*3+0*2+0*1=3. Ответом является строка 100010, представляющая число 1*13+0*8+0*5+0*3+1*2+0*1=13+2=15=12+3.

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

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

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

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

Технические ограничения: строки могут быть столь длинны, что числа A и B превысят максимально допустимое в вашем компьютере целое число. Длина записи чисел A, B и их суммы A+B в фибоначчиевой системе счисления не превышает 255 знаков.

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

В текстовом файле INPUT. TXT в первой строке записано первое число, а во второй - второе.

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

Вывести в текстовый файл OUTPUT. TXT полученную сумму.

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

10101

100

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

100010

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

Одним из способов решения задачи является перевод заданных чисел в фибоначчиевой системе счисления в десятичные числа, после этого производится сложение и результат опять преобразуется в фибоначчиеву систему счисления. В предложенной ниже программе используется алгоритм сложения в фибоначчиевой системе счисления. Точнее, это делается следующим образом. В начале производится сложение по разрядам, а затем, если в записи стоят две единицы рядом, то из соотношения fi=fi-1+fi-2 они заменяются на одну единицу в старшем разряде. Если же в каком-то разряде получается 2, то она заменятся на единицы из соотношений 2f1=f2, 2f2=f3+f1, 2fi=fi+1+fi-2.

Var b, c, d : string;

a : array [1..255] of byte;

i, k, m : integer;

f1, f2 : text;

begin

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

readln(f1,b); readln(f1,c);

if length(b)<length(c) then

begin d:=b; b:=c; c:=d end;

for i:=1 to length(b)-length(c) do c:='0'+c;

m:=length(b);

for i:=1 to 255 do a[i]:=0;

for i:=1 to m do

a[i]:=ord(b[m+1-i])+ord(c[m+1-i])-96;

k:=1;

repeat

if k=1 then

begin

if a[1]>1 then

begin

a[1]:=0; if m<2 then m:=2; a[2]:=a[2]+1

end;

k:=k+1

end;

if k=2 then

begin

if a[2]<2 then

begin

if (a[2]=1) and (a[1]=1) then

begin

a[1]:=0; a[2]:=0; if m<3 then m:=3; a[3]:=a[3]+1

end;

k:=k+1

end

else

begin

if m<3 then m:=3; a[3]:=a[3]+1;

if a[1]=0 then

begin

a[1]:=a[1]+1; a[2]:=a[2]-2; k:=1

end

else

begin

a[1]:=0; a[2]:=a[2]-1;

end

end

end;

if k>2 then

if a[k]<2 then

begin

if (a[k-1]=1) and (a[k]=1) then

begin

a[k-1]:=0; a[k]:=0; if k+1>m then m:=k+1; a[k+1]:=a[k+1]+1

end;

k:=k+1

end

else

begin

if k+1>m then m:=k+1; a[k+1]:=a[k+1]+1;

if a[k-1]=0 then

begin

a[k-2]:=a[k-2]+1; a[k]:=a[k]-2; k:=k-2

end

else

begin

a[k-1]:=0; a[k]:=a[k]-1

end

end

until k>m;

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

for i:=m downto 1 do write(f2,a[i]); close(f2)

end.

Задача A. "Оставшееся число" (20 баллов)

Задан ряд последовательных натуральных чисел от n до m (n<m), из которого удаляют сначала все числа, стоящие на нечетных местах. Затем из оставшегося ряда удаляют все числа, стоящие в нем на четных местах. Эти действия повторяют до тех пор, пока не останется одно число.

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

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

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

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

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

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

В текстовом файле INPUT. TXT в первой строке записано первое число n, а во второй – второе m (n<m<1000000000).

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

Вывести в текстовый файл OUTPUT. TXT оставшееся число.

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

1 4

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

2

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

Каждое вычеркивание уменьшает длину последовательности в почти два раза. Вычитание из каждого элемента последовательности числа n-1 сводит исходную задачу к последовательности 1, 2, …, m-n+1, в которой на i-м месте стоит число i. А теперь проследим сделанные вычеркивания для этой последовательности с конца. Когда после всех вычеркиваний остается один элемент, то его номер равен k=1. Этот номер получается или из номера k=2*k, если вычеркиваются числа, стоящие на нечетных местах, или из номера k=2*k-1, если вычеркиваются числа, стоящие на четных местах. В результате мы можем узнать с какого места в исходной последовательности 1, 2, …, m-n+1, получилось после всех вычеркиваний оставшееся число. А теперь, добавив к нему n-1, получаем оставшееся число из исходной последовательности.

var n, m, k, n1 : longint;

begin

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

readln(n, m);

n1:=m-n+1;

k:=1;

while n1>1 do

begin

n1:=n1 div 2;

if n1>1 then n1:=(n1+1) div 2;

k:=2*(2*k-1)

end;

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

write(n-1+k)

end.

Задача B. " Умножение дроби" (20 баллов)

Задана некоторая правильная периодическая дробь Q и натуральное число N. Q и N таковы, что количество цифр, используемых для их записи, не превосходит 100. При изображении дроби Q периодическая часть заключается в круглые скобки.