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

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;