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

Задача в неделю

Задача 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;