Задача в неделю
Задача 1. "Число" (20 баллов)
Задано целое число N (1£N£2147483647).
Требуется написать программу, которая определяет наименьшее натуральное число с произведением цифр равным N.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит одно целое число N.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно число - искомое наименьшее натуральное число. Если такого числа не существует, то записать в выходной файл значение 0.
Пример файла входных данных:
10
Пример файла выходных данных (для приведенного выше входного файла):
25
Разбор задачи № 1
Проведем разложение заданного числа на простые множители. Если в этом разложении встречается простое число большее 10, то ответом будет 0. Иначе так сгруппируем простые множители 2, 3, 5 и 7, чтобы обеспечить минимум искомого числа. Достаточно очевидно, что для этого надо выделить наибольшее число делителей 9, 8, …, 3, 2 и записать соответствующее количество этих цифр в порядке возрастания. Этот алгоритм и записан в следующей программе.
var
n, n1, k: longint;
i : integer;
f1, f2 : text;
begin
assign(f1,'input.txt'); reset(f1);
assign(f2,'output.txt'); rewrite(f2);
read(f1,n); n1:=0; k:=1;
for i:=9 downto 2 do
while n mod i=0 do
begin n1:=n1+i*k; k:=k*10; n:=n div i end;
if n>1 then n1:=0;
write(f2,n1); close(f2)
end.
В этой программе искомое число записывается как десятичное типа longint. Но, например, для исходного числа равного 230, искомое число равно 8888888888 (10 восьмерок) и выходит за границы указанного типа. Приходится для хранения искомого числа использовать другое представление. Большинство участников для этого использовали строковый тип, в представленной ниже программе с этой целью использован массив от 2 до 9, в котором хранится количество используемых в записи числа цифр.
var
n : longint;
i, j : integer;
a : array [2..9] of integer;
f1, f2 : text;
begin
assign(f1,'input.txt'); reset(f1);
assign(f2,'output.txt'); rewrite(f2);
read(f1,n);
for i:=2 to 9 do a[i]:=0;
for i:=9 downto 2 do
while n mod i=0 do
begin a[i]:=a[i]+1; n:=n div i end;
if n>1 then write(f2,0)
else for i:=2 to 9 do
for j:=1 to a[i] do write(f2,i);
close(f2)
end.
Задача 2. "Сообщение" (20 баллов)
В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили ее порядковым номером в русском алфавите (А - 1, Б - 2, …, Я - 33), а символ пробел нулем.
Требуется написать программу, которая по заданной последовательности цифр (не более 100) находит количество исходных сообщений, из которых она могла бы получиться.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит последовательность цифр.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно число - искомое количество исходных сообщений.
Пример файла входных данных:
1025
Пример файла выходных данных (для приведенного выше входного файла):
4
Разбор задачи № 2
Обозначим через A(n) требуемое количество исходных сообщений, из которых восстанавливаются первые n символов кода. Легко получить, что A(n)=A(n-1)+A(n-2), если два последних символа (n-1-й и n-й) составляют допустимый код (10, 11, …, 33, но не 01, 02, …, 09, 34, 35, …, 99), и A(n)=A(n-1) иначе.
Это реализовано в следующей программе
var
a, b, c : longint;
i : integer;
s, s1, s2 : string;
f1, f2 : text;
begin
assign(f1,'input.txt'); reset(f1);
assign(f2,'output.txt'); rewrite(f2);
readln(f1,s);
a:=1; b:=1; s1:=s[1];
for i:=2 to length(s) do
begin
s2:=s[i]; s1:=s1+s2; c:=b;
if ('10'<=s1) and (s1<='33') then c:=c+a;
a:=b; b:=c; s1:=s2
end;
write(f2,c); close(f2)
end.
Но A(n) для больших n может оказаться больше максимального в используемом типе longint, поэтому надо организовать сложение в столбик двух длинных чисел. Это реализовано так
var
a, b, c : array [1..100] of byte;
i, na, nb, nc : integer;
s, s1, s2 : string;
f1, f2 : text;
procedure summa;
var i, p : integer;
begin
p:=0;
for i:=1 to nc do
begin p:=p+c[i]+a[i]; c[i]:=p mod 10; p:=p div 10 end;
if p>0 then begin nc:=nc+1; c[nc]:=p end
end;
begin
for i:=1 to 100 do begin a[i]:=0; b[i]:=0; c[i]:=0 end;
assign(f1,'input.txt'); reset(f1);
assign(f2,'output.txt'); rewrite(f2);
readln(f1,s);
na:=1; a[1]:=1; nb:=1; b[1]:=1; s1:=s[1];
for i:=2 to length(s) do
begin
s2:=s[i]; s1:=s1+s2; nc:=nb; c:=b;
if ('10'<=s1) and (s1<='33') then summa;
na:=nb; a:=b; nb:=nc; b:=c; s1:=s2
end;
for i:=nc downto 1 do write(f2,c[i]); close(f2)
end.
Задача 3. "Простые гири" (40 баллов)
Имеются гири с массами: 1 г, 2 г, …, N г (N£500000).
Требуется написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 5 секунд на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит число N.
Формат выходных данных:
В выходной файл OUTPUT.TXT выводится список найденных пар. Каждая пара выводится в одной строке через пробел.
Пример файла входных данных:
7
Пример файла выходных данных (для приведенного выше входного файла):
1 6
7 4
5 2
Разбор задачи № 3
Эта задача предлагалась на IX Всероссийской олимпиаде школьников по информатике в апреле 1997 года в Санкт-Петербурге. Ее автором является Сергей Геннадьевич Волченков, кандидат технических наук, доцент Ярославского государственного университета. Сергей Геннадьевич уже много лет работает в жюри Всероссийских олимпиад не только по информатике, но и по математике. Им придумано много задач для различных соревнований школьников по математике и информатике. Его задачи публиковались в журналах "Квант", "Информатика и образование", приложении "Информатика" к газете "Первое сентября", других изданиях. Надеюсь, что в дальнейшем мы еще не раз встретимся с интересными задачами С.Г. Волченкова в нашем проекте.
Авторское решение задачи состоит в следующем. Найдем первое большее N простое число. Обозначим его через P. Тогда пары чисел (P-N, N), (P-N+1, N-1), … имеют суммарный вес P и удовлетворяют условию задачи. Легко заметить, что все числа от P-N до N входят в одну из пар. После этого осталось решить такую же задачу с новым значением N, равным P-N-1. Этот процесс продолжается до тех пор, пока значение N больше одного. При этом получается, что найденное количество пар чисел равно максимально возможному количеству пар из различных чисел от 1 до N. Таким образом, найдено решение, удовлетворяющее всем условиям задачи.
Рассмотренный выше алгоритм реализован в следующей программе
var
n, p, i, j : longint;
f1, f2 : text;
function prostoe(n:longint): boolean;
var i, j : longint;
begin
j:=0;
for i:=1 to n do
if n mod i = 0 then j:=j+1;
if j=2 then prostoe:=true else prostoe:=false
end;
begin
assign(f1,'input.txt'); reset(f1);
assign(f2,'output.txt'); rewrite(f2);
read(f1,n);
while n>1 do
begin
p:=n+1;
while not prostoe(p) do p:=p+1;
i:=p-n; j:=n; n:=i-1;
while i<j do
begin
writeln(f2,i,' ',j);
i:=i+1; j:=j-1
end
end;
close(f2)
end.
В ниже приведенной программе использован для определения простоты числа более совершенный алгоритм.
var n, p, i, j : longint;
f1, f2 : text;
function prostoe(n:longint): boolean;
var i, j : longint; t : boolean;
begin
j:=2; t:=true;
while t and (j*j<=n) do
begin
if n mod j=0 then t:=false;
j:=j+1
end;
prostoe:=t
end;
begin
assign(f1,'input.txt'); reset(f1);
assign(f2,'output.txt'); rewrite(f2);
read(f1,n);
while n>1 do
begin
p:=n+1;
while not prostoe(p) do p:=p+1;
i:=p-n; j:=n; n:=i-1;
while i<j do
begin
writeln(f2,i,' ',j);
i:=i+1; j:=j-1
end
end;
close(f2)
end.
Задача 4. "Последняя цифра" (20 баллов).
Задано натуральное число N (1£N£9999).
Требуется написать программу, определяющую последнюю ненулевую цифру числа N!=1*2*3*…*N.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит число N.
Формат выходных данных:
В выходной файл OUTPUT.TXT найденная цифра.
Пример файла входных данных:
5
Пример файла выходных данных (для приведенного выше входного файла):
2
Разбор задачи № 4
Факториал введенного числа может заканчиваться нулями. Они получаются произведением 2 и 5. Поэтому вначале посчитаем количество пятерок в разложении факториала на простые множители. Далее, используя легко доказываемое свойство остатка от деления на 10 (a*b mod 10=(a mod 10)*(b mod 10) mod 10) и пропуская умножение на 5 и на такое же число умножений на 2, найдем искомую цифру.
Рассмотренный выше алгоритм реализован в следующей программе
var
n, i, j, k, km, f : integer;
begin
assign(input,'input.txt'); reset(input);
read(n);
f:=1;
km:=0; k:=5;
while n div k>0 do begin km:=km+n div k; k:=k*5 end;
for i:=2 to n do
begin
j:=i;
while j mod 5 =0 do j:=j div 5;
while (km>0) and (j mod 2 =0) do begin km:=km-1; j:=j div 2 end;
f:=(f*(j mod 10)) mod 10
end;
assign(output,'output.txt'); rewrite(output);
write(f)
end.
Задача 5. "Плавающие числа" (20 баллов)
Дано N (1£N£100) целых чисел. Каждое из них можно один раз изменить не более чем на целую величину L (1£L£3200) как в сторону увеличения, так и в сторону уменьшения или оставить без изменения. Если после такой операции некоторые из чисел оказываются равными, то они засчитываются за одно. С данными числами произвели указанную операцию таким образом, что осталось минимально возможное количество чисел.
Требуется написать программу для определения этого количества.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 5 секунд на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке значения L и N, во второй строке N чисел (в диапазоне от -32000 до 32000), записанных через пробел.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одну строку - найденное количество.
Пример файла входных данных:
10 3
11 21 27
Пример файла выходных данных (для приведенного выше входного файла):
1
Разбор задачи № 5
Эта задача предлагалась на X Кировской областной олимпиаде школьников по информатике в 1998 году. Большую работу по развитию олимпиадного движения школьников проводит в этом городе кандидат технических наук, декан факультета информатики Кировского государственного педагогического университета Станислав Михайлович Окулов. Его ученики неоднократно побеждали на российский и международных олимпиад, он автор многих интересных задач, а также нескольких книг, посвященных олимпиадам. С его работами можно познакомиться в приложении "Информатика" к газете "Первое сентября". О Станиславе Михайловиче еще очень много можно рассказывать, но я думаю, что еще не раз воспользуюсь его наработками в работе нашего проекта. Итак, авторская идея решения задачи.
Упорядочим исходный массив a1, a2, …, aN по неубыванию. Затем в первую группу объединим числа, попадающие в интервал [a1, a1+2L]. Пусть ak - первое число, не попавшее в первую группу. Во вторую группу объединим числа, попадающие а интервал [ak, ak+2L]. Этот итеративный процесс продолжаем до тех пор, пока не будут рассмотрены все элементы массива. Ясно, что каждую группу, полученную описанным способом, можно превратить в одно число. Таким образом, если описанный способ дает наименьшее количество групп, то он же дает и наименьшее количество чисел. Покажем, что количество групп действительно наименьшее. Для этого рассмотрим числа a1, ak, …, которые являются первыми членами групп. Ясно, что каким бы способом мы не разбивали группы, никакие два числа из этих чисел не попадут в одну группу. Следовательно, групп не может быть меньше, чем этих чисел.
Эта идея реализована в следующей программе.
var
N, L, Count : integer;
X : array [1..100] of integer;
f1, f2 : text;
Procedure Init;
var i, j, Y : integer;;
begin
assign(f1,'input.txt'); reset(f1);
readln(f1,L,N);
for i:=1 to n do read(f1,X[i]);
for i:=1 to N-1 do
for j:=i+1 to n do
if X[i]>X[j] then
begin
Y:=X[i]; X[i]:=X[j]; X[j]:=Y
end
end;
Procedure Solve;
var i, j : integer;
begin
Count:=0; i:=1;
while i<=N do
begin
j:=i+1;
{*} while (j<=n) and (X[j]-X[i]<=2*L) do j:=j+1;
Count:=Count+1;
i:=j
end
end;
begin
Init;
Solve;
assign(f2,'output.txt'); rewrite(f2);
write(f2,Count); close(f2);
end.
Но эта программа имеет один скрытый дефект. При вычитании значений двух элементов массива в строке, помеченной звездочкой, может происходить арифметическое переполнение. Устранить этот дефект можно различными способами, используя для этого данные целого типа повышенной точности. Например, так как сделано в следующей программе.
var
N, L, Count : integer;
X : array [1..100] of longint;
f1, f2 : text;
Procedure Init;
var i, j : integer; Y: longint;
begin
assign(f1,'input.txt'); reset(f1);
readln(f1,L,N);
for i:=1 to n do read(f1,X[i]);
for i:=1 to N-1 do
for j:=i+1 to n do
if X[i]>X[j] then
begin
Y:=X[i]; X[i]:=X[j]; X[j]:=Y
end
end;
Procedure Solve;
var i, j : integer;
begin
Count:=0; i:=1;
while i<=N do
begin
j:=i+1;
while (j<=n) and (X[j]-X[i]<=2*L) do j:=j+1;
Count:=Count+1;
i:=j
end
end;
begin
Init;
Solve;
assign(f2,'output.txt'); rewrite(f2);
write(f2,Count); close(f2);
end.
Задача 6. "Наименьшее из больших" (20 баллов).
Дано натуральное число N.
Требуется написать программу для определения наименьшего из больших чисел, составленных из тех же цифр.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит заданное N (10£N£10100).
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одну строку - найденное число или 0, если такого числа не существует.
Пример файла входных данных:
132
Пример файла выходных данных (для приведенного выше входного файла):
213
Разбор задачи № 6
Двигаясь по цифрам числа справа налево найдем пару соседних цифр, у которой левая ai меньше правой ai+1. Если такой пары цифр нет, то значит и не существует искомого числа. Теперь найдем в правой части наименьшую из больших ai цифру (обозначим ее через aj). Поменяем эти две цифры, а после этого переставим цифры, начиная с (i+1)-ой в обратном порядке. Получаем искомое число. Этот алгоритм реализован в следующей программе.
var
s : string;
c : char;
i, j, l : integer;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
readln(s);
l:=length(s); i:=l-1;
while (i>0) and (s[i]>=s[i+1]) do i:=i-1;
if i=0 then write(0) else
begin
j:=l;
while s[i]>=s[j] do j:=j-1;
c:=s[i]; s[i]:=s[j]; s[j]:=c;
for j:=1 to (l-i) div 2 do
begin
c:=s[i+j]; s[i+j]:=s[l+1-j]; s[l+1-j]:=c
end;
write(s)
end
end.
Задача 7. "Бутылки" (30 баллов)
В цех вторичной переработки поступают бутылки N (1≤N≤8) видов: A, B, C, … (первые N заглавных букв латинского алфавита). Бутылки поступают на переработку партиями из N контейнеров, причем в каждом контейнере могут находиться бутылки различных видов. Перед вторичной переработкой бутылок специальные рабочие сортируют их по видам таким образом, чтобы после сортировки в каждом из поступивших контейнеров остались бутылки только одного вида. В каждом из контейнеров может помещаться неограниченное количество бутылок.
Требуется написать программу, которая определяет минимальное количество перемещений бутылок, обеспечивающих их сортировку по видам, причем за каждое перемещение можно переместить только одну бутылку из одного контейнера в другой.
Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение по времени тестирования: 5 секунд на один тест.
Формат входных данных:
Входной файл INPUT.TXT состоит из N+1 строк. В первой строке записано число N. Во второй строке располагаются разделенные пробелами N целых числа, соответствующие количеству бутылок вида A, B, C, … в первом контейнере. В последующих cтроках содержится аналогичная информация для второго, третьего, …, N-го контейнеров соответственно. Известно, что количество бутылок в каждом из контейнеров не превосходит 32767.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен состоять из двух строк. В первой располагается последовательность из символов A, B, C, …, которая определяет какого вида бутылки находятся после сортировки в 1-м, 2-м, …, N-м контейнерах. Во второй строке располагается число, определяющее искомое количество перемещений бутылок.
Если возможно несколько вариантов ответа, то необходимо выдать любой из них.
Пример файла входных данных:
4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Пример файла выходных данных (для приведенного выше входного файла):
ABCD
102
Разбор задачи № 7
Задача решается полным перебором вариантов перемещения бутылок. Для этого надо воспользоваться одним из алгоритмов генерирования всех перестановок чисел от 1 до N. В литературе описано много таких алгоритмов. В приведенной ниже программе используется алгоритм получения перестановок в лексикографическом порядке из работы С.М. Окулова "Перестановки", опубликованной в № 7 за 2000 год приложения "Информатика" к газете "Первое сентября".
Итак
пусть p1, p2, pN
- перестановка чисел от 1 до N. Тогда, чтобы переместить
все бутылки p1-го вида в первый ящик надо сделать 
перемещений (ai,j- количество бутылок j-го вида в i-том контейнере). Аналогично
получаются формулы и для остальных ящиков. Тогда всего для перекладки всех
бутылок потребуется 
перемещений. Легко заметить,
что в последнем соотношении первая сумма равна сумме всех элементов матрицы и
не зависит от перестановки, а потому может быть вычислена один раз, например
при вводе данных. Для получения минимального количества перемещений, таким
образом, необходимо найти такую перестановку, для которой максимальна сумма 
.
Представленный алгоритм реализован в программе
var
n, i, j, s : integer;
ss, m, max : longint;
a : array [1..8, 1..8] of integer;
p, pmax : array [0..8] of integer;
f1, f2 : text;
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 периодическая часть заключается в круглые скобки.
Требуется написать программу, которая определяет результат умножения Q на N, то есть непериодическую часть и минимальный период числа QxN. В случае получения результата умножения в виде конечной дроби скобки опускаются.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 1 секунда на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит две строки. В первой строке задается дробь Q, а во второй - число N.
Формат выходных данных:
В единственной строке выходного файла OUTPUT.TXT должен содержаться результат умножения Q на N.
Пример файла входных данных:
0.1(6)
3
Пример файла выходных данных (для приведенного выше входного файла):
0.5
Разбор задачи № B
Задача имеет 2 решения. Например, можно перевести дробь в обыкновенную, потом числитель умножить на N, а затем снова делить, выделяя период. Но в длинной арифметике это технически сделать сложно. Проще разработать алгоритм умножения периода на число, а потом, если потребуется, период сократить, при этом еще нужно помнить, что 0.(9)=1, иначе период не будет минимальным.
Можно использовать следующее правило умножения периода правильной дроби на произвольное натуральное число:
1) если при умножении периода дроби на некоторое число количество цифр в произведении равно количеству цифр в периоде исходного числа, то период результата равен полученному произведению и переходим к (6), в противном случае - к (2);
2) "лишними" цифрами будем считать n-k первых слева цифр результата, где n - количество цифр в результате, k - количество цифр в периоде исходной дроби;
3) сложим число, образованное "лишними" цифрами, с числом, образованным правыми k цифрами промежуточного результата;
4) если количество цифр в получившемся результате сложения больше чем k, то процесс следует повторить с (2);
5) если количество цифр результата сложения стало равным количеству цифр периода исходной дроби, то период произведения равен последнему результату суммирования;
6) теперь надо попытаться сократить период. Для этого ищем повторяющиеся части периода и, если они есть, то уменьшаем длину периода. После этого, по возможности, сдвигаем период влево. Если период равен 9, то его удаляем, добавляя 1 к последнему разряду.
7) непериодическая (целая - для чисто периодических дробей) часть результата равна сумме чисел, образованных из "лишних" цифр каждого этапа. Если же у исходной дроби изначально была своя непериодическая часть, то умножить также следует и ее, а затем сложить с результатом умножения периода.
Рассмотрим два примера. Вначале выполним умножение 0,(7)*16. Для этого умножим период дроби на 16: 7*16=112. В периоде дроби одна цифра, а в произведении - три цифры. Следовательно "лишними" являются две левые цифры, образующие число 11. Прибавив 11 к 2, получим 13, что опять превышает исходную длину периода на одну цифру. Вновь сложим "лишнее" число 1 с правой цифрой результата, 1+3=4. Количество цифр результата равно количеству цифр в периоде исходной дроби, следовательно, период произведения равен 4. Целая же часть результата умножения равна 11+1=12 (в процессе ее формирования участвуют только "лишние" цифры). Таким образом получается ответ: 0,(7)*16=12,(4).
В качестве второго примера выполним умножение 0,7(6)*12. Для этого сначала умножим на 12 периодическую часть. 6*12=72. В получившемся произведении две цифры, а в исходном периоде - одна. Следовательно, "лишнее" число равно 7, результат сложения равен 2+7=9. В получившемся результате количество цифр равно количеству цифр в периоде исходной дроби, т.е. период произведения равен 9. Непериодическая часть произведения равна единственному "лишнему" числу - 7. Таким образом, 0,0(6)*12=0,7(9)=0,8. Затем умножим на 12 непериодическую часть исходной дроби 0,7*12=8,4. В результате получаем: 0,7(6)*12 = 8,4+0,8= 9,2.
Задача C. "Сообщение" (20 баллов)
Из пункта А в пункт Б с помощью двух курьеров было отправлено сообщение, состоящее из символов 0 и 1. Каждый из курьеров шутки ради проделал несколько раз следующее преобразование сообщения: любую часть, содержащую две единицы записал в обратном порядке (перевернул). Например, в сообщении 11010100 курьер мог перевернуть подстроку, составленную из символов со 2 по 5 позиции, и тогда получалось сообщение 10101100. Получив два сообщения в пункте Б решили проверить их эквивалентность, т.е. можно ли получить одно из другого с помощью описанных преобразований.
Требуется написать программу, которая определяет эквивалентность сообщений и если сообщения эквивалентны, находит способ (достаточно только один) преобразования одного сообщения в другое.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 3 секунды на один тест.
Формат входных данных:
Входной файл состоит из двух строк – полученных сообщений. Их длина не превышает 100 символов.
Формат выходных данных:
Если сообщения не эквивалентны, то выходной файл должен содержать только строку «No». Если сообщения эквивалентны, то в первую строку выходного файла нужно вывести слово «Yes», в последующие последовательность преобразований первого сообщения во второе. Каждое преобразование записывается в отдельной строке в виде пары чисел i, j (разделенных пробелом), означающей, что переворачивается подстрока, составленная из символов с номерами i, i+1, ..., j.
Пример файла входных данных:
100011100
001011001
Пример файла выходных данных (для приведенного выше входного файла):
Yes
6 9
3 8
1 5
Задача D. "Свинья-копилка" (30 баллов)
Для того чтобы начать свой бизнес, юный коммерсант решил накопить немного денег. С этой целью он отыскал свинью-копилку и начал собирать деньги.
Известно, что определить накопленную сумму в копилке можно, только разбив копилку. Однако юному коммерсанту не хотелось делать это раньше времени, т.е. до тех пор, пока там не накопилась бы требуемая сумма. Избежать этого ему помог его напарник, который посоветовал, как можно оценить минимальное количество денег внутри копилки, зная её вес без монет, вес с монетами и вес монет каждого типа.
Требуется написать программу, которая определяла бы минимальную сумму денег, которая может находиться в копилке, по известным исходным данным.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 5 секунд на один тест
Формат входных данных:
Входной файл INPUT.TXT состоит из следующей последовательности строк. В первой строке содержатся два целых числа:
E – вес пустой копилки (1≤E≤10000);
F – вес копилки, заполненной монетами (1≤E≤F≤10000);
Вторая строка содержит целое число N (1≤N≤500) — количество типов монет.
Каждая из последующих N строк служит для описания монет заданных типов и содержит по два целых числа — Pi и Wi (1≤ Pi ≤30000, 1≤ Wi ≤10000, 1≤ i ≤ N), где Pi — достоинство монеты i-го типа, а Wi — ее вес.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно целое число — значение минимальной суммы денег, которая может находиться в копилке. Если заданный вес копилки F не может быть достигнут с монетами заданного типа, то выходной файл должен содержать сообщение "No".
Пример файлов входных и выходных данных:
|
INPUT.TXT |
OUTPUT.TXT |
|
10 110 |
60 |
|
2 |
|
|
1 1 |
|
|
30 50 |
|
|
INPUT.TXT |
OUTPUT.TXT |
|
10 110 |
100 |
|
2 |
|
|
1 1 |
|
|
50 30 |
|
|
INPUT.TXT |
OUTPUT.TXT |
|
1 6 |
No |
|
2 |
|
|
10 3 |
|
|
20 4 |
|
Разбор задачи № D
Задача решается методом динамического программирования. Для этого обозначим через D(w, k) – минимальную сумму монет в копилке, которые имеют вес w и состоят из монет первых k типов. Для этой функции имеет место следующее соотношение D(w, k)= min{D(w, k-1), D(w-Wk, k)+Pk}. Ответом задачи будет значение функции D(F-E, N). Вычисление этого выражения легко организовать с помощью одного одномерного массива. Реализацию представленного алгоритма смотрите в программе.
var
e, f, n, i, j : integer;
m : longint;
P, W : array [1..500] of integer;
D : array [0..10000] of longint;
f1, f2 : text;
begin
assign(f1,'input.txt'); reset(f1);
read(f1,e,f);
f:=f-e;
read(f1,n);
for i:= 1 to n do read(f1,P[i],W[i]);
D[0]:=0; for i:=1 to f do D[i]:=maxlongint;
for i:=1 to n do
begin
j:=W[i];
while j<=f do
begin
m:=D[j-W[i]];
if m<maxlongint then m:=m+P[i];
if m<D[j] then D[j]:=m;
j:=j+1
end
end;
assign(f2,'output.txt'); rewrite(f2);
if D[f]=maxlongint then write(f2,'No')
else write(f2,D[f]);
close(f2)
end.
Задача E. "Сундук Билли Бонса" (20 баллов).
Билли Бонс положил в сундук некоторое количество золотых монет. На второй год он вынул из сундука сколько-то монет. Начиная с третьего года он добавлял столько монет, сколько было в сундуке два года назад.
Требуется написать программу, которая определит сколько монет было в сундуке в первый и во второй года, если в X-м году там оказалось ровно Y монет.
Пояснение: если в первый год положить 5 монет, а во второй год вынуть 3 монеты, то начиная с первого года в сундуке будет 5, 2, 7, 9, 16, 25, ... монет.
Технические требования:
Входной файл: INPUT.TXT
Ограничение по времени тестирования: по 3 секунды на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит числа X (3£X£20) и Y (1£Y£32767), записанные через пробел.
Формат выходных данных:
В выходной текстовый файл OUTPUT.TXT записываются через пробел количество монет в первый и второй года.
Пример файла входных данных:
6 25
Пример файла выходных данных (для приведенного выше входного файла):
5 2
Разбор задачи № E
Задача решается за два шага. Вначале обозначим количество монет в первый и второй года через a и b. Тогда в третий год будет a+b монет, в четвертый – a+2b, в пятый – 2a+3b и так далее. Легко заметить, что коэффициентами при a и b являются последовательные числа Фибоначчи. Вычислив их для x-го года, получим уравнение с двумя неизвестными a и b. Это уравнение решаем в целых числах перебором всех возможных вариантов.
var
a, b, x, y, x1, x2, xx, i : integer;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(x,y);
x1:=0; x2:=1;
for i:=3 to x do
begin xx:=x1+x2; x1:=x2; x2:=xx end;
a:=y div x1; b:=0;
while x1*a+x2*b<>y do
begin
while x1*a+x2*b<y do b:=b+1;
if x1*a+x2*b<>y then begin a:=a-1; b:=0 end
end;
write(a,' ',b)
end.
Задача F. "Постоянная Капрекара" (20 баллов).
Возьмем четырехзначное число, в котором не все цифры одинаковы, например 6264. Расположим цифры сначала в порядке убывания - 6642; затем, переставив их в обратном порядке, получим 2466. Вычтем последнее число из 6642. На следующем шаге с полученной разностью проделаем тоже самое. Через несколько таких действий получится число, переходящее само в себя и называемое постоянной Капрекара.
Требуется написать программу, которая находит эту постоянную и количество шагов для ее получения из заданного четырехзначного числа.
Технические требования:
Входной файл: INPUT.TXT
Ограничение по времени тестирования: по 3 секунды на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит одну строку, в которой записано четырехзначное число.
Формат выходных данных:
В выходной текстовый файл OUTPUT.TXT записываются: в первой строке постоянная Капрекара, во второй – количество шагов для ее получения.
Пример файла входных данных:
1234
Пример файла выходных данных:
<постоянная Капрекара>
3
Разбор задачи № F
Для введенного числа находим его цифры и записываем в массив. Упорядочим массив по возрастанию, после чего находим число согласно условию задачи. Продолжаем до тех пор, пока числа не совпадут.
var
n, n1, c : integer;
function sled(n:integer): integer;
var a : array [1..4] of integer;
i, j, x : integer;
begin
for i:=1 to 4 do
begin
a[i]:=n mod 10;
n:=n div 10
end;
for i:=1 to 3 do
for j:=1 to 4-i do
if a[j]>a[j+1] then begin x:=a[j]; a[j]:=a[j+1]; a[j+1]:=x end;
sled:=(a[4]-a[1])*999+(a[3]-a[2])*90
end;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(n);
c:=0; n1:=sled(n);
while n<>n1 do
begin
c:=c+1;
n:=n1;
n1:=sled(n)
end;
writeln(n);
write(c)
end.
Задача G. "Шифровка" (20 баллов)
Для кодирования сообщения используют следующие действия: сообщение записывают, опуская пробелы, в прямоугольник заданной высоты по столбцам, а затем прочитывают строки в заданном порядке.
Например, для кодирования слова ПРОГРАММИРОВАНИЕ его записывают в прямоугольник высоты 4 следующим образом:
1 П Р И А
2 Р А Р Н
3 О М О И
4 Г М В Е
а затем, если выбрать порядок строк 3, 1, 2, 4, получают закодированное сообщение ОМОИПРИАРАРНГМВЕ.
Требуется написать программу, которая по заданным высоте прямоугольника и порядке прочтения строк при кодировке декодирует заданное сообщение.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 3 секунды на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит: в первой строке высоту прямоугольника (не больше 10), во второй – порядок прочтения строк (числа записаны через пробел), в третьей – закодированное сообщение, длина которого не превышает 200.
Формат выходных данных:
В выходной текстовый файл OUTPUT.TXT записывается декодированное сообщение.
Пример файла входных данных:
4
3 1 2 4
ОМОИПРИАРАРНГМВЕ
Пример файла выходных данных (для приведенного выше входного файла):
ПРОГРАММИРОВАНИЕ
Разбор задачи № G
В этой задаче необходимо было аккуратно запрограммировать работу со строками. Единственная трудность заключалась в случае неполного заполнения последнего столбца при шифровании. Как это преодолеть смотрите в программе.
var
n, i, j, k1, k2, kk : integer;
a : array [1..10] of integer;
s : string;
t : array [1..10] of string;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);readln;
readln(s);
k1:=length(s) div n;
k2:=length(s)-k1*n;
for i:=1 to n do
begin
if a[i]>k2 then kk:=k1 else kk:=k1+1;
t[a[i]]:=copy(s,1,kk);
delete(s,1,kk)
end;
for i:=1 to k1 do for j:=1 to n do s:=s+t[j][i];
for j:=1 to k2 do s:=s+t[j][k1+1];
writeln(s)
end.
Задача H. "Нить Ариадны" (20 баллов)
Тезею из лабиринта Минотавра помог выйти клубок ниток. Вы можете вместо клубка использовать персональный компьютер.
Требуется написать программу, которая вводит маршрут Тезея в лабиринте и находит обратный путь, по которому Тезей сможет выйти из лабиринта, не заходя в тупики и не делая петель.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 3 секунды на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит маршрут Тезея, который представлен строкой, состоящей из букв: N, S, W, E и длиной не более 200.
Буквы означают:
N - один "шаг" на север,
S - один "шаг" на юг,
W - один "шаг" на запад,
E - один "шаг" на восток.
Формат выходных данных:
В выходной текстовый файл OUTPUT.TXT записывается аналогично входному файлу найденный обратный путь.
Пример файла входных данных:
EENNESWSSWE
Пример файла выходных данных (для приведенного выше входного файла):
NWW
Разбор задачи № H
Представим, что движение осуществляется на квадратном клеточном поле с шагом 1 от точки (0, 0). В массиве будем хранить координаты посещенных точек (перед началом движения там всего одна нулевая точка). После каждого шага в одном из четырех направлений просмотром массива определяем: не были ли мы уже в этой точке. И если были, то удаляем из маршрута эту часть пути. Детали реализации алгоритма смотрите в программе.
var
s, t : string;
a : array [1..2,0..200] of integer;
i, j, k : integer;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
readln(s); t:='';
k:=0; a[1,k]:=0; a[2,k]:=0;
for i:=1 to length(s) do
begin
k:=k+1;
if s[i]='N' then begin a[1,k]:=a[1,k-1]; a[2,k]:=a[2,k-1]+1; t:=t+'S' end;
if s[i]='E' then begin a[1,k]:=a[1,k-1]+1; a[2,k]:=a[2,k-1]; t:=t+'W' end;
if s[i]='S' then begin a[1,k]:=a[1,k-1]; a[2,k]:=a[2,k-1]-1; t:=t+'N' end;
if s[i]='W' then begin a[1,k]:=a[1,k-1]-1; a[2,k]:=a[2,k-1]; t:=t+'E' end;
j:=0;
while (a[1,j]<>a[1,k]) or (a[2,j]<>a[2,k]) do j:=j+1;
if j<k then
begin
delete(t,j+1,k-j);
k:=j
end
end;
for i:=length(t) downto 1 do write(t[i])
end.
Задача I. "Сообщения" (20 баллов)
Для надежности некоторое сообщение было передано по линии связи трижды, но каждый раз ровно один символ был принят в искаженном виде.
Требуется написать программу, которая по трем полученным сообщениям восстановит исходное сообщение, или установит, что сделать это невозможно.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 3 секунды на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит три строки с тремя полученными сообщениями, которые представлены строками длиной не более 255.
Формат выходных данных:
В выходной текстовый файл OUTPUT.TXT записывается восстановленное сообщение или «NO», если сообщение невозможно восстановить.
Пример файла входных данных:
test
texs
eext
Пример файла выходных данных (для приведенного выше входного файла):
text
Разбор задачи № I
Эта задача была на одной из ленинградских олимпиад по информатике. Далее приводится решение Антона Суханова, победителя Всесоюзных и члена жюри Всероссийских олимпиад школьников по информатике.
Выпишем эти три текста в три строки друг под другом, как это сделано в примере.
Колонку из трех символов назовем искаженной, если в ней есть хотя бы один символ, отличный от других. Так как в трех текстах ровно 3 искаженных символа, то искаженных колонок не может быть больше трех. Рассмотрим подробно четыре случая:
а) 3 искаженных колонки. В каждой из искаженных колонок находится ровно один искаженный символ, который легко восстановить, ибо два других равны.
б) 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 групп (необязательно равных по численности). Голосование по любому вопросу теперь следовало проводить отдельно в каждой группе, причем считалось, что группа высказывается "за", если "за" голосует более половины людей в этой группе, а в противном случае считалось, что группа высказывается "против". После проведения голосования в группах подсчитывалось количество групп, высказавшихся "за" и "против", и вопрос решался положительно в том и только том случае, когда групп, высказавшихся "за", оказывалось более половины общего количества групп.
Эта система вначале была с радостью принята жителями острова. Когда первые восторги рассеялись, очевидны стали, однако, некоторые недостатки новой системы. Оказалось, что сторонники партии, предложившей систему, смогли оказать некоторое влияние на формирование групп избирателей. Благодаря этому, они получили возможность проводить некоторые решения, не обладая при этом реальным большинством голосов.
Пусть, например, на острове были сформированы три группы избирателей, численностью в 5, 5 и 7 человек соответственно. Тогда партии достаточно иметь по три сторонника в каждой из первых двух групп, и она сможет провести решение всего 6-ю голосами "за", вместо 9-и, необходимых при общем голосовании.
Требуется написать программу, которая по заданному разбиению избирателей на группы определит минимальное количество сторонников партии, достаточное для принятия любого решения.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 5 секунд на один тест.
Формат входных данных:
Входной файл INPUT.TXT состоит из двух строк. В первой строке записано натуральное число K<1001 - количество групп избирателей. Во второй строке через пробел записаны K натуральных чисел, которые задают количество избирателей в группах. Население острова не превосходит 30000 человек.
Формат выходных данных:
В выходной текстовый файл OUTPUT.TXT записывается найденное число.
Пример файла входных данных:
3
5 5 7
Пример файла выходных данных (для приведенного выше входного файла):
6
Разбор задачи № N
Хотя и условие задачи довольно длинное, но решение достаточно простое. Упорядочим массив количества избирателей в каждом в округе по возрастанию. Как следует из условия для победы в округе необходимо набрать более половины голосов в каждом округе и победить в более половины округов. Из этого следует, что для победы с минимальным общим количеством избирателей надо победить в округах с наименьшим количеством избирателей. Так как надо победить только в половине округов, то и сортировать массив надо только до середины. Подробности реализации приведенных аргументов смотрите в программе.
var
a : array [1..1000] of integer;
n, i, j, k, min : integer;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n div 2+1 do
begin
k:=i; min:=a[i];
for j:=i+1 to n do
if a[j]<min then begin min:=a[j]; k:=j end;
a[k]:=a[i]; a[i]:=min
end;
k:=0;
for i:=1 to n div 2+1 do
k:=k+a[i] div 2 +1;
write(k)
end.
Задача O. "ЧТО ТУТ СЧИТАТЬ?" (20 баллов)
Задано натуральное десятичное число N (N£1.000.000.000).
Требуется написать программу вычисления количества принадлежащих диапазону от 1 до N чисел, в двоичном представлении которых содержится ровно K значащих нулей. Например, для N=18 и K=3 таких чисел — 3 (8, 17, 18).
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 5 секунд на один тест.
Формат входных данных:
В текстовом файле INPUT.TXT в первой строке записано число N, а во второй - K.
Формат выходных данных:
Вывести в текстовый файл OUTPUT.TXT полученное количество.
Пример файла входных данных:
18
3
Пример файла выходных данных (для приведенного выше входного файла):
3
Задача P. "Коррозия металла" (20 баллов)
Для хранения двух агрессивных жидкостей A и B используется емкость с многослойной перегородкой, которая изготавливается из имеющихся N листов. Для каждого листа i (i = 1, …, N) известно время его растворения жидкостью A — ai и жидкостью B — bi. Растворение перегородки каждой из жидкостей происходит последовательно лист за листом, с постоянной скоростью по толщине листа.
Требуется написать программу проектирования такой перегородки, время растворения которой было бы максимальным.
Технические требования:
Выходной файл: OUTPUT.TXT
Ограничение времени: 10 секунд на тест
Формат входных данных:
В первой строке входного файла записано число N (1£N£256). В каждой из последующих N строк содержатся два положительных вещественных числа ai и bi, разделенные пробелом.
Формат выходных данных:
В первую строку выходного файла записать время растворения перегородки с точностью до 3 цифр после десятичной точки. В следующую строку файла записать номера листов в порядке их расположения от жидкости A к жидкости B, разделяя числа пробелами.
Пример файла входных данных:
4
1 2
1 2
0.5 1.5
7 3.5
Пример файла выходных данных
(для приведенного выше входного файла):
6.000
4 2 1 3
Задача Q. "Факториал" (20 баллов)
Факториалом натурального числа N (обозначается N!) называется произведение всех натуральных чисел от 1 до N включительно: N! = 1×2×3×…×N.
Требуется написать программу, которая определит, каким количеством цифр «0» заканчивается запись числа N! в K-ричной системе счисления.
Технические требования:
Ограничение времени: 5 секунд на тест.
Формат входных данных:
Во входном файла содержится два числа: N и K (1£N£2×109, 2£K£5000). Оба числа записаны в десятичной системе счисления.
Формат выходных данных:
В выходной файл вывести количество нулей, которыми в K-ричной системе счисления оканчивается число N!. Число вывести в десятичной системе счисления.
Пример файла входных данных:
10000 10
Пример файла выходных данных (для приведенного выше входного файла):
2499
Задача R. "Палиндром" (20 баллов)
Палиндром – это симметричная строка, т.е. она одинаково читается как слева направо, так и справа налево.
Требуется написать программу, которая по заданной строке определяет минимальное количество символов, которые необходимо вставить в строку для образования палиндрома.
Технические требования:
Выходной файл: OUTPUT.TXT.
Ограничение времени: 5 секунд на тест.
Формат входных данных:
Файл INPUT.TXT состоит из двух строк. Первая строка содержит одно число – длину N входной последовательности (3£N£5000). Вторая – строку длины N, которая состоит из прописных букв от ‘A’ до ‘Z’, строчных букв от ‘a’ до ‘z’, цифр от ‘0’ до ‘9’. Прописные и строчные буквы считаются различными.
Формат выходных данных:
Выходной файл OUTPUT.TXT состоит из одной строки. Эта строка содержит одно целое число, которое является искомым минимальным числом символов.
Пример файла входных данных:
5
Ab3Bd
Пример файла выходных данных
(для приведенного выше входного файла):
2
Задача S. "Гири" (20 баллов)
На левой чашке весов лежит груз в N грамм, где N - натуральное число. Имеется по одной гире в 1, 3, 9, 27, 81, ... грамм.
Требуется написать программу, которая укажет, какие гири и на какую чашку весов надо поставить, чтобы уравновесить груз.
Технические требования:
Выходной файл: OUTPUT.TXT.
Ограничение времени: 5 секунд на тест.
Формат входных данных:
Файл INPUT.TXT состоит из одной строки, в которой содержится число N (1£N£1000000000).
Формат выходных данных:
В выходной файл OUTPUT.TXT вывести номер гири (0 – 1 грамм, 1 – 3 грамма, 2 – 9 грамм, …) и через пробел символ ‘L’ если гиря ставится на левую чашку весов или ‘R’ иначе. Используемые гири выводить в порядке возрастания номеров.
Пример файла входных данных:
2
Пример файла выходных данных (для приведенного выше входного файла):
0 L
1 R
Задача T. "Числа" (20 баллов)
Задано натуральное число N.
Требуется написать программу, которая находит количество натуральных чисел, не превышающих N и не делящихся ни на одно из чисел 2, 3, 5.
Технические требования:
Выходной файл: OUTPUT.TXT.
Ограничение времени: 3 секунды на тест.
Формат входных данных:
Файл INPUT.TXT состоит из одной строки, в которой содержится число N (1£N£1000000000).
Формат выходных данных:
В выходной файл OUTPUT.TXT вывести найденное число.
Пример файла входных данных:
10
Пример файла выходных данных (для приведенного выше входного файла):
2
Задача V. "Числа" (20 баллов)
Для натуральных чисел X и Y будем говорить, что X входит в Y, если двоичную запись числа X можно получить из двоичной записи Y вычеркиванием нулевого, единичного или большего количества цифр. Например, X=1010 входит в Y=1001100.
Требуется написать программу, которая для двух данных натуральных чисел A и B найдет максимальное число C, входящее как в A, так и в B.
Технические требования:
Выходной файл: OUTPUT.TXT.
Ограничение времени: 3 секунды на тест.
Формат входных данных:
Файл INPUT.TXT состоит из одной строки, в которой через пробел записаны числа A и B (1£A, B£1000000000).
Формат выходных данных:
В выходной файл OUTPUT.TXT вывести найденное число C.
Пример файла входных данных:
3 6
Пример файла выходных данных (для приведенного выше входного файла):
3
Задача W. "Сумма" (20 баллов)
Требуется написать программу, которая находит по заданному n (2<n<1000) сто десятичных цифр дробной части числа Sn.
Технические требования:
Выходной файл: OUTPUT.TXT.
Ограничение времени: 3 секунды на тест.
Формат входных данных:
Файл INPUT.TXT состоит из одной строки, в которой записано число n.
Формат выходных данных:
В выходной файл OUTPUT.TXT вывести найденные цифры.
Пример файла входных данных:
3
Пример файла выходных данных (для приведенного выше входного файла):
83333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333
Задача X. "Цифра на N-ом месте" (20 баллов).
В бесконечную бинарную последовательность выписаны натуральные числа по возрастанию в двоичном виде: 11011100101110111100010011010.... Определить, какая цифра стоит на N-м месте.
Требуется написать программу для решения задачи.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени: 3 секунды
Формат входных данных:
Входной файл INPUT.TXT содержит натуральное число N (1≤N≤1000000000).
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать найденную цифру.
Пример файла входных данных:
5
Пример файла выходных данных (для приведенного выше входного файла):
1
Задача Y. "Первая цифра" (20 баллов)
Известно натуральное число k.
Требуется написать программу для определения такого наименьшего натурального число, которое уменьшается в k раз при зачеркивании первой цифры.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени: 10 секунд
Формат входных данных:
Единственная строка входного файла содержит целое число k (1 £ k£ 32767).
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать либо значение найденного числа, либо число 0, если такого числа не существует.
Пример файла входных данных:
6
Пример файла выходных данных (для приведенного выше входного файла):
12
Задача Z. "Домино" (20 баллов)
Дан комплект домино (0, 0), (0, 1), ..., (6, 6) (всего 28 штук).
Требуется написать программу, которая по заданным натуральным числам SUM и N найдет правильную раскладку из N костей так, чтобы их сумма была равна SUM.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение времени: 20 секунд
Формат входных данных:
Единственная строка входного файла содержит два целых числа SUM (0£ SUM£32767) и N (1£N£28), разделенных пробелом.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать либо найденную правильную раскладку (в файле должно быть N строк, в каждой строке через пробел записываются значения на кости домино), либо число 0, если такая раскладка невозможна.
Пример файла входных данных:
20
4
Пример файла выходных данных (для приведенного выше входного файла):
0 1
1 1
1 6
6 4
Рабочие листы
к вашим урокам
Скачать
6 661 359 материалов в базе
Настоящий материал опубликован пользователем Шукалович Татьяна Григорьевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс профессиональной переподготовки
500/1000 ч.
Курс профессиональной переподготовки
500/1000 ч.
Курс повышения квалификации
36 ч. — 180 ч.
Курс профессиональной переподготовки
300/600 ч.
Мини-курс
4 ч.
Мини-курс
3 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.