Олимпиадная информатика - 2015

Задача « Две дроби »

Однажды мудрая Сова подарила ослику Иа-Иа на его день рождения скромный, но очень по- лезный вычислительный прибор, который умеет выполнять три операции:
(A) прибавить единицу к данному числу;
(B) вычесть единицу из данного числа;
(C) заменить ненулевое число на обратное к нему.

К сожалению, на клавиатуре прибора отсутствуют многие клавиши, поэтому некоторые числа приходится получать из других чисел с помощью указанных трёх операций. Представьте, что ослику Иа-Иа из дроби a/b нужно получить дробь c/d. Как ему это сделать, используя только операции A, B и C?

Формат входного файла fractions.in Входной файл: В первой строке записаны через пробел два числа a и b - числитель и знаменатель несократимой дроби a/b, во второй строке также записаны через пробел два числа c и d - числитель и знаменатель несократимой дроби c/d. Все числа a, b, c, d целые, 1 <a,b,c,d <1000000. Дроби a/b и c/d различны.

Формат выходного файла fractions.out Выходной файл: В первой строке запишите одно число n - количество необходимых операций, которое не должно превышать 2 000 001. Во второй строке укажите последовательность из n символов A, B и C латин- ского алфавита - операций, с помощью которых из числа a/b можно получить c/d. Если решений несколько, выведите любое из них. Если из дроби a/b получить дробь c/d невозможно, выведите -1.

var a,b,c,d,x:longint;
    q,w:string;

begin
assign(input, 'fractions.in');
reset(input);
assign(output, 'fractions.out');
rewrite(output);
readln(a,b,c,d);
q:='';
while a<>b do
begin
if a>b then
 begin
a:=a-b;
q:=q+'C';
end else begin
x:=a;a:=b;b:=x;
q:=q+'B';
end;
end;
w:='';
while c<>d do
begin
if c>d then begin
c:=c-d;
w:='A'+w;
end else begin
x:=c;c:=d;d:=x;
w:='B'+w;
end;
end;
writeln(length(q)+length(w));
write(q+w);
close(input);
close(output);
end.

close
 

Разбор задачи №1 "Две дроби"

Сколько всё-таки можно придумать задач, в решении которых применяется алгоритм Евклида для нахождения НОД двух чисел! Ведь в условии по сути предлагается выполнять именно шаги алгоритма Евклида: при вычитании 1 из неправильной дроби замена большего числа на разность этих чисел и обмен значений при нахождении обратной дроби.

Третье действие - прибавление 1 - является обратным к первому. К результате применения алгоритма Евклида оба числа становятся равными (дробь равна 1). Запомним сколько и каких действий мы выполнили, чтобы получить из каждой дроби 1.

Для второй дроби перепишем действия в обратном порядке, заменяя их на обратные (вычитание 1 на прибавление 1, обмен значениями обратен сам себе - замена не требуется). Алгоритм решения задачи имеет вид пока первая дробь неравна 1 делаем нц если дробь неправильная-отнимаем 1 , иначе меняем местами числитель и знаменатель, ведем счетчик проведенных действий, приписываем обозначение действия в КОНЦЕ строки-ответа кц тоже для второй строки только приписываем обозначение ОБРАТНОГО действия в НАЧАЛЕ строки.

Выводим общее количество операций и объединение строк-ответов. Даже при самых больших значениях (1000000/1 и 1000000/1) укладываемся в ограничение на количество действий (2000001). В задаче не требуется минимизировать число действий.